Alacre castoro

Questa voce sull'argomento teorie dell'informatica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Questa voce o sezione sull'argomento informatica è priva o carente di note e riferimenti bibliografici puntuali.

Nella teoria della computabilità un alacre castoro (in inglese "busy beaver", letteralmente "castoro indaffarato", dall'espressione colloquiale per indicare una persona industriosa) è una macchina di Turing che ottiene la massima "attività delle operazioni" (come misurato dal numero di passi eseguiti, o dal numero dei simboli non vuoti che essa stampa sul nastro) tra tutte quelle in una determinata categoria. Un alacre castoro deve rispettare dei vincoli sulla sua struttura, fra cui il requisito che esso deve terminare in un numero finito di passi nel caso parta su un nastro vuoto.

Si può dimostrare che una funzione dell'alacre castoro, che quantifica il limite superiore dell'attività di una macchina di Turing di una data classe, è una funzione non computabile, in quanto cresce asintoticamente più di quanto faccia una qualunque funzione computabile. Il concetto fu introdotto per la prima volta da Tibor Radò in un articolo del 1962, On Non-Computable Functions (Sulle funzioni non computabili).