Vamos definir uma linguagem simples 2D, o que nós vamos dar o nome incrivelmente originais befinge . Befinge tem 5 instruções:

• <>^v, como na maioria dos idiomas 2D, redirecione o ponteiro de instruções nas respectivas direções.
• . é um não-op.

O ponteiro de instruções começa no canto superior esquerdo, indo para a direita. Se o ponteiro de instruções chegar a uma borda, o programa será interrompido. Todo programa Befinge obviamente irá parar ou entrar em um loop infinito que não faz nada. Aqui estão dois exemplos:

Parada:

>.v
..<

Não-parada:

>....v
..v..<
..>v..
^..<..

O problema da parada não é solucionável para uma linguagem completa de Turing, mas é para esta. Sua tarefa é escrever um programa (ou função) que toma como entrada uma string representando o befinge programa e retorna um valor truthy ou Falsey dependendo se ele pára ou não.

• Você pode assumir que a entrada consistirá apenas desses caracteres e será preenchida com espaços para formar um retângulo.
• Você pode usar qualquer conjunto de cinco caracteres para as instruções (por exemplo adws ).

Casos de teste

Parada:

.

v>
>^

....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.

v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<

Não-parada:

>..v
^..<

>v<
v<.
>v.
v<.
>.^

>.>.>.v
.><.<.<

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

ES6 (JavaScript), 111, 101 bytes

EDIT: alterou os valores de saída para true e false , em vez de Y e N , para reduzir mais 10 bytes

Golfe

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0

Teste

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0  

//Alphabet Map
tr={
'<':'h',
'>':'l',
'^':'k',
'v':'j',
'.':'q',
'\n':'\n'
};

//Test
T=(I,A)=>{
console.log({"Y":"#Halting","N":"#Non-Halting"}[A]);
console.log("I=\n",I,"\nF(I)=",O=F([...I].map(s=>tr[s]).join('')));
console.log('NY'[O*1] == A ? "OK !" : "NOT OK !");
}

//Halting
T(
`>.v
..<`
,'Y');

//Non-Halting
T(
`>....v
..v..<
..>v..
^..<..`
,'N');

//Halting
T(
`.`
,'Y')

//Halting
T(
`v>
>^`
,'Y');

//Halting
T(
`....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.`
,'Y');

//Halting
T(
`v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<`
,'Y');

//Non-Halting
T(
`>..v
^..<`
,'N');

//Non-Halting
T(
`>v<
v<.
>v.
v<.
>.^`
,'N');

//Non-Halting
T(
`>.>.>.v
.><.<.<`
,'N');

Saída de amostra

#Halting
I=
>.v
..< 
F(I)= true
OK !    

#Non-Halting
I=
>....v
..v..<
..>v..
^..<.. 
F(I)= false
OK !

#Halting
I=
 . 
F(I)= true
OK !

#Halting
I=
v>
>^ 
F(I)= true
OK !

#Halting
I=
....v....
....>...v
.^..<....
.......v<
.......v.
....^..<. 
F(I)= true
OK !

#Halting
I=
v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^< 
F(I)= true
OK !

#Non-Halting
I=
>..v
^..< 
F(I)= false
OK !

#Non-Halting
I=
>v<
v<.
>v.
v<.
>.^ 
F(I)= false
OK !

#Non-Halting
I=
>.>.>.v
.><.<.< 
F(I)= false
OK !

Python 2 , 116 105 bytes

x=1
X=Y=y=0
H=[]
G=input()
while(X,Y,x,y)not in H:H+=[(X,Y,x,y)];C=ord(G[Y][X]);x=C%3-1;y=C%5-1;X+=x;Y+=y

Experimente online!

O desafio é antigo, mas achei que, como esse é o Python mais curto, eu o publicarei. Entrada é uma lista de cadeias, mas os caracteres usados ​​são incomuns.

> G
< B
v C
^ F
. L

Por exemplo, o terceiro exemplo de parada se transforma ['LLLLCLLLL', 'LLLLGLLLC', 'LFLLBLLLL', 'LLLLLLLCB', 'LLLLLLLCL', 'LLLLFLLBL']. A saída é via código de saída, 0 (êxito) para não parar e 1 (erro) para parar. Todas as dicas ou truques apreciados.

Befunge-98 (PyFunge) , 217 209 200 bytes

#v10dpf1dp12dp3dpk
 >#v~:a-#v_$10dp1dg1+1dp >
v  >10dp;>0dg1dgp0dg1+0dp^;f1dp
>0dg1dgg:'^-#v_n1-v
^<v01_v#!->':<
  <   >:'<-#v_01-0>   v
v^pd1+gd3gd1[:'v-#v_01>3dp2dpndg1dgp
>0dg2dg+0dp ^ @.!;>:'.-#;_

Experimente online!

Um problema de parada precisa de uma solução rápida. Retorna 0 para truthy e 1 para falsey. Coloca a entrada na grade a partir de 1,15 e depois se move para cima, substituindo as setas por zeros. Assim que atingimos o zero, sabemos que ele faz um loop. Qualquer coisa além de> <^ v. e zero é considerado para interromper o programa, que inclui a borda dos espaços que contornamos o programa, colocando-o na grade ligeiramente deslocada.

Uma maneira fácil de eliminar algumas mordidas seria usar números em vez de> <^ v. mas não acho que valha a pena.

Turtlèd , 146 bytes

!u[*.[ r+.]l[ l]dr_+]#*#[ u]d[ (.r)(>.r{.r}@>)(v.d{.d}@v)(<.l{.l}@<)(^.u{.u}@^)(*@0' )],@1(0@0)(v' d)(<' r)(>' l)(^' d)[ u]d[ l]r[ [ r]l[ ' l]dr],

Este programa tem E / S diferente: por favor, termine cada linha com um espaço, incluindo o último. Turtlèd não gosta de novas linhas, pois usa uma grade para sua segunda dimensão de caracteres.

Experimente online!

0 para loops para sempre, 1 para paradas.

Explicação geral:

Ele grava a entrada na grade e, na verdade, segue o caminho que as setas fazem ao redor da grade, substituindo cada seta por um *, além de salvar a direção no char var. Se encontrar um *, uma flecha que atingiu antes, o programa não será interrompido, portanto, definirá char var para 0sair do loop. Caso contrário, atingirá o final da grade e sairá do loop. Ele escreverá o char var. Se atingir o final da grade, ele usa a direção armazenada no char var para retornar à grade e define o char var como 1, para paradas. Se o char var era realmente 0, não uma direção, ele não precisa voltar, pois ainda está lá, e o define novamente 0. Ele limpa a grade e depois escreve o char var, 1para paradas, caso contrário 0.

JavaScript (Node.js) , 80 bytes

f=(a,v=1,x=0,[t,...u]=a,n=1+a.search`
`,c=a[x])=>t?f(a,v=+c?c-2||v:c+n,x-v,u):!c

Experimente online!

JavaScript (Node.js) , 86 bytes

f=(a,v=1,x=0,[t,...u]=a,n=1+a.search`
`,c=a[x])=>t?c>' '<=f(a,v=+c?c-2||v:c+n,x-v,u):0

Experimente online!

JavaScript (ES6), 158 127 bytes

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>c<'~'?(c>'.'&&(a[y][x]='~',d=(c=='>')-(c=='<'),e=(c=='v')-(c=='^')),f(a,x+d,y+e,d,e)):!c

Recebe a entrada como uma matriz de caracteres bidimensional e retorna truepara interrupção e falsepara um loop infinito. Funciona definindo caracteres de direção visitados como~ como s, medida que os percorre recursivamente. Editar: Salva 31 bytes, atualizando meu vetor de direção antes de recursar.

O abuso dos caracteres de instrução ( 1=^ 4=< 5=. 6=> 9=v) me reduz a 101 bytes:

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>+c?(c-5&&(a[y][x]='0',d=~-c%4,e=~-(c>>2)),f(a,x+d,y+e,d,e)):!c

SmileBASIC, 158 145 bytes

Se a mesma seta for encontrada mais de uma vez, o programa nunca será interrompido. Quando o ponteiro da instrução passa uma seta, ele é substituído por um símbolo diferente, que fará com que a função retorne 0 se for alcançada novamente. Se o IP sair dos limites, ele retornará 1.

DEF H P@L
C=VAL(P[Y][X])IF C>8THEN?0RETURN
IF C THEN D=C-1P[Y][X]="9
X=X+!D-(D==1)Y=Y+(D==2)-(D>2)IF X+1&&Y+1&&Y-LEN(P)&&X-LEN(P[0])GOTO@L
?1
END

Recebe entrada como uma matriz de seqüências de caracteres. <any non-digit chracter>, 1, 2, 3, 4= ., >, <, v,^

Python 2, 182 bytes

m,v,d,x,y=input(),[],'>',0,0
try:
 while 1:
  if[x,y]in v:print 0;break
  c=m[y][x]
  if c!='.':d=c;v+=[[x,y]]
  if d in'><':x+=[-1,1][d=='>']
  else:y+=[-1,1][d=='v']
except:print 1

Toma uma matriz de cadeia de caracteres como entrada. Eu tenho que jogar mais isso, mas por enquanto é hora de me estressar com a eleição.

Ungolfed:

input = input()

visited = [  ] 

dir = ">"
x=0
y=0

try:
    while True:
        if[x,y]in visited:print False;break
        char=input[y][x]
        if char!=".":
            dir=char
            visited+=[[x,y]]

        if dir==">":
            x+=1
        if dir=="<":
            x-=1
        if dir=="v":
            y+=1
        if dir=="^":
            x-=1
except:
    print True

Clojure, 143 bytes

#((fn[p v i s](if-let[v({\> 1\< -1\^(- s)\. v\v s}(get % p))](if(neg? i)1(recur(+ p v)v(dec i)s))))0 1 1e9(+(count(take-while(set"<>v^.")%))1))

Uma função com 4 argumentos de estado: posição p, velocidade v, índice de etapas ie tamanho de uma linha s. Retorna 1se não sairmos dos limites em 10 ^ 9 etapas e nilcaso contrário. Na verdade, quantas etapas precisamos verificar para ter certeza (count %)? Eu acho que é mais do que isso, já que o mesmo NOP pode ser percorrido horizontal e verticalmente.

Pode ser chamado assim (usa seqüências de caracteres normais como argumentos, getretorna nilquando está fora dos limites):

(def f #( ... ))
(f ">....v\n..v..<\n..>v..\n^..<..")
(f "v>\n>^")
(f "....v....\n....>...v\n.^..<....\n.......v<\n.......v.\n....^..<.")

As transições de estado (+1, -1, + s, -s) são codificadas no dicionário {\> 1\< -1\^(- s)\. v\v s}.

Python 2/3, 201 192 bytes

def f(x):
 X=Y=b=0;a=1;D={}
 while len(x)>Y>-1<X<len(x[Y]):
  try:
   a,b={'>':(1,0),'^':(0,-1),'<':(-1,0),'v':(0,1)}[x[Y][X]]
   if(X,Y)in D:return 0
  except:0
  D[X,Y]=0;X+=a;Y+=b
 return 1

Experimente online!

Dá a resposta correta para ["<>"]

Java, 477

Eu sei que isso não está ganhando, n = e provavelmente pode ser mais jogado, mas implementa um método semelhante ao que as outras respostas usam, mas este usa o hashmap para realizar pesquisas. A entrada está usando os símbolos> <^ v e qualquer outra coisa que não seja a do no op. A entrada vem através de argumentos.

GOLFE

import java.util.*;interface B{static void main(String[]a){HashMap<String,Byte>h=new HashMap<>();int x,y=0;for(String s:a){x=0;for(char c:s.toCharArray()){if("><^v".indexOf(c)>-1)h.put(x+","+y,(byte)c);x++;}y++;}x=0;y=0;int d=0;int D=0;while(x>-1&&x<a[0].length()&&y<a.length&&y>-1){Byte v=h.get(x+","+y);if(v!=null){if(v==0){System.out.print(0);return;}d=(v<85)?"<>".indexOf(v)*2-1:0;D=(v>84)?"^v".indexOf(v)*2-1:0;}h.replace(x+","+y,(byte)0);x+=d;y+=D;}System.out.print(1);}}

UNGOLFED

importar java.util. *;

interface B{
    static void main(String a[]) {
        HashMap<String, Byte> h = new HashMap<>();
        int x, y = 0;
        for(String s : a) {
            x = 0;
            for(char c : s.toCharArray()) {
                if ("><^v".indexOf(c) > -1) h.put(x + "," + y, (byte) c);
                x++;
            }
            y++;
        }
        x = 0;
        y = 0;
        int d = 0;
        int D = 0;
        while(x > -1 && x < a[0].length() && y < a.length && y > -1) {
            Byte v = h.get(x + "," + y);
            if(v != null) {
                if(v == 0) {System.out.print(0); return;}
                d = (v < 85) ? "<>".indexOf(v)*2-1 : 0;
                D = (v > 84) ? "^v".indexOf(v)*2-1 : 0;
            }
            h.replace(x + "," + y, (byte) 0);
            x += d;
            y += D;
        }
        System.out.print(1);
    }
}

Explicação em breve!