Back to List

Notes and Reflections on Books and Media

by Hannah Leitheiser

Turing Machine: Busy Beaver

#turingmachine #entscheidungsproblem #computer

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine

Charles Petzold

2008

2019-04-09

"We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q1: q2. .... qR; which will be called "m-configurations". The machine is supplied with a "tape" (the analogue of paper) running through it, and divided into sections (called "squares") each capable of bearing a "symbol"..." - Alan Turing - Charles Petzold, The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine (2008)

The syntax of Turing machines vary. I got this instruction set from Wikipedia. The first line

A 0 1 R B

means if the current state is A and the tape currently reads 0, write 1, move the head right, and change to state B. Busy Beaver is the longest running program that does not go on forever. Programs like this are grouped by the number of states and number of kinds of characters printed and only a handful are known.