Esta máquina Foo pára?

43

Sabe-se que determinar se uma máquina de Turing pára é indecidível, mas isso não é necessariamente verdade para máquinas mais simples.

Uma máquina Foo é uma máquina com fita finita, em que cada célula da fita possui um número inteiro ou o símbolo de parada h, por exemplo

2 h 1 -1

O ponteiro de instruções começa apontando para a primeira célula:

2 h 1 -1
^

A cada passo, o ponteiro da instrução avança pelo número para o qual aponta e depois nega esse número. Então, após uma etapa, ele avançaria 2células e transformaria 2em -2:

-2 h 1 -1
     ^

A máquina Foo continua fazendo isso até o ponteiro da instrução apontar para o símbolo de parada ( h). Então, aqui está a execução completa deste programa:

2 h 1 -1
^

-2 h 1 -1
     ^

-2 h -1 -1
         ^

-2 h -1 1
      ^

-2 h 1 1
   ^

A fita também é circular; portanto, se o ponteiro de instruções se mover de um lado da fita, ele será direcionado para o outro lado, por exemplo:

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

Uma coisa interessante sobre essas máquinas Foo é que algumas não param, por exemplo:

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á em loop nesses últimos quatro estados para sempre.

Então, escreva um programa que determine se uma máquina Foo pára ou não! Você pode usar qualquer formato de entrada (razoável) que desejar para as máquinas Foo e optar por usá-lo 0como símbolo de parada. Você pode usar duas saídas distintas para o caso em que ele pára e o caso em que não. É claro que seu programa deve fornecer uma resposta em um período finito de tempo para todas as entradas válidas.

Isso é , então tente tornar o seu programa o mais curto possível!

Casos de teste

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
fonte
5
Só para ter certeza, sobre o algoritmo para resolver isso. Eu não sou o mestre de algoritmos, então prefiro perguntar antes de ir na direção errada. Uma máquina Foo sem interrupção sempre voltará ao seu estado original exato? Ou existem máquinas "non-stoping" de comportamento caótico?
V. Courtois
5
@ V.Courtois Todas as máquinas Foo sem interrupção terminam em um loop de estados, porque há apenas muitos estados possíveis em que uma máquina Foo pode estar (não há lugares possíveis em que o ponteiro de instruções possa estar e 2 ^ n é possível configurações de fita). Cada estado possui um e apenas um "próximo estado". Portanto, se uma máquina Foo voltar ao estado em que já se encontra, ela continuará girando. Como existem apenas estados finitos, ele não pode continuar caoticamente entre os estados, porque acabará indo para o estado em que já esteve.
Leo Tenenbaum
3
Caso de teste sugerido: 1 2 h 42(não para)
Arnauld em
6
Caso de teste sugerido: 3 2 1 1 4 h. Este interrompe, mas requer mais iterações que o dobro do número de elementos.
Arnauld
10
Caso de teste extra longo 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 -36:, que é interrompido após 786430 etapas.
Magma

Respostas:

11

C # (compilador interativo do 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];}

Experimente online!

Não sei se o seguinte é válido, pois requer um delegado personalizado com uma assinatura unsafe delegate System.Action<int> D(int* a); e precisa ser agrupado em um unsafebloco para ser usado, mas aqui está:

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];}

Experimente online!

Essa função recebe um int * e retorna uma ação; em outras palavras, é uma função ao curry. A única razão pela qual eu uso ponteiros é por causa de codegolf.meta.stackexchange.com/a/13262/84206, que me permite salvar bytes já tendo uma variável já definida com o comprimento da matriz.

Guardado 9 bytes graças a @someone

Forma de Ignorância
fonte
Golfed seu código por 2 bytes: tio.run/…
IQuick 143
@ IQuick143 Boa captura, obrigado
Modalidade de Ignorância
Eu não tenho certeza se existem casos de ponta para que ele não vai funcionar, mas sem quebrar qualquer um dos casos de teste atuais você poderia substituir 1<<fcom 2*fa salvar um byte.
Kevin Cruijssen
1
77 bytes com horrível magia LINQ e correção de Arnauld . Não tenho idéia de como essa solução funciona, por isso posso tê-la quebrado.
alguém
1
63 bytes por meio de um golfe normal de 1 byte e alteração de IO para error / no error. Link para o link
alguém
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

Experimente online!

Também funciona para Python 2; um byte pode ser salvo no Python 2 substituindo return por print e tendo a função print em stdout em vez de retornar. R gira Truepara parar e Falsepara não parar.

Agradeço a @Neil e @Arnauld por notar que eu precisava verificar por mais tempo para parar. Obrigado a @Jitse por apontar um problema com [2,0]. Agradecemos a @mypetlion por observar que o valor absoluto dos valores da fita pode exceder o comprimento da fita.

Nick Kennedy
fonte
5
OK, vou morder: como você sabe que x+xé suficiente?
Neil
4
@ Neil Na verdade, não é suficiente. Um contra-exemplo é [ 3, 2, 1, 1, 4, 0 ], que para em mais de 12 iterações.
Arnauld
1
len(x)*x[8,7,6,5,7,4,0,3,6]92
2
2**len(x)Ainda não está nem um pouco abaixo do máximo? Eu calculo o número de estados como n*(2**n)(com n=len(x)-1).
OOBalance
1
@OOBalance Entendo o que você quer dizer, já que cada estado pode ter um ponteiro em cada célula ... no entanto, sinto que há outro limite aplicado pelo fato de que cada célula só pode fazer a transição para duas outras células. Como uma observação lateral: nada no desafio diz que deve haver um estado de parada na entrada
Jo King
6

Geléia , 15 11 bytes

N1¦ṙ⁸ḢƊÐLḢẸ

Experimente online!

Um link monádico que recebe a entrada como uma lista de números inteiros usando 0 para significar parada. Retorna 0 para interromper entradas e 1 para aqueles que não param.

Evita o problema de precisar trabalhar com o número de iterações, pois o uso ÐLserá repetido até que nenhum novo resultado seja visto.

Obrigado a @ JonathanAllan por salvar um byte!

Explicação

      ƊÐ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
fonte
Salve um byte girando todas as entradas e mantendo o primeiro 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

Experimente online!

-40 bytes graças ao JoKing e Jitse

HyperNeutrino
fonte
@JoKing 109 bytes executando as atribuições de variáveis ​​na primeira linha.
Jitse
92 bytes , alterando a conversão de tupla para expansão estrelada, não começando com um conjunto vazio e reformulando a whilecondição.
Jitse
@ JoKing Porra, eu nunca aprendo: p. 93 bytes então.
Jitse
91 bytes
Jitse
@JoKing thanks!
HyperNeutrino
5

Perl 6 , 46 43 36 bytes

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

Experimente online!

Representa a interrupção 0e retorna true se a máquina parar . Isso repete os 2**(length n)tempos lógicos , nos quais, se o ponteiro terminar na célula de parada, ele permanecerá lá, caso contrário, ele estará em uma célula de não parada. Isso funciona porque existem apenas 2**nestados possíveis (ignorando células de parada) para a máquina Foo estar, pois cada célula sem parada tem apenas dois estados. Ok, sim, existem estados além disso, mas devido às limitadas transições possíveis entre ponteiros (e, portanto, estados), haverá menos de 2 ** $ _ estados ... eu acho

Explicação

{                                  }  # 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
Brincadeira
fonte
2
O estado da máquina Foo também inclui a localização do ponteiro, não apenas os sinais de cada célula.
Magma
1
Esboço de uma prova para uma máquina Foo com fita a_1 ... a_n 0. Considere um cubo n dos sinais de cada célula com arestas direcionadas (= uma iteração de Foo) entre vértices (= estados), visitar o mesmo vértice através de qualquer loop de arestas fará com que o IP esteja na mesma posição em que começou com . Prova: em um loop, o IP viaja em cada dimensão um número par de vezes, ou seja, o IP muda em k × (a_j + (-a_j))% n ≡ 0 para cada dimensão, portanto, sempre retorna à mesma posição, sempre vendo 1 estado de n estados para cada vértice, ou seja, um total máximo de 2 ^ n estados (= número de vértices do cubo).
Kritixi Lithos
n2n.euog(n)/n .
Arnauld
3

05AB1E , 14 13 bytes

goFć©(š®._}®_

Experimente online!

Leva a entrada como uma lista de números inteiros com 0 como a instrução de parada. Retorna 1 para parar e 0 para não parar.

Obrigado a @KevinCruijssen por salvar 2 bytes!

Nick Kennedy
fonte
Oh legal, então é isso que a sua resposta Jelly faz! Ótimo uso da rotação e ć! Eu estava esperando por uma explicação na esperança de responder a minha resposta, mas você me venceu, haha. ; p -1 byte fazendo o mesmo golfe que a minha resposta: g·Fa «v( Experimente on-line. )
Kevin Cruijssen
E um -1 adicional usando em ©®vez de DŠs: «vć©(š®._}®_( Experimente online. )
Kevin Cruijssen
Como Arnauld observou na sua resposta em Python, repetir duas vezes o comprimento não é suficiente. Então você pode mudar «vpara goF.
Kevin Cruijssen
@KevinCruijssen thanks
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];}

Porta direta da resposta C # .NET do @EmbodimentOfIgnorance , por isso, vote- o novamente !
Agradecemos a @Arnauld por encontrar dois bugs (o que também se aplica a outras respostas).

Resulta em um java.lang.ArithmeticException: / by zeroerro quando é capaz de parar ou em nenhum erro, se não.

Experimente online.

Explicação:

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
fonte
2
Imaginando, você pode considerar o argumento como argumento adicional? O padrão para postagem de IO na meta não diz isso, e a única razão pela qual minha segunda resposta demora é que ela recebe um int*(de codegolf.meta.stackexchange.com/a/13262/84206 )
Modalidade de ignorância
@EmbodimentofIgnorance Ah, quando vi sua resposta, presumi que houvesse algum tipo de meta-regra que permitisse que o comprimento fosse tomado como entrada adicional, mas que só se aplica a ponteiros. Obrigado por me avisar. Eu removi o parâmetro length (mas ainda use o erro / nenhum erro para determinar o 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

Experimente online!

Retorna Truepara máquinas de parada, e Falsecaso contrário. Entrada na forma de uma lista, com a 0representação de um estado de parada.

Supõe uma versão do GHC maior que 8.4 (lançado em fevereiro de 2018).

B. Mehta
fonte
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]}

Basicamente, o mesmo que @EmbodimentOfIgnorance C # .NET do

Economize 4 bytes graças a @Arnaud

Experimente online!

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 versão usa undefinedcomo um símbolo de parada e lança umTypeError: Cannot read property 'f' of undefined quando a máquina pára e termina silenciosamente quando a máquina não para.

Experimente online!

IQuick 143
fonte
1

Scala , 156 bytes

OMI ainda jogável, mas estou bem com isso por enquanto. Retorna 0para Foos sem interrupção e s 1com interrupção Foo. Recebe a entrada acomo Array[Int], e hé tomada 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

É muito longo para executar (cerca de 4 segundos para todos os casos de teste) por causa das várias pesquisas de matriz completa que fiz, além das .deepque criam cópias ... Mas você ainda pode experimentá-lo online.

V. Courtois
fonte
1

Anexo , 40 bytes

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

Experimente online!

Explicação

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

Isso executa uma única iteração da máquina Foo; nega o primeiro membro e depois gira a matriz pelo primeiro elemento (original, não negado) da matriz.

Periodicaplicará esta função até que um resultado duplicado seja acumulado. Uma máquina pára ou entra em um loop infinito trivial. Se parar, o primeiro elemento será 0. Caso contrário, será diferente de zero.

&Né uma maneira de obter o primeiro elemento de uma matriz numérica. Em seguida, Notretorna truepara 0 (máquinas de parada) e falsepara qualquer outra coisa (máquinas sem parada).

Conor O'Brien
fonte
1

Carvão , 28 bytes

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

Experimente online! Link é a versão detalhada do código. Saídas usando a saída booleana padrão do Charcoal, que é -para true e nada para false. Explicação:

≔⁰η

Inicialize o ponteiro da instrução.

FX²Lθ«

Faça o loop tantas vezes quanto houver estados teoricamente possíveis.

§≔θ籧θη

Negue o valor no ponteiro da instrução.

≧⁻§θηη

Subtraia o novo valor do ponteiro da instrução. Os acessos à matriz do carvão vegetal são cíclicos, portanto emula automaticamente a fita circular do Foo.

»¬§θη

No final do loop, mostre se o programa foi interrompido.

Neil
fonte
0

Stax , 11 bytes

Ç₧┬òE▐tµ|⌡1

Execute e depure

Ele recebe entrada na forma de uma matriz inteira, com 0representação de parada.

Ele produz 1para uma parada e 0para uma máquina sem parada.

recursivo
fonte
0

Pitão , 12 bytes

!hu.<+_hGtGh

Suíte de teste!

Usa a abordagem direta. Faça o recursão até vermos a lista duas vezes em um estado idêntico. Para programas interrompidos, a lista acabará tendo uma liderança, 0porque é aí que a recursão para. Para programas que não são interrompidos, a lista não começa com o 0, mas sim em um estado no qual o processo seria periódico e, portanto, a máquina Foo não seria interrompida.

Mr. Xcoder
fonte