Alacre castor

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În teoria calculabilității un castor alacru (în engleză „busy beaver”, literalmente „castor ocupat”, expresia colocvială pentru a indica o persoană harnică) este o mașină Turing care obține „activitățile operaționale” maxime (măsurate prin numărul de pașii efectuați sau numărul de simboluri ne-goale pe care le imprimă pe bandă) dintre toți cei dintr-o anumită categorie. Un castor vioi trebuie să respecte anumite constrângeri asupra structurii sale, inclusiv cerința ca acesta să se termine într-un număr finit de pași în cazul în care începe pe o centură goală.

Se poate arăta că o funcție a castorului halter, care cuantifică limita superioară a activității unei mașini Turing dintr-o anumită clasă, este o funcție necomputabilă, deoarece crește asimptotic mai mult decât o face orice funcție calculabilă. Conceptul a fost introdus pentru prima dată de Tibor Rado într-un articol din 1962, Despre funcțiile necomputabile (funcțiile nu pot fi calculate).

Alte proiecte

Controlul autorității GND ( DE ) 4282517-9
Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT