A Programmable Prototype to Build Turing Machines

Home Alan TURING History Turing machine The actual experimental prototype Some diagrams of Turing machines for this prototype Presentations Presse Simulator A new
machine
Machines Ideas Description How the machine operates Technologies First Turing machine Easy Calculations Sequences Interesting Colleges University Talks Videos Contact


  Interesting programs  

Fibonacci sequence



Un+2 = Un + Un+1


9 states		    
 
 
Collatz Conjecture



Also called
the Syracuse conjecture


The machine stops
when it reaches the value 1.

6 states
>
 
 
Calculation of the GCD
of 2 integers written
in unary




11 states		  
 


Bijection between
the natural numbers N
and the points of the plane
of integer and positive
coordinates


10 states


             


Reverse a string

10 states


Each character is moved
from left to right
by a series of transpositions.
 
 
Calculation of N modulo p
in unary
N > 0 and p > 0

7 states
 
 
Euclidean division
of A by B in unary

9 states








  Busy beaver See the article on Wikipedia

>

Busy beaver   BB2

2 states   2 symbols { b,1 }

6 cycles

Score = 4
 
 
 
Busy beaver   BB3

3 states   2 symbols { b,1 }

21 cycles

Score = 5
 
 
 
Busy beaver   BB4

4 states   2 symbols { b,1 }

107 cycles

Score = 13
 
 
 
Busy beaver   BB5

5 states   2 symbols { b,1 }

47 176 870 cycles

Pour la science N°570 		     
 
 
 
Busy beaver

2 states   3 symbols { b,0,1 }

38 cycles

Score = 9
 
 
 
Busy beaver

3 states   3 symbols { b,0,1 }

Number of cycles
≥ 119 112 334 170 342 540

Score ≥ 374 676 383

Wikipedia