¿Qué son programas muy cortos con un estado de detención desconocido?

32

Este programa de 579 bits en el cálculo binario de Lambda tiene un estado de detención desconocido:

01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010

Es decir, no se sabe si este programa finaliza o no. Para determinarlo, debes resolver la conjetura de Collatz , o, al menos, para todos los números hasta 2 ^ 256. En este repositorio hay una explicación completa de cómo se obtuvo este programa.

¿Hay (mucho) programas BLC más cortos que también tienen un estado de detención desconocido?

MaiaVictor
fuente
66
Pregunta muy relacionada . Votos de la comunidad, por favor: ¿duplicado?
Raphael
99
La tarea de expresar un programa de este tipo en tan pocos bits como sea posible parece ser un problemas de Código de golf , por lo menos equipo ciencia .
Raphael
2
Creo que la respuesta de Ricky sobre las TM de 5 estados es mejor que la de la pregunta original. Si este está cerrado como un engañado, ¿se puede mover la respuesta?
David Richerby
66
Le falta un detalle clave: no ha especificado en qué idioma debe escribirse el programa. Su ejemplo utiliza cálculo lambda binario. ¿Es ese el único idioma que le interesa? Podemos ver que es trivial desarrollar un programa de 1 bit que tenga un estado de detención desconocido, simplemente integrando el cuerpo del algoritmo directamente en el lenguaje mismo. Es una escapatoria, pero a la que debe prestar atención cuando solicite soluciones de golf. ¡ Aman sus lagunas! La complejidad de Kolmogov puede ser un tema importante para explorar aquí.
Cort Ammon - Restablece a Monica el

Respuestas:

30

Sí. Esta página dice que hay 98 5-estatales máquinas de Turing , cuyos estados de detención son desconocidos. Molesto, no da ningún ejemplo de tales máquinas, pero esta página de 26 años da 2 máquinas Turing de 5 estados cuyos estados de detención aparentemente eran desconocidos en ese momento. (La búsqueda de "contador simple" lo llevará directamente entre esos 2.) Los copié aquí en caso de que el enlace se caiga:

Input Bit   Transition on State     Steps            Comment
             A   B   C   D   E

    0       B1L C1R D0R A1L H1L   > 2*(10^9)       ``chaotic''
    1       B1R E0L A0L D0R C0L

    0       B1L A0R C0R E1L B0L       ?        complex ``counter''
    1       A1R C0L D1L A0R H1L

fuente
La parte inferior de la página dice: $ Fecha: 2007/11/03, entonces, ¿cómo tiene 26 años?
Falaque
1
@Falaque La parte superior de la página dice "Esta página es la reescritura HTML del autor de ... febrero de 1990". El texto tiene 26 años, la versión en HTML es de (o última actualización) en 2007.
IMSoP
5

Conjetura de Collatz:

El siguiente programa siempre se detiene:

void function( ArbitraryInteger input){
     while( input > 1){
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }

     // Halt here
}

Ligera variación (sigue siendo una conjetura, porque se basa en un resultado del de Collatz):

Para alguna entrada, el siguiente programa nunca entrará en el mismo estado dos veces (donde el estado está determinado por el valor contenido en "entrada"):

void function( ArbitraryInteger input){
     while( input >= 1){ // notice the "="
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }
}

Tenga en cuenta que el segundo programa nunca se detiene, independientemente de si el primer programa se detiene o no.

Se cree que el primer programa siempre termina para cualquier entrada, sin embargo, no tenemos la prueba de eso, y aún puede existir algún número entero para el que el programa no se detenga (también hay un premio de $ 100 por probarlo) .

El segundo programa también es interesante: establece que el programa nunca entrará en el mismo estado dos veces para alguna entrada, lo que básicamente requiere que el primer programa tenga una secuencia conocida que diverge sin repetirse. No solo requiere que la conjetura de Collatz sea falsa, sino que también es falsa y sin bucles , aparte del obvio bucle 1,4,2,1.

  • Si Collatz solo tiene contraejemplos en bucle, la variación de la conjetura es falsa

  • Si Collatz es falso sin bucles, la variación de la conjetura es verdadera

  • Si Collatz es verdadero, la variación es falsa

  • Si Collatz es falso tanto porque tiene bucles como porque tiene un número para el cual diverge, la variación de la conjetura es verdadera (solo requiere un número para el cual diverge sin ingresar un bucle)

Creo que la variación es más interesante (no solo porque la encontré por accidente y la noté gracias a @LieuweVinkhuijzen), sino porque en realidad requiere una prueba real. Por fuerza bruta, podemos encontrar un bucle un día u otro (y ese será un bucle de más de 70 números: el estado actual de la técnica es que no puede haber bucles infinitos más cortos que 68), y bruto forzar no es interesante: es solo un cálculo numérico. Sin embargo, no podemos forzar con fuerza bruta una secuencia divergente infinita, no sabemos si realmente terminará sin una prueba real.

EDITAR: me salteé la parte sobre la conjetura de Collatz, lo siento, realmente respondí de memoria con un algoritmo que leí hace unos años, no esperaba que ya se mencionara.

EDIT2: Un comentario me hizo notar que escribí el algoritmo con un error, sin embargo, ese error realmente hace que mi respuesta sea diferente de la conjetura de Collatz (pero una variación directa del mismo).

Desarrollador de juegos
fuente
1
Creo que quieres escribir en input > 1lugar de input >= 1? Tal como está ahora, este programa repetirá1421
Lieuwe Vinkhuijzen
Tienes razón, quería poner un >, sin embargo, siempre y cuando no tengamos una prueba para detenernos, >no podemos estar seguros de que llegaremos al 1 -> 4 -> 2 -> 1bucle (por ejemplo, si no termina por >eso, no lo hagas ) t reach >=)
GameDeveloper
1
Una prueba de que su programa con no se detiene: suponga que la conjetura de Collatz es verdadera, entonces llegamos al bucle en todas las entradas. De lo contrario, si es falso, entonces alcanzamos el bucle en algunas entradas, y en otras entradas la secuencia se repite en otro lugar o diverge en el infinito (y por lo tanto se repite para siempre). En cualquier escenario, el programa con nunca se detiene, independientemente de si la conjetura de Collatz es verdadera o no. El programa con detiene en todas las entradas si la conjetura de Collatz es verdadera, lo cual no está resuelto. 1421 1421 > = >>=14211421>=>
Lieuwe Vinkhuijzen
2
n<1n=1n4n>1n11
1
Eso es cierto :) Tienes razón, debería haber agregado 'si la conjetura de Collatz es verdadera' a mi primer comentario. Veo tu edición, muy bien. No necesita el segundo programa, porque la conjetura 'este programa nunca ingresa al mismo estado dos veces' tampoco está resuelta del primer programa: es posible que haya un número que no se separe en el infinito, sino que se atasque en un bucle grande en algún lugar en números muy altos.
Lieuwe Vinkhuijzen