miniatura|Aquest "diagrama espai-temps" mostra l'estat de la cinta de memòria en una fila durant els primers 100.000 passos temporals del millor castor ocupat de 5 estats de dalt a baix. El taronja és "1", el blanc és "0" (imatge comprimida verticalment). En informàtica teòrica, el joc del castor ocupat pretén trobar un programa final d'una mida determinada que (segons la definició) produeixi la major quantitat de sortida possible o s'executi durant el nombre més llarg de passos. Com que es concebeix fàcilment un programa en bucle sense fi que produeixi una sortida infinita o que s'executi durant un temps infinit, aquests programes s'exclouen del joc. En lloc dels llenguatges de programació tradicionals, els programes utilitzats al joc són màquines de Turing d'estat n, un dels primers models matemàtics de computació.
Les màquines de Turing, peça clau d'aquest problema, consten d'una cinta infinita i un conjunt finit d'estats que serveixen com a "codi font" del programa. Produir la màxima sortida es defineix, en aquest cas, com escriure el nombre més gran d'1's a la cinta. Això és equivalent a intentar aconseguir la puntuació més alta sumant tots els valors de la cinta, que poden ser uns o zeros (una màquina de Turing binària), i executar-se durant el temps més llarg es defineix com fer el nombre més llarg de passos fins aturar-se. El joc de busy beaver de n estats consisteix a trobar la màquina de Turing que funcioni més temps o que obtingui la puntuació més alta amb n estats i que finalment s'aturi. Se suposa que aquestes màquines comencen en una cinta en blanc (plena de zeros).
Una busy beaver n-èssima, també anomenat BB -n o, simplement, una busy beaver de n estats, és una màquina de Turing que guanya el joc del treballador incansable en n estats. Depenent de la definició, aquesta màquina o bé aconsegueix la puntuació més alta (denotada per Σ(n)), o bé s'executa durant el temps més llarg (S(n)), d'entre totes les altres possibles màquines de Turing que competeixen en n estats. Aquestes dues mètriques no són equivalents: maximitzar la producció de sortida no implica necessàriament maximitzar el temps d’execució, i a l’inrevés tampoc.
De fet, tant les funcions Σ(n) com S(n) acaben sent més grans que qualsevol funció computable. Això té implicacions en la teoria de la computabilitat, el problema de la parada i la teoria de la complexitat. El concepte de busy beaver va ser, de fet, introduït per primera vegada per Tibor Radó en el seu article de 1962, "Sobre funcions no computables".
Un dels aspectes més importants del joc del treballador incansable és que, si fos possible calcular les funcions Σ(n) i S(n) per a tot n, això resoldria totes les conjectures matemàtiques que es poden codificar en la forma "s'atura ?". Per exemple, hi ha una màquina de Turing de 25 estats que comprovaria la conjectura de Goldbach per a cada nombre i s'atura en un contraexemple; si aquesta màquina no s'atura després d'executar durant S(25) passos, aleshores ha d'executar-se per sempre, resolent la conjectura. Molts altres problemes, incloent-hi la hipòtesi de Riemann (744 estats) i la consistència de la teoria de conjunts ZF (745 estats), es poden expressar de forma similar, on com a màxim cal comprovar un nombre infinit numerable de casos.
Definició tècnica El joc de busy beaver amb n estats (o joc BB- n), introduït a l'article de Tibor Radó de 1962, implica una classe de màquines de Turing, cada membre de les quals ha de complir les següents especificacions de disseny:
La màquina té n estats “operacionals” més un estat d’aturada (Halt), on n és un enter positiu, i un dels n estats es distingeix com a estat inicial. Habitualment, els estats s’etiqueten amb 1, 2, …, n, amb l’estat 1 com a inicial, o bé amb A, B, C, …, amb l’estat A com a inicial. La màquina fa servir una única cinta bidireccional infinita (o no acotada). L’alfabet de la cinta és {0, 1}, on 0 fa el paper de símbol en blanc. La funció de transició de la màquina pren dos inputs: l’estat actual (no aturat), el símbol de la cel·la actual de la cinta, i produeix tres outputs: el símbol que s’ha d’escriure a la cel·la actual (pot ser el mateix que hi havia), la direcció del moviment (esquerra o dreta; és a dir, desplaçar-se a la cel·la adjacent corresponent), l’estat al qual es transita (que pot ser l’estat d’aturada). "Fer funcionar" la màquina consisteix a arrencar-la en l'estat inicial, a qualsevol cel·la d'una cinta en blanc (tot 0's), i després iterar la funció de transició fins que s'entra a l'estat de parada Halt (si és que s'hi atura). Si i només si la màquina s'atura, el nombre d'1 que finalment queden a la cinta s'anomena puntuació de la màquina. El joc busy beaver de n estats (BB- n) és, per tant, una competició, que depèn de la definició per trobar una màquina de Turing de n estats que tingui la puntuació o el temps d'execució més gran possible.
Exemple Les regles per a una màquina de Turing d'un estat podrien ser:
A l'estat 1, si el símbol actual és un 0, s'escriu un 1, es mou un espai a la dreta i es passa a l'estat 1 (ja que és l'únic que hi ha). A l'estat 1, si el símbol actual és un 1, escriviu un 0, moveu-vos un espai a la dreta i atureu-vos (HALT).
Aquesta màquina de Turing es mouria cap a la dreta, intercanviant el valor de tots els bits que passa. Com que la cinta inicial són tots zeros, crearia una cadena interminable d'uns. Aquesta màquina no seria una competidora perquè funciona per sempre amb una cinta en blanc.
De fet, la busy beaver amb un estat és aquella que té una puntuació de 1. Com seria aquesta màquina?
Funcions En l'article original de 1962, Radó va definir dues funcions relacionades amb busy beaver: la funció de puntuació Σ(n) i la funció de desplaçament S(n). Ambdues prenen màquines de Turing de -estats i generen la puntuació màxima que pot assolir una màquina de Turing d'aquest nombre d'estats segons alguna mesura. La funció de puntuació Σ(n) dóna el nombre màxim d'1s que una màquina de Turing de -estats pot generar abans d'aturar-se, mentre que la funció de desplaçament S(n) dóna el nombre màxim de desplaçaments (o equivalentment passos, perquè cada pas inclou un desplaçament) que una màquina de Turing de -estats pot experimentar abans d'aturar-se. Va demostrar-se que ambdues funcions no eren computables, perquè cadascuna creixia més ràpid que qualsevol funció computable.
També es poden definir diverses altres funcions no computables basades en la mesura del rendiment de les màquines de Turing, d'altres maneres que no siguin el temps o el nombre màxim d'uns possibles. Per exemple:
La funció es defineix com el nombre màxim d'uns contigus que una màquina de Turing de n estats que s'atura pot escriure en una cinta en blanc. En altres paraules, aquest és el nombre unari més gran que una màquina de Turing de n estats pot escriure en una cinta. La funció es defineix com el nombre màxim de quadrats de cinta que una màquina de Turing en aturada pot llegir (és a dir, visitar) abans d'aturar-se. Això inclou el quadrat inicial, però no un quadrat que la màquina només arriba després de la transició d'aturada (si la transició d'aturada està anotada amb una direcció de moviment), perquè aquest quadrat no influeix en el comportament de la màquina. Aquesta és la complexitat espacial màxima d'una màquina de Turing de n estats.
Aquestes quatre funcions juntes es troben en la relació També es poden definir més funcions fent funcionar el joc en diferents màquines informàtiques, com ara màquines de Turing de 3 símbols, màquines de Turing no deterministes, el càlcul lambda, o fins i tot llenguatges de programació arbitraris.
Funció de puntuació Σ La funció de puntuació mesura la puntuació màxima que pot assolir una busy beaver de n estats. Aquesta és una funció no computable, perquè creix asimptòticament més ràpid que qualsevol funció computable.
La funció de puntuació, , es defineix de manera que és la puntuació màxima assolible (el nombre màxim d'1s finalment a la cinta) entre totes les Màquines de Turing que s'aturen de estats.
És clar que és una funció ben definida: per a cada n, hi ha com a màxim un nombre finit de màquines de Turing de n estats com s'ha indicat anteriorment, per tant, com a màxim un nombre finit de temps d'execució possibles.
Segons la definició basada en puntuacions, qualsevol màquina de Turing M de 2 símbols i n estats per a la qual (és a dir, que aconsegueix la puntuació màxima) s'anomena busy beaver.
Per a cada n, existeixen almenys 4(n − 1)! busy beavers de n estats, per isomorfisme entre màquines. És a dir: donada qualsevol busy beaver d'n estats, se n'obté una altra simplement canviant la direcció de desplaçament en una transició d'aturada, una tercera invertint totes les direccions de desplaçament uniformement i una quarta invertint la direcció d'aturada. A més, una permutació de tots els estats excepte els de "Inici" i "Aturada", produeix una màquina que aconsegueix la mateixa puntuació. Teòricament, hi podria haver més d'un tipus de transició que condueixi a l'estat d'aturada, però a la pràctica seria un malbaratament, perquè només hi ha una seqüència de transicions d'estat que produeixen el resultat buscat)
No computabilitat L'article de Radó de 1962 va demostrar que si és qualsevol funció computable, aleshores Σ(n) > f (n) per a tot n prou gran, i per tant Σ no és una funció computable.
A més a més, això implica que és indecidible, per un algorisme general, si una màquina de Turing arbitrària és una busy beaver o no. Un algoritme d'aquest tipus no pot existir, perquè la seva existència permetria calcular Σ, cosa que és una impossibilitat demostrada. En particular, un algoritme d'aquest tipus es podria utilitzar per construir un altre algoritme que calculés Σ de la següent manera: per a qualsevol n donat, cadascuna de les finites màquines de Turing de 2 símbols de n estats es provaria fins que es trobés una busy beaver de n estats. Aquesta màquina se simularia aleshores per determinar la seva puntuació, que per definició és Σ(n).
Tot i que Σ(n) és una funció no computable, hi ha algunes n petites per a les quals és possible obtenir els seus valors i demostrar que són correctes. No és difícil demostrar que Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, i també es pot demostrar que Σ(3) = 6, Σ(4) = 13, i que Σ(5) 4098.
El 2 de juliol de 2024, un grup de matemàtics aficionats van afirmar haver descobert que Σ(5) = 47.176.870. La prova, dissenyada en Coq (un assistent per realitzar demostracions matemàtiques), va ocupar més de 18000 línies de codi, amb un fitxer separat de 6800 línies amb la prova de la màquina concreta que és busy beaver.
Complexitat i indemostrabilitat de Σ Una variant de la complexitat de Kolmogorov es defineix de la següent manera: La complexitat d'un nombre n és el nombre més petit d'estats necessaris per a una màquina de Turing Busy Beaver que s'atura amb un sol bloc de n 1's consecutius en una cinta inicialment en blanc. La variant corresponent del teorema d'incompletesa de Chaitin estableix que, en el context d'un sistema axiomàtic donat per als nombres naturals, existeix un nombre k tal que no es pot demostrar que cap nombre específic tingui una complexitat més gran que k, i per tant que no es pot demostrar cap límit superior específic per a Σ(k) (això últim és perquè "la complexitat de n és més gran que k" es demostraria si es demostrés ). Com s'esmenta a la referència citada, per a qualsevol sistema axiomàtic de "matemàtiques ordinàries", el valor mínim k per al qual això és cert és molt menor que 10⇈10; en conseqüència, en el context de les matemàtiques ordinàries, no es pot demostrar ni el valor ni cap límit superior de Σ(10⇈10). De fet, el primer teorema d'incompletesa de Gödel s'il·lustra amb aquest resultat: en un sistema axiomàtic de matemàtiques ordinàries, hi ha una oració vertadera però indemostrable de la forma , i hi ha infinites oracions vertaderes però indemostrables de la forma .