b'\n_START_ARTICLE_\nBusy beaver\n_START_PARAGRAPH_\nEen 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.\n_START_SECTION_\nBewijs van niet-berekenbaarheid\n_START_PARAGRAPH_\nHoewel de busybeaverfunctie voor alle invoerwaarden gedefinieerd is, is ze niet berekenbaar; dat wil zeggen dat er geen turingmachine bestaat die de busybeaverfunctie berekent. _NEWLINE_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.\n_START_SECTION_\nGroeisnelheid\n_START_PARAGRAPH_\nEr 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.'