Busy Beaver

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

Definitie[bewerken]

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 dezelfde bandalfabet hebben, termineren met de lege band als invoer na minder dan of even veel stappen als M.

De busy beaver-functie 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[bewerken]

Hoewel de busy beaver-functie voor alle invoerwaarden gedefinieerd is, is ze niet berekenbaar; dat wil zeggen dat er geen Turingmachine bestaat die de busy beaver-functie berekent.

Om dit te bewijzen, we doen een bewijs uit het ongerijmde. Stel dat de busy beaver-functie 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 kan men S(n+k) berekenen. We simuleren M op een andere Turingmachine en kijken 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 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 busy beaver-functie niet berekenbaar is.

Groeisnelheid[bewerken]

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