Turing Machines

Turing Machines zijn machines die enen en nullen schrijven op een oneindige band, afhankelijk van het programma waarmee ze zijn geprogameerd. De Turing machine bestaat uit een aantal staten waaronder een haltstatus. Als de Turingmachine in de haltstatus komt, stopt hij direct. De instructies voor een status bestaan uit de volgende:

<huidige status> <huidige symbool> <nieuw symbool> <richting> <nieuwe status>

De huidige status is meestal een cijfer, maar de status kan ook een letter hebben. De Turing Machine begint in status nul met zijn lezer, waarmee hij het huidige symbool leest, een nul leest, want de band begint met alleen maar nullen. Dan schrijft de Turing machine een nieuw symbool, schuift een stapje op en gaat naar een andere of dezelfde status. Daar leest hij een nieuw symbool.

Voorbeeld van een Turing machine programma:

0 _ 1 r 1 
0 1 1 l halt 
1 _ 1 l 0

Deze Turing machine stopt na 3 stappen en heeft dan 2 enen geschreven. Turing machines kunnen ook zo geprogrameerd worden dat ze niet stoppen.

De grote getallen

Met behulp van deze machines van Alan Turing maakte Rado een extreem snel groeiende functie: $\Sigma(n)$. Voor groot genoege n geld dat $\Sigma(n) > f(n)$, waar $f(n)$ een recursief gedefinieerde functie is, zoals BEAF. De volgende waarden en ondergrenzen zijn bekend:

• $\Sigma(1) = 1$
• $\Sigma(2) = 4$
• $\Sigma(3) = 6$
• $\Sigma(4) = 13$
• $\Sigma(5) \geq 4098$  
• $\Sigma (6)>3,514\cdot 10^{18276}$
• $\Sigma(18) > G$ waar G Graham's getal voorstelt

Het is verwacht dat $\Sigma(5)$ gelijk is aan 4098, er moeten nog 42 machines worden geanalyseerd.

De machines die deze grenzen maken worden Busy Beavers genoemd.

Bronnen

[1]

[2]