Busy Beaver

Een Busy Beaver is een Turingmachine met alfabet {#,1} die de Busy Beaver functie berekent. De Busy Beaver functie $S:N\rightarrow N$ berekent het maximum aantal stappen dat een Busy Beaver van (n+1) toestanden kan doen op de lege invoerband, zonder in een oneindige lus te gaan.

We mogen veronderstellen dat een Turing machine n toestanden $q_1, q_2, \ldots ,q_n$ heeft en één aanvaardbare halttoestand h. Enkele waarden van S(n):

S(1)=1

S(2)=6

S(3)=21

S(4)=107

S(5) ≥ 47176870

S(6) > 10²⁸⁷⁹

Niet-berekenbaarheid

De Busy Beaver functie is niet Turing berekenbaar. We doen een bewijs uit het ongerijmde. Stel dat de Busy Beaver functie wel Turing berekenbaar is, dan bestaat er een Turingmachine die deze functie berekent. Nu heeft men echter een oplossing voor het stop-probleem want gegeven een Turingmachine M met n toestanden en een invoer x van lengte k, dan kan men $S(n+k)$ berekenen. We simuleren M op een andere Turingmachine en men bekijkt de toestand van M na $S(n+k)$ stappen. Is M gestopt, dan weten we dat M na een eindig aantal stappen stopt. Is M dan nog niet gestopt, weten we zeker dat M oneindig lang door zal gaan. We hebben nu dus een oplossing gevonden voor het stop-probleem, wat tegenstrijdig is want het is bewezen dat het stop-probleem geen oplossing heeft.

Snelst groeiende functie

Er bestaat geen Turing berekenbare functie die sneller stijgt dan de Busy Beaver functie. We voeren weer een bewijs uit het ongerijmde. Neem aan dat er wel een Turing berekenbare functie is die sneller stijgt dan de Busy Beaver functie, dan kan men die gebruiken als bovengrens voor de Busy Beaver functie om het stop-probleem alsnog op te lossen, wat natuurlijk niet kan.