Busy beaver

Een busy beaver met $n$ toestanden is een terminerende turingmachine die een zo groot mogelijk aantal stappen doet. De busybeaverfunctie wijst aan een getal $n$ het aantal stappen toe dat de busy beaver met $n$ toestanden doet. De busybeaverfunctie is een totale functie die niet berekenbaar is.

Definitie

Een busy beaver met $n$ toestanden is een turingmachine $M$ waarvoor het volgende geldt:

• $M$ heeft $n$ toestanden plus een eindtoestand;
• het bandalfabet van $M$ is $\{\Box ,1\}$, waarbij $\Box$ het blank-symbool is;
• als $M$ wordt aangezet met de lege band als invoer, termineert $M$ na een eindig aantal stappen;
• alle andere turingmachines met $n$ toestanden en een eindtoestand, die hetzelfde bandalfabet hebben, termineren met de lege band als invoer na minder dan of even veel stappen als $M$.

De busybeaverfunctie is de wiskundige functie $S:\mathbb {N} \rightarrow \mathbb {N}$ die gedefinieerd is als: $S(n)$ is het aantal stappen dat de busy beaver met $n$ toestanden doet voordat hij stopt. Enkele waarden van $S(n)$:

• $S(1)=1$
• $S(2)=6$
• $S(3)=21$
• $S(4)=107$
• $S(5)\geq 47176870$
• $S(6)>10^{2879}$

Bewijs van niet-berekenbaarheid

Hoewel de busybeaverfunctie voor alle invoerwaarden gedefinieerd is, is ze niet berekenbaar; dat wil zeggen dat er geen turingmachine bestaat die de busybeaverfunctie berekent.

Om dit te bewijzen, doen we een bewijs uit het ongerijmde. Stel dat de busybeaverfunctie wel berekenbaar is. Dan bestaat er een turingmachine die deze functie berekent. Nu heeft men echter een oplossing voor het stopprobleem op lege band: gegeven een turingmachine $M$ met $n$ toestanden, dan kan men $S(n)$ berekenen. We simuleren $M$ op een andere turingmachine en bekijken de toestand van $M$ na $S(n)$ stappen. Is $M$ gestopt, dan weten we dus dat $M$ na een eindig aantal stappen stopt. Is $M$ dan nog niet gestopt, dan weten we zeker dat $M$ oneindig lang door zal gaan. Omdat $M$ willekeurig gekozen was, hebben we nu dus een oplossing gevonden voor het stopprobleem. Het stopprobleem op lege band is, net als het eigenlijke stopprobleem, onbeslisbaar. Daarom hebben we nu een tegenspraak afgeleid, en moeten we concluderen dat de busybeaverfunctie niet berekenbaar is.

Groeisnelheid

Er bestaat geen berekenbare functie die sneller stijgt dan de busybeaverfunctie. We voeren weer een bewijs uit het ongerijmde. Neem aan dat er wel een berekenbare functie is die sneller stijgt dan de busybeaverfunctie, dan kan men die in plaats van de busybeaverfunctie gebruiken in het bovenstaande bewijs.