Busy beaver
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 
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 hetzelfde 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 
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 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.

Theoretische informatica