¿Se detiene esta máquina Foo?

43

Es bien sabido que determinar si una máquina de Turing se detiene es indecidible, pero eso no es necesariamente cierto para máquinas más simples.

Una máquina Foo es una máquina con una cinta finita, donde cada celda de la cinta tiene un número entero o el símbolo de detención h, p. Ej.

2 h 1 -1

El puntero de instrucciones comienza apuntando a la primera celda:

2 h 1 -1
^

En cada paso, el puntero de instrucciones avanza por el número al que apunta, y luego niega ese número. Entonces, después de un paso, movería las 2celdas hacia adelante y las convertiría 2en -2:

-2 h 1 -1
     ^

La máquina Foo sigue haciendo esto hasta que el puntero de instrucción apunta al símbolo de detención ( h). Entonces, aquí está la ejecución completa de este programa:

2 h 1 -1
^

-2 h 1 -1
     ^

-2 h -1 -1
         ^

-2 h -1 1
      ^

-2 h 1 1
   ^

La cinta también es circular, por lo que si el puntero de instrucciones se mueve de un lado de la cinta, va al otro lado, por ejemplo:

3 h 1 3
^
-3 h 1 3
       ^
-3 h 1 -3
     ^
-3 h -1 -3
         ^
-3 h -1 3
 ^
3 h -1 3
  ^

Una cosa interesante acerca de estas máquinas Foo es que algunas no se detienen, por ejemplo:

1 2 h 2
^
-1 2 h 2
   ^
-1 -2 h 2
        ^
-1 -2 h -2
    ^
-1 2 h -2
        ^
-1 2 h 2
   ^

Este programa continuará girando en esos últimos cuatro estados para siempre.

Por lo tanto, escriba un programa que determine si una máquina Foo se detiene o no. Puede usar cualquier formato de entrada (razonable) que desee para las máquinas Foo, y puede elegir usar0 como símbolo de detención. Puede usar dos salidas distintas para el caso en que se detiene y el caso en que no. Su programa debe, por supuesto, generar una respuesta en un tiempo finito para todas las entradas válidas.

Esto es , ¡así que trate de hacer su programa lo más corto posible!

Casos de prueba

2 h 1 -1
Halts
3 h 1 3
Halts
h
Halts
1 1 1 1 h
Halts
2 1 3 2 1 2 h
Halts
3 2 1 1 4 h
Halts
1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36
Halts

2 h
Does not halt
1 2 h 2
Does not halt
8 1 2 3 3 4 8 4 3 2 h
Does not halt
1 2 4 3 h 2 4 5 3
Does not halt
3 1 h 3 1 1
Does not halt
1 2 h 42
Does not halt
Leo Tenenbaum
fuente
55
Solo estoy seguro, sobre el algoritmo para resolver esto. No soy un maestro de algoritmos, así que prefiero preguntar antes de ir en la dirección equivocada. ¿Una máquina Foo que no se detiene siempre volverá a su estado original exacto? ¿O hay máquinas que no se detienen con "comportamiento caótico"?
V. Courtois
55
@ V.Courtois Todas las máquinas Foo que no se detienen terminarán en un bucle de estados, porque solo hay muchos estados posibles en los que puede estar una máquina Foo (hay n lugares posibles donde puede estar el puntero de instrucción, y 2 ^ n posibles configuraciones de cinta). Cada estado tiene uno y solo un "estado siguiente". Por lo tanto, si una máquina Foo termina en un estado en el que ya ha estado, seguirá funcionando. Debido a que solo hay muchos estados, no puede seguir caóticamente saltando entre estados porque finalmente terminará yendo a uno en el que ya ha estado.
Leo Tenenbaum
3
Caso de prueba sugerido: 1 2 h 42(no se detiene)
Arnauld
66
Caso de prueba sugerida: 3 2 1 1 4 h. Éste se detiene pero requiere más iteraciones que el doble del número de elementos.
Arnauld
10
Caso de prueba extralargo sugerido: 1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36que se detiene después de 786430 pasos.
Magma

Respuestas:

11

C # (compilador interactivo de Visual C #) , 71 bytes

x=>{for(int i=0,k=0,f=x.Count;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;i/=x[k];}

Pruébalo en línea!

No sé si lo siguiente es válido, ya que requiere un delegado personalizado con una firma de unsafe delegate System.Action<int> D(int* a); y tiene que estar envuelto en un unsafebloque para ser utilizado, pero aquí está de todos modos:

C # (.NET Core) , 64 bytes

x=>f=>{for(int i=0,k=0;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;k/=x[k];}

Pruébalo en línea!

Esta función toma un int * y devuelve una acción; en otras palabras, es una función al curry. La única razón por la que uso punteros es por codegolf.meta.stackexchange.com/a/13262/84206, que me permite guardar bytes al tener una variable ya definida con la longitud de la matriz.

Guardado 9 bytes gracias a @someone

Encarnación de la ignorancia
fuente
Golfó su código por 2 bytes: tio.run/…
IQuick 143
@ IQuick143 Buena captura, gracias
Encarnación de la ignorancia
No estoy seguro de si hay casos extremos en los que no va a funcionar, pero sin romper cualquiera de los casos de prueba actuales podría reemplazar 1<<fcon 2*fguardar un byte.
Kevin Cruijssen
1
77 bytes con horrible magia LINQ y la solución de Arnauld . No tengo idea de cómo funciona esta solución, así que puede que la haya roto.
alguien el
1
63 bytes a través de un golf normal de 1 byte y cambiando IO a error / no error. Enlace a enlace
alguien el
7

Python 3 , 63 89 bytes

def f(x):
 for i in range(2**len(x)):a=x[0];x[0]=-a;b=a%len(x);x=x[b:]+x[:b]
 return a==0

Pruébalo en línea!

También funciona para Python 2; Se puede guardar un byte en Python 2 reemplazando return con print y haciendo que la función print stdout en lugar de regresar. R gira Truepara detenerse y Falsepara no detenerse.

Gracias a @Neil y @Arnauld por señalar que necesitaba comprobar más tiempo para detenerme. Gracias a @Jitse por señalar un problema con [2,0]. Gracias a @mypetlion por señalar que el valor absoluto de la cinta podría exceder la longitud de la cinta.

Nick Kennedy
fuente
55
OK, voy a morder: ¿cómo sabes que x+xes suficiente?
Neil
44
@Neil En realidad no es suficiente. Un contraejemplo es [ 3, 2, 1, 1, 4, 0 ], que se detiene en más de 12 iteraciones.
Arnauld
1
len(x)*x[8,7,6,5,7,4,0,3,6]9 92
2
¿ 2**len(x)Todavía no está un poco por debajo del máximo? Calculo el número de estados como n*(2**n)(con n=len(x)-1).
OOBalance
1
@OOBalance Entiendo a qué te refieres, ya que cada estado puede tener un puntero en cada celda ... sin embargo, creo que hay algún otro límite aplicado por el hecho de que cada celda solo puede hacer la transición a otras dos celdas. Como nota al margen: nada en el desafío dice que tiene que haber un estado de detención en la entrada
Jo King
6

Jalea , 15 11 bytes

N1¦ṙ⁸ḢƊÐLḢẸ

Pruébalo en línea!

Un enlace monádico que toma la entrada como una lista de enteros usando 0 para significar detener. Devuelve 0 para las entradas de detención y 1 para las que no se detienen.

Evita el problema de la necesidad de calcular el número de iteraciones debido al uso del ÐLcual se repetirá hasta que no se vea ningún resultado nuevo.

¡Gracias a @JonathanAllan por guardar un byte!

Explicación

      ƊÐL   | Loop the following as a monad until the result has been seen before:
N1¦         | - Negate the first element
   ṙ⁸       | - Rotate left by each of the elements
     Ḣ      | - Take just the result of rotating by the first element
         Ḣ  | Finally take the first element
          Ẹ | And check if non-zero
Nick Kennedy
fuente
Guarde un byte girando por todas las entradas y luego simplemente manteniendo el primer resultado:N1¦ṙ⁸ḢƊÐLḢẸ
Jonathan Allan
5

Python 3 , 91 bytes

def f(a):
	s={0,};i=0
	while{(*a,)}-s:s|={(*a,)};a[i]*=-1;i-=a[i];i%=len(a)
	return a[i]==0

Pruébalo en línea!

-40 bytes gracias a JoKing y Jitse

Hiperneutrino
fuente
@JoKing 109 bytes haciendo las asignaciones variables en la primera línea.
Jitse
92 bytes cambiando la conversión de tupla a expansión destacada, no comenzando con un conjunto vacío y reformulando la whilecondición.
Jitse
@JoKing Maldición, nunca aprendo: p. 93 bytes entonces.
Jitse
91 bytes
Jitse
@JoKing gracias!
HyperNeutrino
5

Perl 6 , 46 43 36 bytes

{$_.=rotate(.[0]*=-1)xx 2**$_;!.[0]}

Pruébalo en línea!

Representa detener por 0y devuelve verdadero si la máquina se detiene. Esto repite los 2**(length n)tiempos lógicos , donde si el puntero termina en la celda detenida, permanece allí, de lo contrario estará en una celda no detenida.Esto funciona porque solo hay 2**nestados posibles (ignorando las celdas de detención) para la máquina Foo, ya que cada celda sin detención tiene solo dos estados.De acuerdo, sí, hay estados más que eso, pero debido a las posibles transiciones limitadas entre punteros (y, por lo tanto, estados) habrá menos de 2 ** $ _ estados ... creo

Explicación

{                                  }  # Anonymous codeblock
                     xx 2**$_         # Repeat 2**len(n) times
            .[0]*=-1                  # Negate the first element
 $_.=rotate(        )                 # Rotate the list by that value
                             ;!.[0]   # Return if the first element is 0
Jo King
fuente
2
El estado de la máquina Foo también incluye la ubicación del puntero, no solo los signos de cada celda.
Magma
1
Boceto de una prueba para una máquina Foo con cinta a_1 ... a_n 0. Considere un n-cubo de los signos de cada celda con bordes dirigidos (= una iteración de Foo) entre vértices (= estados), visitar el mismo vértice a través de cualquier bucle de bordes dará como resultado que la IP esté en la misma posición con la que comenzó . Prueba: en un bucle, la IP viaja en cada dimensión un número par de veces, es decir, la IP cambia en k × (a_j + (-a_j))% n ≡ 0 para cada dimensión, por lo tanto, siempre vuelve a la misma posición, solo se ve 1 estado de n estados para cada vértice, es decir, un máximo total de 2 ^ n estados (= número de vértices del cubo).
Kritixi Lithos
norte2norte.losol(norte)/ /norte
3

05AB1E , 14 13 bytes

goFć©(š®._}®_

Pruébalo en línea!

Toma la entrada como una lista de enteros con 0 como la instrucción de detención. Devuelve 1 para detener y 0 para no detener.

¡Gracias a @KevinCruijssen por guardar 2 bytes!

Nick Kennedy
fuente
Oh, bien, ¡eso es lo que hace tu respuesta de Jelly! Gran uso de la rotación y ć! Estaba esperando una explicación con la esperanza de jugar mi respuesta, pero me ganaste, jaja. ; p -1 byte haciendo el mismo golf que mi respuesta: g·Fto «v( Pruébelo en línea )
Kevin Cruijssen
Y un -1 adicional usando en ©®lugar de DŠs: «vć©(š®._}®_( Pruébelo en línea. )
Kevin Cruijssen
Como Arnauld señaló en su respuesta de Python, recorrer dos veces la longitud no es suficiente. Entonces puedes cambiar el «va goF.
Kevin Cruijssen
@KevinCruijssen gracias
Nick Kennedy
3

Java 8, 78 79 73 bytes

a->{int k=0,l=a.length,i=0;for(;i++<1<<l;k%=l)k-=(a[k]*=-1)%l-l;k/=a[k];}

Puerto directo de la respuesta C # .NET de @EmbodimentOfIgnorance , ¡así que asegúrate de votarlo!
Gracias a @Arnauld por encontrar dos errores (que también se aplica a algunas otras respuestas).

Da como resultado un java.lang.ArithmeticException: / by zeroerror cuando puede detenerse, o ningún error si no es así.

Pruébalo en línea.

Explicación:

a->{                   // Method with integer-array as parameter and no return-type
  int k=0,             //  Index integer, starting at 0
      l=a.length,      //  The length `l` of the input-array
  i=0;for(;i++<1<<l;   //  Loop 2^length amount of times:
          k%=l)        //    After every iteration: take mod `l` of `k`
    k-=                //   Decrease `k` by:
       (a[k]*=-1)      //    Negate the value at index `k` first
                 %l    //    Then take modulo `l` of this
                   -l; //    And then subtract `l` from it
                       //  (NOTE: the modulo `l` and minus `l` are used for wrapping
                       //  and/or converting negative indices to positive ones
  k/=a[k];}            //  After the loop: divide `k` by the `k`'th value,
                       //  which will result in an division by 0 error if are halting
Kevin Cruijssen
fuente
2
Solo me pregunto, ¿puedes tomar la longitud como un argumento adicional? El valor predeterminado para la publicación de IO en meta no lo dice, y la única razón por la que mi segunda respuesta tarda un tiempo es porque toma un int*(de codegolf.meta.stackexchange.com/a/13262/84206 )
Encarnación de la ignorancia
@EmbodimentofIgnorance Ah, cuando vi su respuesta, asumí que había algún tipo de meta regla que permitía tomar la longitud como entrada adicional, pero eso solo se aplica a los punteros. Gracias por hacérmelo saber. He eliminado el parámetro de longitud (pero aún uso el error / no-error para determinar el resultado).
Kevin Cruijssen
3

Haskell , 79 bytes

s x|m<-length x,let g(n:p)=(drop<>take)(mod n m)(-n:p)=iterate g x!!(2^m)!!0==0

Pruébalo en línea!

Devoluciones Truepara máquinas de detención, y de lo Falsecontrario. Entrada en forma de una lista, con la 0representación de un estado de detención.

Asume una versión de GHC mayor que 8.4 (lanzada en febrero de 2018).

B. Mehta
fuente
2

JavaScript (Node.js) , 71 67 bytes

x=>{for(p=l=x.length,i=2**l;i--;)p+=l-(x[p%l]*=-1)%l;return!x[p%l]}

Básicamente lo mismo que la respuesta C # .NET de @EmbodimentOfIgnorance

Ahorro de 4 bytes gracias a @Arnaud

Pruébalo en línea!

JavaScript (Node.js) , 61 bytes

x=>{for(p=l=x.length,i=2**l;i--;p+=l-(x[p%l]*=-1)%l)x[p%l].f}

Esta versión se usa undefinedcomo un símbolo de detención y arroja un TypeError: Cannot read property 'f' of undefinedcuando la máquina se detiene y termina silenciosamente cuando la máquina no se detiene.

Pruébalo en línea!

IQuick 143
fuente
1

Scala , 156 bytes

Sigue siendo goloso en mi opinión, pero estoy de acuerdo con esto por ahora. Devuelve 0para no detener Fooy 1para detener Foos. Toma la entrada acomo an Array[Int], por lo que hse toma como 0.

var u=Seq[Array[Int]]()//Keep track of all states
var i=0//Index
while(u.forall(_.deep!=a.deep)){if(a(i)==0)return 1//Check if we are in a previously encountered step ; Halt
u:+=a.clone//Add current state in the tracker
var k=i//Stock temp index
i=(a(i)+i)%a.length//Move index to next step
if(i<0)i+=a.length//Modulus operator in Scala can return a negative value...
a(k)*=(-1)}//Change sign of last seen index
0//Returns 0 if we met a previous step

Es bastante largo de ejecutar (alrededor de 4 segundos para todos los casos de prueba) debido a las múltiples búsquedas de matriz completa que hice, más las .deepque crean copias ... Pero aún puede intentarlo en línea.

V. Courtois
fuente
1

Adjunto , 40 bytes

Not@&N@Periodic[{On[0,`-,_]&Rotate!_@0}]

Pruébalo en línea!

Explicación

{On[0,`-,_]&Rotate!_@0}

Esto realiza una sola iteración de la máquina Foo; niega el primer miembro, luego gira la matriz por el primer elemento (original, no negado) de la matriz.

Periodicaplicará esta función hasta que se acumule un resultado duplicado. Una máquina se detiene o entra en un bucle infinito trivial. Si se detiene, el primer elemento será 0. De lo contrario, será distinto de cero.

&NEs una forma de golf de obtener el primer elemento de una matriz numérica. Luego, Notregresa truepara 0 (máquinas de detención) y falsepara cualquier otra cosa (máquinas sin detención).

Conor O'Brien
fuente
1

Carbón , 28 bytes

≔⁰ηFX²L諧≔θ籧θη≧⁻§θη绬§θη

Pruébalo en línea! El enlace es a la versión detallada del código. Salidas que utilizan la salida booleana predeterminada de Charcoal, que es -para verdadero y nada para falso. Explicación:

≔⁰η

Inicialice el puntero de instrucciones.

FX²Lθ«

Haga un bucle tantas veces como haya estados teóricamente posibles.

§≔θ籧θη

Negar el valor en el puntero de instrucción.

≧⁻§θηη

Resta el nuevo valor del puntero de instrucción. Los accesos a la matriz de carbón son cíclicos, por lo que esto emula automáticamente la cinta circular de Foo.

»¬§θη

Al final del ciclo, indique si el programa se detuvo.

Neil
fuente
0

Stax , 11 bytes

Ç₧┬òE▐tµ|⌡1

Ejecutar y depurarlo

Toma entrada en forma de una matriz de enteros, con la 0detención de la representación.

Sale 1para una 0máquina de detención y para una máquina sin detención.

recursivo
fuente
0

Pyth , 12 bytes

!hu.<+_hGtGh

¡Banco de pruebas!

Utiliza el enfoque directo. Repetir hasta que veamos la lista dos veces en un estado idéntico. Para los programas que se detienen, la lista eventualmente tendrá un liderazgo 0porque es donde se detiene la recursividad. Para los programas que no se detienen, la lista no comenzará con 0, sino que estará en un estado en el que el proceso sería periódico y, por lo tanto, la máquina Foo no se detendría.

Sr. Xcoder
fuente