A two-dimensional Turing machine with a very simple set of rules but complicated emergent behavior.

The machine has 2 states and 3 colors, and is 596440 in Wolfram's numbering scheme. If it is universal, then it represents the smallest possible universal Turing machine. Is it universal?

A crash course in the mathematics behind Turing's results and how it applies to the very practical problem of programming in C. Explains the connection between Turing Machines, Lambda Calculus, types, Classical Logic and proofs.

Chaitin compares and contrasts Gödel's, Turing's and his own work in a straight-forward manner using Lisp.

Alan Turing proved in 1936 that a general algorithm to decide for all program-input pairs whether a program will halt or run forever cannot exist.

Claims that any calculation that is possible can be performed by an algorithm running on a computer, provided that sufficient time and storage space are available.