Program Examples

A 4-State Busy Beaver

The busy beaver problem is an interesting theoretical computer science problem. The problem is to find the smallest number of states that outputs as much data as possible yet eventually halts on it's own. More formally it goes something like this — given an n-state Turing machine with a two symbol alphabet {0, 1}, what is the maximum number of 1s that the machine may print on an initially blank tape before halting?

This problem turns out to be non-computable, that is, for a small number of states an answer can be found, but in general it cannot be solved. Theorists call such problems non-computable. The number of steps it takes to run to completion (halt) grows very rapidly as the number of states increase. A 3-state example takes 14 steps while this 4-state example takes 107 steps. Increasing from there, a 5-state example has been found that takes 47,176,870 steps, and a 6-state example that takes 2.584 x102879 steps. I will not be trying any of these in the near future.

The States Used For This Example (Explanation of the Programming Syntax Used)

(0,0) -> (1,1) Right
(0,1) -> (1,1) Left
(0,B) -> (1,1) Right

(1,0) -> (0,1) Left
(1,1) -> (2,0) Left
(1,B) -> (0,1) Left

(2,0) -> (2,1) Halt
(2,1) -> (3,1) Left
(2,B) -> (2,1) Halt

(3,0) -> (3,1) Right
(3,1) -> (0,0) Right
(3,B) -> (3,1) Right


If you liked the Turing machine, check out the nickle printing robot I created a few years ago.


Turing's Cathedral: The Origins of the Digital Universe

The book focuses on a small group of men and women, who built one of the first computers to realize Alan Turing’s vision of a Universal Machine.


Alan Turing: The Enigma The Centenary Edition

This classic biography of the founder of computer science, reissued on the centenary of his birth with a substantial new preface by the author, is the definitive account of an extraordinary mind and life.