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 código golf , ¡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

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

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.

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

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

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

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!

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

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).

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!

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.

Perl 5 -ap , 88 bytes

for(;$F[$i]&&!$k{"$i|$F[$i]"};$i=($i+$F[$i])%@F){$k{"$i|$F[$i]"}=1;$F[$i]*=-1}$_=!$F[$i]

Pruébalo en línea!

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).

Carbón , 28 bytes

≔⁰ηＦＸ²Ｌ諧≔θ籧θη≧⁻§θη绬§θη

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.

ＦＸ²Ｌθ«

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.

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.

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.