Busy beaver

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Busy Beaver)
Ga naar: navigatie, zoeken

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

Definitie[bewerken]

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

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

De busybeaverfunctie is de wiskundige functie die gedefinieerd is als: is het aantal stappen dat de busy beaver met toestanden doet voordat hij stopt. Enkele waarden van :

Bewijs van niet-berekenbaarheid[bewerken]

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 met toestanden, dan kan men berekenen. We simuleren op een andere turingmachine en bekijken de toestand van na stappen. Is gestopt, dan weten we dus dat na een eindig aantal stappen stopt. Is dan nog niet gestopt, dan weten we zeker dat oneindig lang door zal gaan. Omdat willekeurig gekozen was, hebben we nu dus een oplossing gevonden voor het stopprobleem. Het stoppprobleem 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[bewerken]

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.