Alacre castor
Î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
- Wikimedia Commons conține imagini sau alte fișiere despre castorul dornic
Controlul autorității | GND ( DE ) 4282517-9 |
---|