Busy beaver

Este "diagrama espai-temps" mostra l'estat de la cinta de memòria en una fila per als primers 100 000 passos de temps del castor ocupat de 5 estats, de dalt a avall. El taronja és "1", el blanc és "0" (image comprimida verticalment)

En ciència computacional teòrica, el joc del castor ocupat (nom original en anglés: busy beaver) busca obtindre un programa d'un tamany donat, que (segons la definició) produïxca la major cantitat d'eixida possible o s'eixecute durant el major número de passos abans de detindre's. Ya que és fàcil concebre un programa en bucle infinit que produïxca una eixida infinita o s'eixecute durant un temps infinit, dits programes s'exclouen del joc. En lloc de llenguages de programació tradicionals, els programes utilisats en el joc són màquines de Turing de n estats, un dels primers models de computació matemàtics.

Les màquines de Turing consistixen en una cinta infinita i un conjunt finit d'estats que servixen com el "còdic font" del programa. Produir la major cantitat de senyes es definix com escriure la major cantitat d'uns en la cinta, també conegut com obtindre la puntuació més alta, i eixecutar durant el major temps es definix com prendre la major cantitat de passos per a detindre's. El joc del castor ocupat de n estats consistix en trobar la màquina de Turing de n estats que eixecute n estats i finalment es detinga. Se supon que dites màquines comencen en una cinta en blanc, i se supon que la cinta conté solament zeros i uns (una màquina de Turing binaria). L'objectiu del joc és programar un conjunt de transicions entre estats buscant la puntuació més alta o el temps d'eixecució més llarc, assegurant-se de que la màquina es detinga finalment.

Decidir el temps d'eixecució o la puntuació del n-simo castor ocupat no és computable. De fet, tant les funcions Σ(n) com a S(n) finalment es tornen majors que qualsevol funció computable. Açò té implicacions en teoria de la computabilidad, en el problema de la parada i en la teoria de la complexitat computacional. El concepte de castor ocupat va ser introduït per primera volta per Tibor Radó en el seu artícul de 1962, "Sobre funcions no computables".

Una implicació del joc del castor ocupat és que, si fora possible calcular les funcions Σ(n) i S(n) para tot n, llavors açò resoldria totes les conjectura matemàtiques que poden ser reduïdes a un problema de parada, per eixemple, en una forma de "¿es deté ⟨esta màquina de Turing⟩?". Per eixemple, existix una màquina de Turing de 27 estats que verifica la conjectura de Goldbach per a cada número i es deté davant un contraeixemple; si esta màquina no es detinguera despuix d'eixecutar-se durant S(27) passos, llavors deu eixecutar-se indefinidament, resolent aixina la conjectura. Molts atres problemes, incloent l'hipòtesis de Riemann (744 estats) i la consistència de la teoria de conjunts de Zermelo-Fraenkel (745 estats), poden expressar-se de forma similar, a on com a màxim es deuen verificar infinits casos numerables.

Definició tècnica

El joc del castor ocupat de n estats (o joc BB-n), introduït en l'artícul de Tibor Radó de 1962, involucra una classe de màquines de Turing, cada una de les quals deu complir en les següents especificacions de disseny:

L'eixecució de la màquina consistix en escomençar en l'estat inicial, en la cela actual de la cinta sent qualsevol cela d'una cinta en blanc (totes les posicions zero), i despuix iterar la funció de transició fins que s'alcance l'estat de parada (si és que s'alcança). Si i solament si la màquina finalment es deté, el número d'uns que queden en la cinta es denomina la puntuació de la màquina. Un castor ocupat de n estats, BB-n o simplement "castor ocupat", és una màquina de Turing que guanya el joc del castor ocupat de n estats. Segons la definició, obté la puntuació més alta (denotada per Σ(n)) o s'eixecuta durant el major temps (S(n)), entre totes les possibles màquines de Turing de n estats.

Eixemple

Les regles per a una màquina de Turing d'1 estat podrien ser:

• En l'estat 1, si el símbol actual és 0, escriu un 1, alvança un espai a la dreta i torna a l'estat 1.
• En l'estat 1, si el símbol actual és 1, escriu un 0, alvança un espai a la dreta i es deté.

Esta màquina de Turing es desplaçaria cap a la dreta, intercanviant el valor de tots els bits que recorre. Ya que la cinta inicial està composta solament per zeros, generaria una cadena infinita d'uns. Esta màquina no seria una màquina de Turing competitiva perque s'eixecuta indefinidament en una cinta en blanc.

Funcions

En el seu artícul original de 1962, Radó va definir dos funcions relacionades en el joc del castor ocupat: la funció de puntuació Σ(n) i la funció de desplaçaments S(n). Abdós prenen un número d'estats de la màquina de Turing $n$ i produïxen la puntuació màxima alcanzable per una màquina de Turing en eixe número d'estats, segons alguna mida. La funció de puntuació Σ(n) proporciona el número màxim d'uns que una màquina de Turing en $n$ estats pot produir abans de detindre's, mentres que la funció de desplaçaments S(n) proporciona el número màxim de desplaçaments (o, equivalentemente, passos, ya que cada pas inclou un desplaçament) que una màquina de Turing en $n$ estats pot realisar abans de detindre's. Va demostrar que abdós funcions no eren computables, perque cada una creixia més ràpit que qualsevol funció computable. La funció BB(n) s'ha definit com qualsevol d'estes funcions, per lo que eixa notació no s'utilisa en este artícul.

També es poden definir atres funcions incomputables medint el rendiment de les màquines de Turing de maneres distintes al temps o al número màxim d'uns: Per eixemple:

• La funció $\text{num}(n)$ es definix com el número màxim d'uns contigus que una màquina de Turing que es deté pot escriure en una cinta en blanc. En atres paraules, est és el major unary number que una màquina de Turing de n estats pot escriure en una cinta.
• La funció $\text{espacio}(n)$ es definix com el número màxim de caselles de cinta que una màquina de Turing que es deté pot «llegir» (és dir, visitar) abans de detindre's. Açò inclou la casella inicial, pero no una casella a la que la màquina solament aplega despuix de la transició de parada (si la transició de parada està anotada en una direcció de moviment), ya que eixa casella no influïx en el comportament de la màquina. Est és el valor màxim de complexitat espacial d'una màquina de Turing de «n» estats.

Estes quatre funcions juntes es troben en la relació $\text{num}(n)\le \Sigma (n)\le \text{espacio}(n)\le S(n)$. També es poden definir més funcions eixecutant el joc en diferents màquines de computació, com a màquines de Turing de 3 símbols, màquines de Turing no determinista, càlcul lambda A333479 o inclús llenguages de programació arbitraris.

Funció de puntuació Σ

La funció de puntuació quantifica la puntuació màxima que pot alcançar un castor ocupat d'un tamany donat. Esta és una funció no computable, perque creix asintóticamente més ràpit que qualsevol funció computable.

La funció de puntuació, $\Sigma :\mathbb{N}\to \mathbb{N}$, es definix de modo que $\Sigma (n)$ siga la puntuació màxima alcanzable (el número màxim d'uns que finalment apareixen en la cinta) entre totes les màquines de Turing de dos símbols i dos estats $n$ del tipo descrit anteriorment, que es detenen en iniciar-se en una cinta en blanc.

És evident que $\Sigma$ és una funció ben definida: per a cada n, existixen com a màxim un número finit de màquines de Turing de n estats com les anteriors, llevat isomorfismes, i per lo tant, com a màxim un número finit de temps d'eixecució possibles.^p. 880

Segons la definició basada en la puntuació, qualsevol màquina de Turing M de dos símbols i dos estats que alcance la puntuació màxima (σ(M)= Σ(n)) es denomina "busy beaver" (castor ocupat). Per a cada n, existixen a lo manco 4(n − 1)! castors ocupats de n estats.

Donat qualsevol castor ocupat de n estats, s'obté un atre simplement canviant la direcció de desplaçament en una transició de parada, un tercer invertint uniformemente totes les direccions de desplaçament, i un quarto invertint la direcció de parada del castor ocupat en totes les direccions intercanviades. Ademés, una permutació de tots els estats llevat Inici i Parada produïx una màquina que alcança la mateixa puntuació. Teòricament, podria haver més d'un tipo de transició que conduïxca a l'estat de parada, pero en la pràctica seria un desperdici, ya que solament hi ha una seqüència de transicions d'estat que produïx el resultat desijat.

No computabilidad

L'artícul de Radó de 1962 va demostrar que si $f:\mathbb{N}\to \mathbb{N}$ és qualsevol funció computable, llavors Σ(n) > f(n) para tot n suficientment gran, i per lo tant, que Σ no és una funció computable.

Ademés, açò implica que és un problema indecidible per mig d'un algoritme general si una màquina de Turing arbitrària és un castor ocupat. Tal algoritme no pot existir, ya que la seua existència permetria calcular Σ, lo que és una impossibilitat demostrada. En particular, dit algoritme podria usar-se per a construir un atre algoritme que calcularia Σ de la següent manera: per a qualsevol n donat, es provarien totes les màquines de Turing de 2 símbols i n estats fins a trobar una màquina de Turing de n estats; esta màquina se simularia per a determinar la seua puntuació, que per definició és Σ(n).

Encara que Σ(n) és una funció incomputable, existixen alguns valors chicotets de n per als quals és possible obtindre els seus valors i demostrar la seua correcció. No és difícil demostrar que Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, i en creixent dificultat es pot demostrar que Σ(3) = 6, Σ(4) = 13 i Σ(5) = 4098 A028444. Encara no s'ha determinat Σ(n) per a cap cas de n > 5, encara que s'han establit llímits inferiors (vore la secció valores coneguts més alvance).

Complexitat i impossibilitat de demostrar Σ

Una variant de la complexitat de Kolmogórov es definix de la següent manera: la complexitat d'un número n és el número més chicotet d'estats necessaris per a una màquina de Turing de classe BB que es deté en un sol bloc de n 1s consecutius en una cinta inicialment en blanc. La variant corresponent de la complexitat de Kolmogórov establix que, en el context d'un sistema axiomàtic donat per als número natural, existix un número k tal que no es pot provar que cap número específic tinga una complexitat major que k, i per lo tant que no es pot provar cap llímit superior específic para Σ(k) (açò últim es deu a que "la complexitat de n és major que k" es provaria si es provara que n > Σ(k). Com es menciona en la referència citada, per a qualsevol sistema axiomàtic de matemàtiques ordinàries, el valor més chicotet k per al qual açò és cert és molt menor que 10⇈10. En conseqüència, en el context de les matemàtiques ordinàries, ni el valor ni cap llímit superior de Σ(10⇈10) poden demostrar-se.

El teorema de incompletitud de Gödel s'ilustra en este resultat: en un sistema axiomàtic de matemàtiques ordinàries, existix una proposició verdadera pero indemostrable de la forma Σ(10⇈10)= n, i infinites proposicions verdaderes pero indemostrables de la forma Σ(10⇈10) < n.

Funció del màxim número de desplaçaments S

Ademés de la funció Σ, Radó [1962] va introduir una atra funció extrema per a les màquines de Turing, la funció del màxim número de desplaçaments, S, definida de la següent manera:

• s(M) = el número de desplaçaments que M realisa abans de detindre's, per a qualsevol M ∈ I_n,

• S(n)= maxPlantilla:Mset = el major número de desplaçaments realisats per qualsevol màquina de Turing de 2 símbols i n estats que es deté. Ya que les màquines de Turing normals requerixen un desplaçament en cada transició o "pas" (inclosa qualsevol transició a un estat de parada), la funció de desplaçaments màxims és, a la seua volta, una funció del màxim de passos.

Radó va demostrar que S no és computable per la mateixa raó que Σ no ho és: creix més ràpit que qualsevol funció computable. Ho va demostrar simplement observant que, per a cada n, S(n) ≥ Σ(n). Cada desplaçament pot escriure un 0 o un 1 en la cinta, mentres que Σ conta un subconjunt dels desplaçaments que varen escriure un 1, és dir, aquells que no havien segut sobrescritos quan la màquina de Turing es va detindre; per tant, S creix a lo manco tan ràpit com Σ, que ya s'havia demostrat que creixia més ràpit que qualsevol funció computable.

Lin i Radó varen utilisar la següent relació entre Σ i S (Estudis Computacionals de Problemes de Màquines de Turing, 1965) per a demostrar que Σ(3) = 6 i que S(3) = 21: Per a un n donat, si es coneix S(n), llavors totes les màquines de Turing de n estats poden (en principi) eixecutar-se fins a S(n) passos, moment en el qual qualsevol màquina que encara no s'haja detingut mai es detindrà. En eixe punt, en observar qué màquines s'han detingut en la major cantitat de 1s en la cinta (és dir, les màquines més actives), s'obté de les seues cintes el valor de Σ(n). L'enfocament utilisat per Lin i Radó per al cas de n = 3 va ser conjeturar que S(3) = 21 (despuix de conjeturar sense èxit 18), i despuix simular totes les màquines de 3 estats essencialment diferents (82.944 màquines, equivalents a 2Plantilla:Sup3Plantilla:Sup) fins a 21 passos. Varen trobar 26.073 màquines que es varen detindre, incloent una que es va detindre solament despuix de 21 passos. En analisar el comportament de les màquines que no es varen detindre dins dels 21 passos, varen conseguir demostrar que cap d'eixes màquines es detindria jamai, i la majoria d'elles seguien un patró determinat. Açò va demostrar la conjectura de que S(3) = 21, i també va determinar que Σ(3) = 6, valor que varen alcançar vàries màquines, totes detenint-se despuix d'11 a 14 passos.

En 2016, Adam Yedidia i Scott Aaronson varen obtindre la primera cota superior (explícita) sobre el mínim n per al qual S(n) és indemostrable en el conjunt de Zermelo-Fraenkel. Per a això varen construir una màquina de Turing de 7910 estats el comportament dels quals no pot provar-se basant-se en els axioma usuals de la teoria de conjunts (els axioma de Zermelo-Fraenkel en l'axioma d'elecció), baix hipòtesis de consistència raonables (propietat de Ramsey estacionaria, equivalent a l'existència de moradures sotils arbitrariamente grans). Stefan O'Rear despuix la va reduir a 1919 estats, en la dependència de la propietat de Ramsey estacionaria eliminada, i més vesprada a 748 estats. En juliol de 2023, Riebel ho va reduir a 745 estats. S'informen millores adicionals en el lloc web del BB Challenge [1].

Prova de la incomputabilidad de S(n) i Σ(n)

Suponga's que S(n) és una funció computable i siga EvalS una màquina de Turing que evalua S(n). Donada una cinta en n uns, produirà S(n) uns en la cinta i despuix es detindrà. Siga Clean una màquina de Turing que neteja la seqüència d'uns escrita inicialment en la cinta. Siga Double una màquina de Turing que evalua la funció n + n. Donada una cinta en n uns, produirà 2n uns en la cinta i despuix es detindrà.

Siguen les opcions disponibles Double | EvalS | Clean, i siga n₀ el número d'estats d'esta màquina. Siga Create_n₀ una màquina de Turing que crea n₀ uns en una cinta inicialment en blanc. Esta màquina pot construir-se de manera trivial per a tindre n₀ estats (l'estat i escriu 1, mou el cabezal a la dreta i canvia a l'estat i + 1, llevat l'estat n₀, que es deté). Siga N la suma n₀ + n₀.

Siga BadS la composició Create_n₀ | Double | EvalS | Clean. Note's que esta màquina té N estats. Partint d'una cinta inicialment en blanc, primer crea una seqüència de n₀ uns i despuix la duplica, produint una seqüència de N uns. A continuació, EvalS produirà S(N) uns en la cinta, i finalment borrarà tots els uns i es detindrà. Pero la fase de neteja continuarà a lo manco S(N) passos, per lo que el temps de funcionament de BadS és estrictament major que S(N), lo que contradiu la definició de la funció S(n).

L'impossibilitat de calcular Σ(n) pot demostrar-se de forma similar. En la demostració anterior, es deu intercanviar la màquina "EvalS" per "EvalΣ" i "Clean" per "Increment", una màquina de Turing simple que busca el primer 0 en la cinta i ho reemplaça per un 1.

La incomputabilidad de S(n) també es pot establir fent referència al problema de la parada en la cinta buida. Este problema consistix en decidir, per a qualsevol màquina de Turing, si es detindrà o no en escomençar en una cinta buida. El problema de la parada en una cinta buida és equivalent al problema de la parada estàndar i, per lo tant, també és incomputable. Si S(n) fora computable, es podria resoldre el problema de la parada en la cinta buida simplement eixecutant qualsevol màquina de Turing en n estats durant S(n) passos; si encara no s'ha detingut, mai ho farà. Per lo tant, ya que el problema de la parada en una cinta buida no és computable, es deduïx que S(n) també deu ser incomputable.

Incomputabilidad d'espai(n) i num(n)

Tant les funcions $\text{espacio}(n)$ com $\text{num}(n)$ són incomputables. Açò es pot demostrar per a $\text{espacio}(n)$ observant que cada casella de cinta en la que una màquina de Turing escriu un un, també deu visitar-la; en atres paraules, $\Sigma (n)\le \text{espacio}(n)$. Es pot demostrar que la funció $\text{num}(n)$ és incomputable provant, per eixemple, que $\text{espacio}(n)<\text{num}(3n+3)$: açò es pot fer dissenyant una màquina de Turing de (3n+3) estats que simule el campeó de l'espai de n estats i despuix l'use per a escriure a lo manco $\text{espacio}(n)$ uns contigus en la cinta.

Vore també

• Número de Raig
• Turmite

Bibliografia

• Radó, Tibor(més de maig de 1962).«On senar-computable functions».Bell System Technical Journal.41(3): 877–884.doi:10.1002/j.1538-7305.1962.tb00480.x.Consultat el 7 de juliol de 2022.

  Ací Radó va definir per primera volta el problema del castor ocupat i va demostrar que era incomputable i que creixia més ràpit que qualsevol funció computable.

• Lin, Shen; Radó, Tibor(més d'abril de 1965).«Computer Studies of Turing Machine Problems».Journal of the ACM.12(2): 196–212.doi:10.1145/321264.321270.

• Els resultats d'este artícul ya havien aparegut parcialment en la tesis doctoral de Lin de 1963, baix la direcció de Radó. Lin i Radó demostren que S(3) = 6 i S(3) = 21 en provar que totes les màquines de Turing de 3 estats i 2 símbols que no es detenen en 21 passos mai es detindran. (La majoria es demostren automàticament per mig d'un programa informàtic; no obstant, 40 es demostren per mig d'inspecció humana).

• Brady, Allen H.(més d'abril de 1983).«The determination of the value of Rado's noncomputable function Σ(k) for four-state Turing machines».Mathematics of Computation.40(162): 647–665.doi:10.1090/S0025-5718-1983-0689479-6.

  Brady demostra que S(4) = 13 i S(4) = 107. Brady definix dos noves categories per a màquines de Turing de 3 estats i 2 símbols que no es detenen: arbres de Nadal i contadors. Utilisa un programa informàtic per a demostrar que totes les màquines, llevat 27 que s'eixecuten durant més de 107 passos, són variants d'arbres de Nadal i contadors, i es pot demostrar que s'eixecuten infinitament. Les últimes 27 màquines (denominades "rebujades") es demostren per mig d'inspecció personal pel propi Brady que no es detenen.

• Machlin, Rona; Stout, Quentin F.(més de juny de 1990).«The complex behavior of simple machines».Physica D: Nonlinear Phenomena.42(1–3): 85–98.doi:10.1016/0167-2789(90)90068-Z.Consultat el 7 de juliol de 2022.

  Machlin i Stout descriuen el problema del castor ocupat i moltes tècniques utilisades per a trobar castors ocupats (que apliquen a màquines de Turing de 4 estats i 2 símbols, verificant aixina la demostració de Brady). Sugerixen cóm estimar una variant de la provabilitat de parada de Chaitin (O).

• Marxen, Heiner; Buntrock, Jürgen(més de febrer de 1990).«Attacking the Busy Beaver 5».Bulletin of the EATCS.40: 247–251.Consultat el 19 de giner de 2020.

  Marxen i Buntrock demostren que S(5) = 4098 i S(5) = 47 176 870 i descriuen en detalle el método que varen utilisar per a trobar estes màquines i provar que moltes unes atres mai es detindran.

• Green, Milton W. (1964). «A lower bound RADO's sigma function for binary turing machines», 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 91–94. doi:10.1109/SWCT.1964.3. Consultat el 7 de juliol de 2022.

  Green construïx recursivamente màquines per a qualsevol número d'estats i proporciona la funció recursiva que calcula la seua puntuació (calcula s), proporcionant aixina una cota inferior per a S. El creiximent d'esta funció és comparable al de Funció de Ackermann.

• Dewdney, Alexander K.(1984).«A computer trap for the busy beaver, the hardest working Turing machine».Scientific American.251(2): 10–17.

  Els programes del castor ocupat es descriuen en Alexander Dewdney en «Scientific American», agost de 1984, pàgines 19-23, també en març de 1985, pág. 23 i abril de 1985, pág. 30.

• Chaitin, Gregory J. (1987). «Computing the Busy Beaver Function», Open Problems in Communication and Computation, Springer, pp. 108–112. ISBN 978-0-387-96621-2. Consultat el 7 de juliol de 2022.
• Brady, Allen H. (1995). «The Busy Beaver Game and the Meaning of Life», The Universal Turing Machine: A Half-Century Survey, 2nd edició, Wien, New York: Springer-Verlag, pp. 237–254. ISBN 978-3-211-82637-9.

  En este artícul, Brady (conegut per la seua trayectòria en quatre estats) descriu part de l'història d'este fenomen i denomina a la seua busca «El joc del castor ocupat». Descriu atres jocs (per eixemple, autómata celular i Joc de la vida). De particular interés és «El joc del castor ocupat en dos dimensions» (pág. 247). En 19 referències.

• Booth, Taylor L. (1967). Sequential Machines and Automata Theory, New York: Wiley. ISBN 978-0-471-08848-6.

  Vore el Capítul 9, Màquines de Turing. Un llibre complex, dirigit a ingeniers elèctrics i tècnics especialisats. Tracta sobre recursión, recursión parcial en referència a les màquines de Turing i el problema de la parada. Una referència en Booth atribuïx el problema del castor ocupat a Rado. Booth també definix el problema del castor ocupat de Rado en els "problemes bàsics" 3, 4, 5 i 6 del Capítul 9, pág. 396. El problema 3 consistix en "demostrar que el problema del castor ocupat és irresoluble... per a tots els valors de n".

• Ben-Amram, A. M.; Petersen, H.(2002).«Improved Bounds for Functions Related to Busy Beavers».Theory of Computing Systems.35: 1–11.doi:10.1007/s00224-001-1052-0.«citeseerx: 10.1.1.136.5997»

  Llímits millorats.

• Este artícul conté una classificació completa de les màquines de Turing de 2 estats i 3 símbols, i per lo tant, una demostració per al castor ocupat (2, 3): S(2, 3) = 9 i S(2, 3) = 38.

• Boolos, George S.; Burgess, John P.; Jeffrey, Richard C. (2007). Computability and Logic, Fifth edició, Cambridge University Press. ISBN 978-0-521-87752-7.
• Kropitz, Pavel(2010).«Problém Busy Beaver».Charles University in Prague.(en sk)

  Es descriuen les idees, els algoritmes i la seua implementació, junt en la descripció dels experiments que examinen les màquines de Turing de 5 i 6 estats per mig d'eixecució paralela en una computadora de 31 núcleus i, finalment, els millors resultats per a la màquina de Turing de 6 estats.