Invitation to Computability

Invitation to Computability

Text Register Machine Programs

First steps
Simple programs
When does a program halt?
Functions defined by programs
Tidy programs

Issues

Computability
Algorithmic problems
What is coding?
Reduction of one problem to another

More Programs

Tools to help write programs
Programs for Arithmetic
Primitive Recursion

Universal Programs

Universal Programs

The Enumeration Theorem

Coding words by numbers
The T predicate

Undecidability

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

Self-Writing Programs and the Recursion Theorem

Self-Replicating Programs

Powered by Jupyter Book

What is coding?

What is coding?¶

previous

Algorithmic problems

next

Reduction of one problem to another

By Lawrence S. Moss
© Copyright 2023.