Halting Problem for Simplified Hexagony

Question

Introduction

Decide whether a Hexagony program composed solely of the characters .)_|\/><@ will halt using least bytes.

Challenge

Hexagony is a language developed by Martin Ender in which the source code is presented in the form of a hexagon. It has been extensively used in PPCG and there has been many impressive submissions using this language. Your task is to take a Hexagony program in its short form (one liner) that contains the characters .)_|\/><@ only and decide whether it will halt.

Since a challenge should be self-contained (per comment by @Mr.Xcoder), the language specifications related to this challenge is given in the appendix. If there is anything unclear you can refer to the document itself, which I believe is pretty clear.

You can use a set of output values as truthy and another set as falsy provided that the intersection of the two sets is empty, and at least one of them should be finite (Thanks@JonathanAllan for fixing the loophole). Please indicate in the answer which sets you will use.

You can use TIO to check whether a Hexagony program halts within 60 seconds.

Bonus point for solutions in Hexagony!

Test cases

Input
Hexagonal Form
Output

.
.
False

.....@
 . .
. . .
 @ .
False

)\..@
 ) \
. . @
 . .
True

.\|<..@
 . \
| < .
 . @
False

)\|<..@
 ) \
| < .
 . @
True

..\...@|.<.\....>._ 
  . . \
 . . . @
| . < . \
 . . . .
  > . _
False

Specs

• The input is a string or an array of characters of a Hexagony program in its short form

• The length of the program will be less than or equal to 169 characters (side length of 8)

• To reiterate, please clarify the truthy/falsy value sets you use in the answer

• Your program should halt for all valid inputs. Halting with error is fine as long as a truthy/falsy value is written to stdout or its closest equivalent in your language. (Thanks @moonheart08 for pointing out this)

• This is code-golf, the lowest number of bytes wins.

• As usual, default loopholes apply here.

Appendix: Hexagony language specs related to this challenge

Overview

Source code

The source code consists of printable ASCII characters and line feeds and is interpreted as a pointy-topped hexagonal grid, where each cell holds a single-character command. The full form of the source code must always be a regular hexagon. A convenient way to represent hexagonal layouts in ASCII is to insert a space after each cell and offset every other row. A hexagon of side-length 3 could be represented as

  . . .
 . . . .
. . . . .
 . . . .
  . . .

Within the scope of this challenge, the source code is padded to the next centered hexagonal number with no-ops (.s) and rearranged it into a regular hexagon. This means that the spaces in the examples above were only inserted for cosmetic reasons but don't have to be included in the source code.

For example, abcdefgh and abcdef will be padded to

  a b c
 d e f g            a b
h . . . .   and    c d e  ,   respectively.
 . . . .            f .
  . . .

Control flow

Within the scope of this challenge, the IP of Hexagony start at the top left corner of the hexagon moving to the right. There are commands which let you change the directions of IP movement based on its current direction and the value in the memory.

The edges of the hexagon wrap around to the opposite edge. In all of the following grids, if an IP starts out on the a moving towards the b, the letters will be executed in alphabetical order before returning to a:

   . . . .          . a . .          . . k .          . g . .   
  a b c d e        . . b . .        . . j . .        . h . . a  
 . . . . . .      g . . c . .      . . i . . e      . i . . b . 
. . . . . . .    . h . . d . .    . . h . . d .    . j . . c . .
 f g h i j k      . i . . e .      . g . . c .      k . . d . . 
  . . . . .        . j . . f        f . . b .        . . e . .  
   . . . .          . k . .          . . a .          . f . .   

If the IP leaves the grid through a corner in the direction of the corner there are two possibilities:

-> . . . .   
  . . . . .  
 . . . . . . 
. . . . . . . ->
 . . . . . . 
  . . . . .  
-> . . . .   

If value in the memory is non-zero, the IP will continue on the bottom row. If it's zero, the IP will continue on the top row. For the other 5 corners, just rotate the picture. Note that if the IP leaves the grid in a corner but doesn't point at a corner, the wrapping happens normally. This means that there are two paths that lead to each corner:

      . . . . ->   
     . . . . .  
    . . . . . . 
-> . . . . . . .
    . . . . . . 
     . . . . .  
      . . . . ->

Memory model

In the scope of this challenge, the memory is a single cell containing an unbounded unsigned integer, and is initialized to zero before the start of the program.

Command list

The following is a reference of all commands relevant to this challenge.

• . is a no-op: the IP will simply pass through.
• @ terminates the program.
• ) increments the value in the memory

• _, |, /, \ are mirrors. They reflect the IP in the direction you'd expect. For completeness, the following table shows how they deflect an incoming IP. The top row corresponds to the current direction of the IP, the left column to the mirror, and the table cell shows the outgoing direction of the IP:

  cmd   E SE SW  W NW NE
  
   /   NW  W SW SE  E NE
   \   SW SE  E NE NW  W
   _    E NE NW  W SW SE
   |    W SW SE  E NE NW
  

• < and > act as either mirrors or branches, depending on the incoming direction:

  cmd   E SE SW  W NW NE
  
   <   ?? NW  W  E  W SW 
   >    W  E NE ?? SE  E
  

  The cells indicated as ?? are where they act as branches. In these cases, if the value in the memory is non-zero, the IP takes a 60 degree right turn (e.g. < turns E into SE). If the value is zero, the IP takes a 60 degree left turn (e.g. < turns E into NE).

Example

This is a program taken from the test case: )\..@. Its full form is

 ) \
. . @
 . .

And here is how it executes before coming to a halt. To make it terse I will number the cells in the hexagon and use the notation 1E) if the IP is currently at cell 1, executes the instruction ) and is heading east after execution of the instruction.

 1 2
3 4 5
 6 7

The IP starts from cell 1 heading east. The memory cell was initialized to 0.

1. 1E), memory cell is now 1
2. 2\SW, the IP is reflected
3. 4SW., no-op.
4. 6SW., no-op. Then it branches, as the memory cell is nonzero, it wraps to cell 1 instead of cell 5.
5. 1SW), memory cell is now 2.
6. 3SW., no-op.
7. 2E\, the IP is reflected then wrapped.
8. 3E., no-op.
9. 4E., no-op.
10. 5E@, the program halts.

---

_{Credits to @MartinEnder, @FryAmTheEggman and @Nitrodon for their helpful comments.}

_{@FryAmTheEggman brought the issue of decidablity of halting problems of programs with both ( and ) to attention.}

_{@MartinEnder pointed out that if ( and ) cannot appear in the same program then ( can be dropped entirely.}

_{@Nitrodon gave a simple proof for the decidability of the halting problem for programs with both ( and ).}

Answer 1

APL (Dyalog Unicode), 616 bytes^SBCS

{l←3 3 1⊥⍨s←⌊.5+.5*⍨3÷⍨¯1+≢⍵
X d n←(s 0)(2 0)0
'@'∊⍵{V W←X+d⊢←⍎'d⊣n∨←1' 'd×1 ¯1' 'dׯ1 1' '(¯1 ¯1)(1 1)(2 0)(¯2 0)d⊃⍨(2 0)(¯2 0)(¯1 ¯1)(1 1)⍳⊂d' '(¯1 1)(1 ¯1)(2 0)(¯2 0)d⊃⍨(2 0)(¯2 0)(¯1 1)(1 ¯1)⍳⊂d' '(1,¯1+2×n)(¯2 0)(-d)⊃⍨2 ¯1⍳⊃d' '(¯1,1-2×n)(2 0)(-d)⊃⍨¯2 1⍳⊃d' 'd'⊃⍨')_|/\<>'⍳o←X⌷⍉(l↑⍺)@{(((¯3×s)≤-)∧(s≥-)∧((5×s)≥+)∧(s≤+)∧0=2|s++)/¨⍵}⍳1+2 4×s
⍵,o⊣X⊢←(s×1,2×n)(s×3,2×~n)(s×(1+3×n),2-n)(s×(3×n),1+n)(s×(4-3×n),~n)(s×(3-3×n),n)(X+3 1×s)(X+0 2×s)(X+¯3 1×s)(X-3 1×s)(X×1 0)(X+3 ¯1×s)(V W)⊃⍨(V=2+4×s)(V=¯2)((W<0)∧V<s)((W<0)∧V>3×s)((W>2×s)∧V<s)((W>2×s)∧V>3×s)(s>V+W)(W<0)((3×s)<V-W)((5×s)<V+W)(W>2×s)(s<W-V)⍳1}⍣(12×l)⊢''}

Try it online!

The function accepts a Simplified Hexagony source code as a character vector, and returns 1 if @ is included in the first 12 * full program size instructions run, 0 otherwise.

Uses the property pointed out by user202729, which is

Theorem: If a Simplified Hexagony doesn't halt after (full program size) * 12 steps (= 12 * ((side length) * (side length - 1) * 3 + 1)), it will run forever.

Simple proof: A Simplified Hexagony program can have "full program size=N" PC positions × 6 directions × 2 memory states (zero or nonzero) distinct internal states. If the program doesn't halt within that many steps, it leads to 12N+1th internal state which is identical to some previous state (by pigeonhole principle). This means the program has a cycle in the internal state, so it never terminates.

Other than that, it runs the Hexagony code very literally, with a small number trick that using side length - 1 as a variable allows cleaner expressions here and there.

Ungolfed & How it works

f←{
  ⍝ length of the input program
  l←≢⍵

  ⍝ side length - 1
  side←⌊.5+.5*⍨3÷⍨l-1

  ⍝ full program length
  full←side⊥3 3 1

  ⍝ pad the input program with spaces
  p←full↑⍵

  ⍝ create a dummy grid of the size of the full hexagon grid
  grid←⍳1+2 4×side

  ⍝ replace the appropriate positions of the grid with the padded program
  grid←p@{(((¯3×side)≤-)∧(side≥-)∧((5×side)≥+)∧(side≤+)∧0=2|side++)/¨⍵}grid

  ⍝ initialize the positions(x y), directions(dx dy), memory state(n) and the PC trajectory(t)
  x y dx dy n t←side 0 2 0 0 ''

  ⍝ run the program (12×full) steps and check if the trajectory contains a '@'
  '@'∊t⊣{

    ⍝ extract the opcode from the grid
    op←grid[y;x]

    ⍝ append to the trajectory
    t,←op

    ⍝ classify the op so that we can choose which code fragment to run
    idx←')_|/\<>'⍳op

    ⍝ specify the code fragments for the opcodes (which includes dummy '⍬' for no-op)
    fns←'n∨←1' 'dy×←¯1' 'dx×←¯1' 'dx dy⊢←(¯1 ¯1)(1 1)(2 0)(¯2 0)(dx dy)⊃⍨(2 0)(¯2 0)(¯1 ¯1)(1 1)⍳⊂dx dy'
    fns,←⊂'dx dy⊢←(¯1 1)(1 ¯1)(2 0)(¯2 0)(dx dy)⊃⍨(2 0)(¯2 0)(¯1 1)(1 ¯1)⍳⊂dx dy'
    fns,←'dx dy⊢←(1,¯1+2×n)(¯2 0)(-dx dy)⊃⍨2 ¯1⍳dx' 'dx dy⊢←(¯1,1-2×n)(2 0)(-dx dy)⊃⍨¯2 1⍳dx' '⍬'

    ⍝ choose the code fragment, run it, and move the PC one step forward
    x2 y2←x y+dx dy⊣⍎idx⊃fns

    ⍝ check for boundary conditions (first 6 are "branching" outs, next 6 are non-branching outs)
    idx2←(x2=2+4×side)(x2=¯2)((y2<0)∧x2<side)((y2<0)∧x2>3×side)((y2>2×side)∧x2<side)((y2>2×side)∧x2>3×side)(side>x2+y2)(y2<0)((3×side)<x2-y2)((5×side)<x2+y2)(y2>2×side)(side<y2-x2)⍳1

    ⍝ specify the code fragments for destination coordinates
    fns2←'side×1,2×n' 'side×3,2×~n' 'side×(1+3×n),2-n' 'side×(3×n),1+n' 'side×(4-3×n),~n' 'side×(3-3×n),n' 'x y+3 1×side' 'x,2×side' 'x y+¯3 1×side' 'x y-3 1×side' 'x 0' 'x y+3 ¯1×side' 'x2 y2'

    ⍝ run the selected opcode and return a dummy value via ⊢
    ⊢x y⊢←⍎idx2⊃fns2
  }⍣(12×full)⊢⍬
}

Answer 2

Python 3, 979 bytes

R=range
p=input()
l=len(p)
s=int((~-l/3)**.5+.5)
f=s*-~s*3+1
p+=(f-l)*'.'
o=0
g=[]
for i in[*R(s,s*2),*R(s*2,s-1,-1)]:
 w=[' ']*(s*4+1)
 for j in R(i+1):w[j*2+s*2-i]=p[o+j]
 g+=w,
 o+=i+1
x=s;y=0;u=2;v=0;n=0;t=''
M={'/':lambda e:{(2,0):(-1,-1),(-2,0):(1,1),(-1,-1):(2,0),(1,1):(-2,0)}.get(e,e),'\\':lambda e:{(2,0):(-1,1),(-2,0):(1,-1),(-1,1):(2,0),(1,-1):(-2,0)}.get(e,e),'<':lambda e:(1,2*n-1)if e[0]>1else(-2,0)if-1==e[0]else(-e[0],-e[1]),'>':lambda e:(-1,1-2*n)if-1>e[0]else(2,0)if e[0]==1else(-e[0],-e[1])}
exec("""
o=g[y][x];t+=o
if')'==o:n=1
elif'_'==o:v*=-1
elif'|'==o:u*=-1
elif o in M:u,v=M[o]((u,v))
X,Y=x+u,y+v
if X==s*4+2:X=s;Y=2*s*n
if X==-2:X=3*s;Y=2*s*(1-n)
if Y<0and X<s:X=s*(1+3*n);Y=s*(2-n)
if Y<0and X>s*3:X=s*3*n;Y=s*(1+n)
if Y>s*2and X<s:X=s*(4-3*n);Y=s*(1-n)
if Y>s*2and X>s*3:X=s*(3-3*n);Y=s*n
if X+Y<s:X=x+3*s;Y=y+s
if Y<0:X=x;Y=2*s
if X-Y>3*s:X=x-3*s;Y=y+s
if X+Y>5*s:X=x-3*s;Y=y-s
if Y>2*s:X=x;Y=0
if Y-X>s:X=x+3*s;Y=y-s
x,y=X,Y"""*12*f)
print('@'in t)

Try it online!

A full program. Prints True to stdout if the input program halts, False otherwise. Note that TIO version has four backslashes instead of two, in order to wrap the entire program in exec call.

Port of my own APL answer. The underlying algorithm is the same; it just uses different language-specific constructs to do the same thing. Golfing suggestions are welcome.

Ungolfed

p=input()  # one line of input program from stdin
l=len(p)   # length of the original program
s=int((~-l/3)**.5+.5)  # side length - 1
f=s*-~s*3+1            # length of the full program
p=p.ljust(f,'.')       # pad with dots

o=0        # offset in the original program for doing the layout
g=[]       # grid to format the program as a hexagon
# loop for generating hexagonal layout
for i in[*range(s,s*2),*range(s*2,s-1,-1)]:
 row=[' ']*(s*4+1)
 for j in range(i+1):row[j*2+s*2-i]=p[o+j]
 g+=[row]
 o+=i+1

# initial condition: position(x,y),direction(dx,dy),memory(n),trajectory(t)
x=s;y=0;dx=2;dy=0;n=0;t=''
# mirror maps just for '/\<>' because '_|' are relatively easy
M={
 '/':lambda e:{(2,0):(-1,-1),(-2,0):(1,1),(-1,-1):(2,0),(1,1):(-2,0)}.get(e,e),
 '\\':lambda e:{(2,0):(-1,1),(-2,0):(1,-1),(-1,1):(2,0),(1,-1):(-2,0)}.get(e,e),
 '<':lambda e:(1,2*n-1)if e[0]==2else(-2,0)if e[0]==-1else(-e[0],-e[1]),
 '>':lambda e:(-1,1-2*n)if e[0]==-2else(2,0)if e[0]==1else(-e[0],-e[1])
}

# run the loop f*12 times
for _ in range(f*12):

 # run the opcode
 op=g[y][x];t+=op
 if op==')':n=1
 elif op=='_':dy*=-1
 elif op=='|':dx*=-1
 elif op in M:dx,dy=M[op]((dx,dy))

 # one step forward
 x2,y2=x+dx,y+dy

 # handle "branching outs"
 if x2==s*4+2:x2=s;y2=2*s*n
 if x2==-2:x2=3*s;y2=2*s*(1-n)
 if y2<0and x2<s:x2=s*(1+3*n);y2=s*(2-n)
 if y2<0and x2>s*3:x2=s*3*n;y2=s*(1+n)
 if y2>s*2and x2<s:x2=s*(4-3*n);y2=s*(1-n)
 if y2>s*2and x2>s*3:x2=s*(3-3*n);y2=s*n

 # handle "non-branching outs"
 if x2+y2<s:x2=x+3*s;y2=y+s
 if y2<0:x2=x;y2=2*s
 if x2-y2>3*s:x2=x-3*s;y2=y+s
 if x2+y2>5*s:x2=x-3*s;y2=y-s
 if y2>2*s:x2=x;y2=0
 if y2-x2>s:x2=x+3*s;y2=y-s
 x,y=x2,y2

# finally, does the trajectory include '@'?
print('@'in t)