No espírito de resolver o problema de parada para Befinge , vamos definir outra linguagem 2D chamada Modilar SNISP . O SNISP Modilar tem as seguintes seis instruções:

• \ direciona o ponteiro da instrução da seguinte maneira:
  • se abordado de cima, vá para a direita;
  • se for abordado da direita, suba;
  • se aproximado de baixo, vá para a esquerda;
  • se aproximado da esquerda, desça.
• / direciona o ponteiro da instrução da seguinte maneira:
  • se abordado de cima, vá para a esquerda;
  • se abordado a partir da esquerda, suba;
  • se abordado de baixo, vá para a direita;
  • se aproximado da direita, desça.
• ! pula a próxima instrução.
• @ coloca a localização e a direção do IP na pilha de chamadas.
• #exibe um local IP e uma direção da pilha de chamadas e os restaura e depois pula a próxima instrução. Se a pilha de chamadas estiver vazia, a execução será interrompida.
• . faz nada.

O ponteiro de instruções começa no canto superior esquerdo, indo para a direita. Se ele sair do campo, a execução será interrompida.

O SNISP Modilar não pode ser mais poderoso que um PDA , porque sua única fonte de armazenamento ilimitado é uma pilha (a pilha de chamadas) com um alfabeto finito (o conjunto de todos os pares IP (local, direção)). O problema da parada é decidível para os PDAs , portanto esse desafio sempre deve ser possível.

O desafio

Seu objetivo é escrever um programa que utilize uma matriz de caracteres representando um programa SNISP Modilar e retorne uma das duas saídas distintas, dependendo de parar ou não.

Isso é código-golfe , então o programa válido mais curto (medido em bytes ) vence.

Especificações

• A maneira como você utiliza uma matriz de caracteres é flexível: uma string separada por nova linha, matriz de cadeias, matriz de matrizes de caracteres, matriz 2D de caracteres, matriz plana de caracteres com um número inteiro representando a largura etc. são todos aceitáveis. Os casos de teste optam pela primeira dessas opções.
• Você pode assumir que a matriz de entrada será retangular (portanto, não será necessário preencher linhas curtas) e terá comprimento e largura diferentes de zero.
• Você pode escolher duas saídas distintas, não apenas verdade / falsidade.
• Você pode assumir que a matriz de entrada irá consistir apenas de comandos válidos ( \, /, !, @, #, e .).
• Quando se diz que um comando "ignora a próxima instrução", você pode assumir que haverá uma próxima instrução a ignorar. Em particular, ele nunca será encontrado em circunstâncias em que (1) esteja na borda do campo de jogo e (2) o IP esteja se movendo perpendicularmente a essa borda, de modo que a "próxima instrução" depois dela esteja fora do campo de jogo.

Casos de teste

O fragmento a seguir pode ser usado para testar programas no idioma. Observe que é um pouco mais permissivo do que a especificação real fornecida aqui (por exemplo, permite caracteres diferentes de .não-ops).

function htmlEscape(t){let i=document.createElement("span");return i.innerText=t,i.innerHTML}function tick(){snisp.tick(),snisp.update()}function run(){runButton.style.display="none",stopButton.style.display="",code.style.display="none",executionArea.style.display="",snisp.initialize(),intervalId=setInterval(tick,INTERVAL_MS)}function stop(){runButton.style.display="",stopButton.style.display="none",code.style.display="",executionArea.style.display="none",clearInterval(intervalId)}let TICKS_PER_SECOND=5,INTERVAL_MS=1e3/TICKS_PER_SECOND,runButton=document.getElementById("run-button"),stopButton=document.getElementById("stop-button"),code=document.getElementById("code"),executionArea=document.getElementById("execution-display"),intervalId,snisp={x:null,y:null,direction:null,callStack:null,stopped:null,playfield:null,padRows:function(){let t=Math.max(...this.playfield.map(t=>t.length));for(let i=0;i<this.playfield.length;i++)this.playfield[i]=this.playfield[i].padEnd(t,".")},initialize:function(){this.x=0,this.y=0,this.direction="right",this.callStack=[],this.stopped=!1,this.playfield=code.value.split("\n"),this.padRows(),this.update()},getCurrentChar:function(){let t=this.playfield[this.y];if(void 0!=t)return t[this.x]},backslashMirror:function(){let t={up:"left",right:"down",down:"right",left:"up"};this.direction=t[this.direction]},slashMirror:function(){let t={up:"right",right:"up",down:"left",left:"down"};this.direction=t[this.direction]},forward:function(){switch(this.direction){case"up":this.y-=1;break;case"down":this.y+=1;break;case"left":this.x-=1;break;case"right":this.x+=1;break;default:throw"direction is invalid"}},pushState:function(){this.callStack.push({x:this.x,y:this.y,direction:this.direction})},restoreState:function(){let t=this.callStack.pop();void 0!=t?(this.x=t.x,this.y=t.y,this.direction=t.direction):this.stopped=!0},tick:function(){if(this.stopped)return;let t=this.getCurrentChar();if(void 0!=t){switch(t){case"\\":this.backslashMirror();break;case"/":this.slashMirror();break;case"!":this.forward();break;case"@":this.pushState();break;case"#":this.restoreState(),this.forward()}this.forward()}else this.stopped=!0},generatePlayfieldHTML:function(t,i){let e=[];for(let n=0;n<this.playfield.length;n++){let s=[],l=this.playfield[n];for(let e=0;e<l.length;e++){let a=htmlEscape(l[e]);e==t&&n==i&&(a='<span class="highlight">'+a+"</span>"),s.push(a)}e.push(s.join(""))}return e.join("<br>")},update:function(){let t=[];for(let i=0;i<this.callStack.length;i++){let e=this.callStack[i];t.push(this.generatePlayfieldHTML(e.x,e.y))}t.push(this.generatePlayfieldHTML(this.x,this.y));let i=t.join("<br><br>");executionArea.innerHTML=i}};

#code{font-family:monospace;}#execution-display{font-family:monospace;white-space:pre;}.highlight{background-color:yellow;}

<b>Code:</b><br/><textarea id="code" width="300" height="300"></textarea><br/><button id="run-button" onclick="run()">Run</button><button id="stop-button" onclick="stop()" style="display: none;">Stop</button><br/><div id="execution-display"></div>

A forma não destruída pode ser encontrada aqui .

Parada

.

O menor programa possível. Sai pela direita.

\\
\/

Enrola o programa e sai do topo.

.\./.\
.\!/./

Entra em loop. Enrola parte da pista em duas direções diferentes.

@\!/#
.\@/#

Usa todos os seis comandos.

@.@.@.@.@.@.@.@.@.#

O tempo de execução deste programa é exponencial no número de repetições de @., mas ainda pára.

Non-Halting

!/\
.\/

Eu acredito que este é o loop infinito mais curto.

@!\\#/@\!\
//@//.#./.
.\#.!\./\.
#.\!@!\@//
/..@.@\/#!
\.@.#.\/@.

Isso gira ao redor da pista, gerando quadros de pilha ocasionalmente, antes de eventualmente ser pego em um ciclo gerando infinitamente quadros de pilha. Nem todos os comandos são realmente usados.

.!/@.@.@.@.@.\
/.@.@.@.@.@.@/
\@.@.@.@.@.@.\
/.@.@.@.@.@.@/
.@\@.@.@.@.@.\
\.@.@.@.@.@.@/

Continua criando quadros de pilha, mas nenhum deles retorna.

Python 3 , 639 bytes 630 bytes 593 bytes

def e(I):
 m=[(0,-1),(0,1),(1,1),(1,-1)];a=lambda i:(tuple(i[0]),i[1]);b=lambda s,q:s.s==q.s and s.S&q.S==q.S
 class O():i=[[0,0],2];S=[];A={}
 def z():d=m[O.i[1]];O.i[0][d[0]]+=d[1]
 def y():O.i=O.S.pop();z()
 def x():O.i[1]=[3,2,1,0][O.i[1]]
 def w():O.i[1]=[2,3,0,1][O.i[1]]
 def v():O.S+=[[O.i[0][:],O.i[1]]]
 while 1:
  p=O();p.s=a(O.i);p.S={a(i)for i in O.S};l=O.A.setdefault(p.s,[]);c=any((b(p,s)for s in l));l+=[p];e=O.i[0];d=not((0<=e[0]<len(I))and(0<=e[1]<len(I[0])))or((x,w,z,v,lambda:len(O.S)==0 or y(),lambda:0)["\\/!@#.".find(I[e[0]][e[1]])]()==1);z()
  if d!=c:return not c or d

Experimente online!

Eu sinto que isso é mais fonte minificada do que golfe ... Tenho certeza de que há uma maneira melhor de chegar lá.

Programa funciona como um intérprete completo para o idioma. Para quando:

1. Saímos do programa
2. Detectamos que estamos em um loop.

A detecção de loop é um tanto ingênua (e com muita memória). Antes de avaliar cada movimento, armazenamos em cache nossa Direção, Posição e Pilha atuais. Se percebermos que chegamos a uma posição em que estivemos antes, movendo na mesma direção, e nossa pilha atual é um superconjunto de uma pilha anterior nessa posição + direção, sabemos que estamos em um loop e a pilha está crescendo (ou permanecendo constante).

Edit 1 - Graças a Herman L por cortar o "passe". Também corte "Verdadeiro".

Edit 2 - Lambda-ified algumas funções. Número reduzido de devoluções. Retorna "Verdadeiro" para terminar e "Falso" para não terminar. Alavancou a classe O existente como objeto de rastreamento, eliminando a necessidade de N classe.

JavaScript (ES6), 258 254 bytes

p=>(d=>{for(x=y=r=k=1,s=[],v={};w=[--x,--y,d],c=1<<"\\!@/#".indexOf(q=(p[y]||0)[x]),q&&r&&(e=v[w]?v[w].some(u=>!s.some(t=>u+0==t+0)):1);x+=d>>2,y+=d&3)v[w]=[...s],k=k?c&9?d=c&1?d/4|4*d&12:(d+5)%10:c&4?s.push(w):c&16?(r=s.pop())&&!([x,y,d]=r):c-2:1})(9)|e

Espera um programa não vazio como uma matriz de cadeias, em que cada elemento representa uma linha do SNISP Modilar. Saída 1se o programa fornecido parar e, 0caso contrário.

Mesma lógica da resposta de @ machina.widmo . Algumas tentativas fracassadas de métodos alternativos me levaram a concluir que eles produziriam código mais longo de qualquer maneira!

Experimente online!

Explicação

Semelhante à outra resposta, esta função sai com:

• 1 se o programa parar (por exemplo, o IP sai da grade ou uma pilha vazia é exibida)
• 0 se o IP atingir um posição que ele já visitou, movendo-se na mesma direção e com um superconjunto da pilha presente na visita anterior.

Por que a mesma direção?

 1
!\/

O programa acima pára, mas atinge a mesma posição (caractere 1), com uma pilha idêntica, mas de uma direção diferente.

Por que um superconjunto e não apenas o tamanho da pilha?

  ab4
!/@@.\
.\..#/

Isso também é interrompido e o IP atinge o caractere 4 de uma direção consistente quatro vezes, com os seguintes estados da pilha ( *indica o topo da pilha):

• tamanho = 2 [a, b] *
• tamanho = 1 [a] *
• tamanho = 1 [b] *
• tamanho = 0 [] *

Como o intérprete funciona

As instruções ( q) são traduzidas para binário ( c) da seguinte maneira (com todos os outros caracteres .ou de outra forma, servindo como nops):

1 2 4 8 16
\ ! @ / #

Direction ( d) é representado como um campo de bit:

9 -> right : 1001
1 -> left  : 0001
6 -> down  : 0110
4 -> up    : 0100

Espelhos (\/ ) transformam a direção:

\: 6-> 9 9-> 6 4-> 1 1-> 4

d/4 | 4*d&12

/: 1-> 6 6-> 1 4-> 9 9-> 4

(d+5) % 10

Novas direções transformam a posição:

x += d>>2 - 1

y += d&3 - 1

Outras variáveis ​​globais

• x, y : Posição IP
• r: retém o valor da pilha
• k: falsy se pular a próxima instrução (por exemplo, de !# )
• s: pilha
• v: armazena em cache as posições visitadas, direção, instantâneo da pilha
• w: [x, y, d], o valor armazenado na pilha e usado como o valor-chave parav
• e: falso se o programa não parar devido a uma correspondência de cache

Ungolfed

p => (d => {                                                  // set initial direction and avoid a verbose `return` statement
    for (
        x = y = r = k = 1,
        s = [],
        v = {};
        w = [--x, --y, d],                                    // decrement positions early so that x,y 
                                                              // do not require a separate assignment to 0
        c = 1 << "\\!@/#".indexOf(q = (p[y]||0)[x]),          // taking an index of undefined produces an error; using 0 does not
        q && r && (
            e = v[w]
                ? v[w].some(u => !s.some(t => u+0 == t+0))    // in order to compare two arrays, must coerce to strings
                : 1
        );
        x += d>>2,
        y += d&3
    )
        v[w] = [...s],                         // clone stack
        k = k
            ?
                c&9                            // if \ or /
                    ? d = c&1
                        ? d/4 | 4*d&12
                        : (d+5) % 10
                : c&4                          // if @
                    ? s.push(w)
                : c&16                         // if #
                    ? (r = s.pop())
                        && !([x, y, d] = r)    // destructure value in stack if any exists
                : c-2                          // 0 if !
            : 1
})(9) | e