Solve the Halting Problem for Modilar SNISP

Question

In the spirit of Solve the Halting Problem for Befinge, let's define another 2D language called Modilar SNISP. Modilar SNISP has the following six instructions:

• \ directs the instruction pointer as follows:
  • if approached from the top, go right;
  • if approached from the right, go up;
  • if approached from the bottom, go left;
  • if approached from the left, go down.
• / directs the instruction pointer as follows:
  • if approached from the top, go left;
  • if approached from the left, go up;
  • if approached from the bottom, go right;
  • if approached from the right, go down.
• ! skips over the next instruction.
• @ pushes the IP location and direction onto the call stack.
• # pops an IP location and direction from the call stack and restores them, then skips over the next instruction. If the call stack is empty, execution halts.
• . does nothing.

The instruction pointer starts at the top left corner going right. If it ever leaves the playfield, execution halts.

Modilar SNISP cannot be more powerful than a PDA, because its only source of unbounded storage is a stack (the call stack) with a finite alphabet (the set of all IP (location, direction) pairs). The halting problem is decidable for PDAs, so this challenge should always be possible.

The Challenge

Your goal is to write a program that takes a matrix of characters representing a Modilar SNISP program and returns one of two distinct outputs depending on whether it halts or not.

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

Specifications

• The way you take a matrix of character is flexible: a newline-separated string, array of strings, array of arrays of characters, 2d array of characters, flat array of characters with an integer representing width, etc. are all acceptable. The test cases opt for the first of those choices.
• You can assume that the input matrix will be rectangular (so you don't have to pad short rows) and will be of nonzero length and width.
• You can choose any two distinct outputs, not just truthy/falsy.
• You can assume that the input matrix will consist only of valid commands (\, /, !, @, #, and .).
• When a command is said to "skip the next instruction," you can assume that there will be a next instruction to skip. In particular, it will never be encountered in circumstances where (1) it lies on the playfield's edge and (2) the IP is moving perpendicular to that edge, such that the "next instruction" after it would lie outside the playfield.

Test Cases

The following snippet can be used to test programs in the language. Note that it is slightly more permissive than the actual specification given here (e.g. it permits characters other than . as no-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>

The ungolfed form can be found here.

Halting

.

The smallest program possible. Goes out the right.

---

\\
\/

Winds around the program and goes out the top.

---

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

Goes in a loop. Winds through part of the track in two different directions.

---

@\!/#
.\@/#

Uses all six commands.

---

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

This program's execution time is exponential in the number of repetitions of @., but it still halts.

---

Non-Halting

!/\
.\/

I believe this is the shortest infinite loop.

---

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

---

This winds around the track, spawning stack frames occasionally, before eventually getting caught in a cycle infinitely generating stack frames. Not all commands are actually used.

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

Keeps creating stack frames, but none of them ever return.

Answer 1

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

Try it online!

I feel like this is more of minified source than golf... I'm sure there's a better way to get there.

Program works as a full interpreter for the language. It stops either when:

1. We exit the program
2. We detect we're in a loop.

Loop detection is somewhat naive (and memory heavy). Before we evaluate each move, we cache off our current Direction, Position, and Stack. If we see we've come to a position we've been to before, moving the same direction, and our current stack is a super set of a previous stack at this position + direction, then we know we're in a loop and the stack is either growing (or staying constant).

Edit 1 - Thanks to Herman L for cutting "pass". Also cut "True".

Edit 2 - Lambda-ified some functions. Reduced number of returns. Returns "True" for terminating and "False" for non-terminating. Leveraged existing O class as tracking object, eliminating the need for N class.

Answer 2

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

Expects a non-empty program as an array of strings, where each element represents a line of Modilar SNISP. Outputs 1 if the given program halts, and 0 otherwise.

Same logic as @machina.widmo's answer. A few failed attempts at alternative methods led me to conclude that they'd produce longer code anyway!

Try it online!

Explanation

Similar to the other answer, this function exits with:

• 1 if the program halts (e.g. the IP moves off the grid or an empty stack is popped)
• 0 if the IP reaches a position it has already visited, moving in the same direction, and with a superset of the stack present in the previous visit.

Why the same direction?

 1
!\/

The above program halts, but hits the same position (character 1), with an identical stack, but from a different direction.

Why a superset and not merely stack size?

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

This also halts, and the IP hits character 4 from a consistent direction four times, with the following stack states (* indicates the top of the stack):

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

How the interpreter works

Instructions (q) are translated into binary (c) as follows (with all other characters, . or otherwise, serving as nops):

1 2 4 8 16
\ ! @ / #

Direction (d) is represented as a bit field:

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

Mirrors (\/) transform the direction:

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

d/4 | 4*d&12

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

(d+5) % 10

New directions transform the position:

x += d>>2 - 1

y += d&3 - 1

Other global variables

• x, y: IP position
• r: holds value popped off the stack
• k: falsy if skipping the next instruction (e.g. from !#)
• s: stack
• v: caches visited positions, direction, snapshot of stack
• w: [x, y, d], the value stored on the stack and used as the key value for v
• e: falsy if program does not halt due to a cache match

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

Answer 3

APL (Dyalog Unicode), 93 bytes

⍬{~1∊∊⍺⍷¨⊂⍵:(⍺,⊂⍵)∇(1↓⍵),⍨⊃⍬(⊂1⌽⍉g)(⊂⍉⊖⌽1⌽g)(⊂2⌽g)((1⌽g)(2⌽g))(⊂1⌽g)⌷⍨'#\/!@.'⍳⊃⊃g←⊃⍵}⊂1⍪⍨⎕,0

Try it online!

Instead of moving the IP around the grid, we move the grid around the IP, so the current IP is always at the top-left with direction pointing right.

Raises an IndexError to indicate halting; no error indicates a non-halting SNISP program.

(⊂1⌽g)⌷⍨'#\/!@.'⍳⊃⊃g←⊃⍵}⊂1⍪⍨⍵,0}
⍬{~1∊∊⍺⍷¨⊂⍵:(⍺,⊂⍵)∇(1↓⍵),⍨⊃⍬(⊂1⌽⍉g)(⊂⍉⊖⌽1⌽g)(⊂2⌽g)((1⌽g)(2⌽g))(⊂1⌽g)⌷⍨'#\/!@.'⍳⊃⊃g←⊃⍵}⊂1⍪⍨⎕,0
          ⊂1⍪⍨⎕,0 ⍝ Pass an initial stack: the input padded with 0s on the right and 1s on the bottom
                   ⍝ This lets us treat the program grid as wraparound
                   ⍝ 1 and 0 could be any 2 distinct values not in '#\/!@.'
                   ⍝ They have to be different to differentiate SNISP programs that are symmetric on the main diagonal
⍬                 ⍝ Pass an initial stack history
 {...}            ⍝ Inner function:
 ~1∊∊⍺⍷¨⊂⍵:        ⍝ Only continue if the stack is not a prefix of any member of the stack history
                    ⍝ Prefix because the top of the stack is the first element and gives the current direction/position
 (⍺,⊂⍵)∇           ⍝ Recurse with an appended stack history and an updated stack:
          g←⊃⍵      ⍝ Pop the current grid off the stack
      ⍬...⊂1⌽g      ⍝ A list of all possible stack changes. Will add to the stack:
       ⍬             ⍝ #: nothing, so the next step pops the stack
       ⊂1⌽⍉g         ⍝ \: transposed grid, wrap-rotated right by 1; the new IP is 1 unit down
       ⊂⍉⊖⌽1⌽g       ⍝ /: new grid such that the new IP is at the current bottom-left
       2⌽g           ⍝ !: new grid has IP 2 units to the right
       (1⌽g)(2⌽g)    ⍝ @: push both 1⌽g, which is the same as the '.' instruction,
                      ⍝ and 2⌽g, which is the same as the '!' instruction.
                      ⍝ The 1⌽g will be immediately popped for the next position
       ⊂1⌽g          ⍝ .: Push 1⌽g, which simply moves the IP 1 unit to the right
   ⌷⍨'#\/!@.'⍳⊃⊃g   ⍝ Get the next-grid corresponding to the character under the IP
                     ⍝ If that character is 0 or 1, then the pointer has walked off the edge,
                     ⍝ This causes an IndexError since 7='#\/!@.'⍳1, and the list of
                     ⍝ stack changes has only 6 elements
                     ⍝ If the stack is empty, and there is no current grid,
                     ⍝ then it would also try to get the 7th elements, also raising the IndexError
    (1↓⍵),⍨⊃        ⍝ Add the next grid to the beginning (top) of the popped stack