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

Contents

Computability
Concrete and Abstract Models of Computation
Finite vs. Infinite

Computability

Contents

Computability
Concrete and Abstract Models of Computation
Finite vs. Infinite

Computability¶

Concrete and Abstract Models of Computation¶

Finite vs. Infinite¶

previous

Tidy programs

next

Algorithmic problems

By Lawrence S. Moss
© Copyright 2023.