Skip to main content

Ctrl+K

Invitation to Computability and Recursion

Themes

Computability: choices
Algorithmic problems, decidable and undecidable
Reduction of one problem to another
Computable functions on encoded structures
Recursion

Text Register Machine Programs

Instructions of 1#
How to run programs
Basic programs
Halting
Functions defined by programs
Tidy programs

More Programs

A tool to help write programs
Programs for arithmetic
The s-m-n Theorem

Universal Programs

Universal programs
Further results on universal programs

Computable Functions of Numbers

Primitive recursion
The T predicate
Mu-recursive functions
Ackermann’s function
Turing computability

The Recursion Theorem

Self-writing programs
The Recursion Theorem
Reflective \(\onehash\)

Computably Enumerable Sets And Beyond

Computably enumerable sets

Undecidability

The halting problem
The busy beaver problem
Tiling
Post’s Correspondence Problem
Matrix mortality

Applications to Logic

The Church-Turing Theorem via tiling
The Church-Theorem via matrix mortality

Repository
Open issue

Index

By Lawrence S. Moss

© Copyright 2023.