Solve the Halting Problem for Befinge

Question

Let's define a simple 2D language, which we'll give the incredibly original name befinge. Befinge has 5 instructions:

• <>^v, as in most 2D esolangs, redirect the instruction pointer in their respective directions.
• . is a no-op.

The instruction pointer starts out at the top-left corner going right. If the instruction pointer gets to an edge, the program halts. Every Befinge program will obviously either halt or go into an infinite loop which does nothing. Here are two examples:

Halting:

>.v
..<

Non-Halting:

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

The halting problem is not solvable for a Turing-complete language, but it is for this one. Your task is to write a program (or function) that takes as input a string representing the befinge program and returns a truthy or falsey value depending on whether it halts or not.

• You can assume that the input will consist only of these characters and will be padded with spaces to form a rectangle.
• You can use any set of five characters for the instructions (e.g. adws ).

Test Cases

Halting:

.

v>
>^

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

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

Non-Halting:

>..v
^..<

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

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

This is code-golf, so the shortest program (in bytes) wins.

Answer 1

ES6 (JavaScript), 111,101 bytes

EDIT: changed output values to true and false, instead of Y and N, to shave off 10 bytes more

Golfed

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

Test

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');

Sample Output

#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 !

Answer 2

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

Try it online!

The challenge is old, but I figured since this is the shortest Python, I will post it. Input is a list of strings, but the characters used are unusual.

> G
< B
v C
^ F
. L

For example, the third halting example turns into ['LLLLCLLLL', 'LLLLGLLLC', 'LFLLBLLLL', 'LLLLLLLCB', 'LLLLLLLCL', 'LLLLFLLBL']. Output is via exit code, 0 (success) for non-halting, and 1 (error) for halting. Any tips or tricks appreciated.

Answer 3

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 ^ @.!;>:'.-#;_

Try it online!

A befinge halting problem needs a befunge solution. Returns 0 for truthy and 1 for falsey. Puts the input on the grid starting from 1,15 and then moves on top, replacing the arrows with zeros. As soon as we hit a zero, we know it loops. Anything besides ><^v. and zero is considerd to halt the program, which includes the border of spaces we get around the program by placing it on the grid slightly offset.

One easy way to shave off a few bites would be to use numbers instead of ><^v. but I don't feel like that's worth it.

Answer 4

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

Try it 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

Try it online!

Answer 5

SmileBASIC, 158 145 bytes

If the same arrow is encountered more than once, the program will never halt. When the instruction pointer passes an arrow, it's replaced with a different symbol, which will cause the function to return 0 if it's reached again. If the IP goes out of bounds, it returns 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

Takes input as an array of strings. <any non-digit chracter>,1,2,3,4 = .,>,<,v,^

Answer 6

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],

This program takes I/O differently: please terminate each line with a space, including the last one. Turtlèd doesn't like newlines, as it uses a grid for it's second dimension of characters.

Try it online!

0 for loops forever, 1 for halts.

General explanation:

It writes the input on the grid, then it actually follows the path the arrows make around the grid, replacing each arrow with a * as it goes, also saving the direction in the char var. If it encounters an *, an arrow it hit before, the program would not halt, so it sets the char var to 0, exit the loop. Otherwise, it will hit the end of the grid and exit the loop. It will write the char var. If it hit the end of grid, it uses the direction stored in the char var to get back to the grid, and sets the char var to 1, for halts. If the char var was actually 0, not a direction, it does not need to get back, as it is still there, and it sets it back to 0. It clears the grid off, then writes the char var, 1 for halts, else 0.

Answer 7

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

Takes input as a two-dimensional character array and returns true for halting and false for an infinite loop. Works by setting visited direction characters to ~s as it recursively traverses them. Edit: Saved 31 bytes by updating my direction vector before recursing.

Abusing the instruction characters (1=^ 4=< 5=. 6=> 9=v) takes me down to 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

Answer 8

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

A function with 4 state arguments: position p, velocity v, step index i and size of one line s. Returns 1 if we didn't go out of bounds in 10^9 steps and nil otherwise. Actually how many steps do we need to check to be sure, (count %)? I think it is more than that as same NOP can be traversed horizontally and vertically.

Can be called like this (takes normal strings as arguments, get returns nil when out of bounds):

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

State transitions (+1, -1, +s, -s) are encoded in the dictionary {\> 1\< -1\^(- s)\. v\v s}.

Answer 9

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

Try it online!

Gives correct answer for ["<>"]

Answer 10

Java, 477

I know that this is not winning, n=and can probably be golfed more, but it implments a similar method as to what the other answers use, but this one uses hashmap to perform lookups. The input is using the symbols ><^v and anything other than that for the no op. Input comes through args.

GOLFED

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

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

Explanation coming soon!

Answer 11

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

Takes a string array as input. I have to golf this more but for now it's time to stress over the election.

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