¿Qué tamaño debe tener $S(5)$ ser al menos , si no lo es $47,176,870\ $ ?

Question

Consulte aquí :

https://en.wikipedia.org/wiki/Busy_beaver

para más detalles sobre la función de desplazamiento máximo

Se dice que alrededor de $40$ máquinas con $5$ estados tienen estado desconocido (no se sabe si acaban deteniéndose o no).

Estoy bastante seguro de que esas máquinas se han simulado y funcionado durante mucho tiempo.

¿Existe alguna referencia que indique, al menos de forma aproximada, cuántos pasos dan las máquinas?

En otras palabras :

Si $S(5)>47,176,870\ $ es válida, ¿cuál es el límite inferior de $S(5)$ ?

Answer 1

Creo que te refieres al análisis de Georgiev de las máquinas de Turing de 5 estados; escribió un programa que era capaz de resolver el comportamiento de parada de todas las máquinas de Turing de 5 estados excepto 164, y luego redujo ese número a 42 con un análisis individual.

El usuario Ikosarakt1 de Googology Wiki ejecutó cada una de esas 42 máquinas durante 10.000 millones de pasos, y ninguna de ellas se detuvo, por lo que presumiblemente podríamos concluir que o bien S(5) = 47.176.870 o bien es más de 10.000 millones. (Véase aquí .)

Un par de advertencias: Según Daniel Briggs, Georgiev etiquetó mal una de las 164 máquinas y en realidad debería haber 43 máquinas sin resolver. Así que tendríamos que evaluar la máquina 43 durante 10.000 millones de pasos para hacer la afirmación anterior. Además, parece que el trabajo de Georgiev no ha sido verificado, así que quizá deberíamos tomarnos con cautela la afirmación de que todas las máquinas de Turing de 5 estados excepto 42/43 han sido resueltas hasta que se produzca una verificación independiente.

Answer 2

Me entristece responder negativamente a su pregunta: no he podido encontrar ninguna descripción de las TM "retenidas", es decir, aquellas de las que no sabemos si llegaron a detenerse.

Por lo que sé, la gente se limita a publicar sus campeones Busy Beaver, pero poco más.

Por ejemplo Sitio web de Heiner Marxen da muchas TMs de larga duración que se detienen.

He encontrado un artículo que se queja de ese estado de cosas, aunque : https://arxiv.org/abs/1602.03228 presupuesto:

"Si bien no hay razón alguna para dudar de la veracidad o sinceridad de estos resultados y otros similares en la literatura, no parece científico aceptar tales resultados como probados en ausencia de pruebas matemáticas y empíricas. pruebas matemáticas y empíricas que puedan inspeccionarse, evaluarse y comprobarse. [...] Estas pruebas deberían incluir no sólo los programas utilizados para la búsqueda, sino también la lista de máquinas generadas, así como las pruebas utilizadas para extraer conclusiones sobre su estado."

Sobre tu comentario/edición, efectivamente si hipotéticamente cualquier TM holdout finalmente se detiene, eso no nos dice nada acerca de $\Sigma(5)$ porque el número de unos en la cinta no crece necesariamente con el número de pasos. Así que el siguiente $S(5)$ campeón podría haber $4099$ , $Ackerman[5,2]$ o $3$ los de la cinta, por lo que sé.