Skip to main content

Ctrl+K

Invitation to Computability

Issues

Computability: several notions
Algorithmic problems
Computable functions on encoded structures
Reduction of one problem to another

Text Register Machine Programs

First steps
Basic programs
Halting
Functions defined by programs
Tidy programs

More Programs

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

Universal Programs

Two-by-Two encoding
Universal programs

Computable Functions of Numbers

The T predicate
Mu-recursive functions

The Recursion Theorem

Self-writing programs
The Recursion Theorem

Undecidability

The halting problem
The busy beaver problem
Tiling
Post’s Correspondence Problem
Logic

Repository
Open issue

Index

By Lawrence S. Moss

© Copyright 2023.