Does this Foo machine halt?

Question

Determining whether a Turing machine halts is well known to be undecidable, but that's not necessarily true for simpler machines.

A Foo machine is a machine with a finite tape, where each cell on the tape has an integer or the halt symbol h, e.g.

2 h 1 -1

The instruction pointer starts by pointing to the first cell:

2 h 1 -1
^

At every step, the instruction pointer moves forward by the number it points to, then negates that number. So, after one step, it would move forward 2 cells, and turn the 2 into a -2:

-2 h 1 -1
     ^

The Foo machine keeps doing this until the instruction pointer is pointing to the halt symbol (h). So, here is the full execution of this program:

2 h 1 -1
^

-2 h 1 -1
     ^

-2 h -1 -1
         ^

-2 h -1 1
      ^

-2 h 1 1
   ^

The tape is also circular, so if the instruction pointer moves off of one side of the tape, it goes to the other side, e.g.:

3 h 1 3
^
-3 h 1 3
       ^
-3 h 1 -3
     ^
-3 h -1 -3
         ^
-3 h -1 3
 ^
3 h -1 3
  ^

One interesting thing about these Foo machines is that some do not halt, e.g.:

1 2 h 2
^
-1 2 h 2
   ^
-1 -2 h 2
        ^
-1 -2 h -2
    ^
-1 2 h -2
        ^
-1 2 h 2
   ^

This program will continue looping in those last four states forever.

So, write a program which determines if a Foo machine halts or not! You can use any (reasonable) input format you like for the Foo machines, and you can choose to use 0 as the halt symbol. You can use any two distinct outputs for the case where it does halt and the case where it doesn't. Your program must, of course, output an answer in a finite amount of time for all valid inputs.

This is code-golf, so try to make your program as short as possible!

Test cases

2 h 1 -1
Halts
3 h 1 3
Halts
h
Halts
1 1 1 1 h
Halts
2 1 3 2 1 2 h
Halts
3 2 1 1 4 h
Halts
1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36
Halts

2 h
Does not halt
1 2 h 2
Does not halt
8 1 2 3 3 4 8 4 3 2 h
Does not halt
1 2 4 3 h 2 4 5 3
Does not halt
3 1 h 3 1 1
Does not halt
1 2 h 42
Does not halt

Answer 1

C# (Visual C# Interactive Compiler), 71 bytes

x=>{for(int i=0,k=0,f=x.Count;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;i/=x[k];}

Try it online!

I don't know if the following is valid, since it requires a custom delegate with a signature of unsafe delegate System.Action<int> D(int* a); and has to be wrapped in an unsafe block to be used, but here it is anyways:

C# (.NET Core), 64 bytes

x=>f=>{for(int i=0,k=0;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;k/=x[k];}

Try it online!

This function takes in an int* and returns a Action; in other words, it is a curried function. The only reason I use pointers is because of codegolf.meta.stackexchange.com/a/13262/84206, which allows me to save bytes by already having a variable already defined with the length of the array.

Saved 9 bytes thanks to @someone

Answer 2

Jelly, 15 11 bytes

N1¦ṙ⁸ḢƊÐLḢẸ

Try it online!

A monadic link that takes the input as a list of integers using 0 to mean halt. Returns 0 for halting inputs and 1 for those that don’t halt.

Avoids the issue of needing to work out number of iterations because of the use of ÐL which will loop until no new result seen.

Thanks to @JonathanAllan for saving a byte!

Explanation

      ƊÐL   | Loop the following as a monad until the result has been seen before:
N1¦         | - Negate the first element
   ṙ⁸       | - Rotate left by each of the elements
     Ḣ      | - Take just the result of rotating by the first element
         Ḣ  | Finally take the first element
          Ẹ | And check if non-zero

Answer 3

Python 3, 63 89 bytes

def f(x):
 for i in range(2**len(x)):a=x[0];x[0]=-a;b=a%len(x);x=x[b:]+x[:b]
 return a==0

Try it online!

Also works for Python 2; a byte can be saved in Python 2 by replacing return with print and having the function print to stdout instead of returning. R turns True for halting and False for non-halting.

Thanks to @Neil and @Arnauld for noting that I needed to check longer for halting. Thanks to @Jitse for pointing out a problem with [2,0]. Thanks to @mypetlion for noting that the absolute of the tape values could exceed the tape length.

Answer 4

Python 3, 91 bytes

def f(a):
	s={0,};i=0
	while{(*a,)}-s:s|={(*a,)};a[i]*=-1;i-=a[i];i%=len(a)
	return a[i]==0

Try it online!

-40 bytes thanks to JoKing and Jitse

Answer 5

Perl 6, 46 43 36 bytes

{$_.=rotate(.[0]*=-1)xx 2**$_;!.[0]}

Try it online!

Represents halt by 0 and returns true if the machine halts. This repeats the logic 2**(length n) times, where if the pointer ends up on the halt cell, it stays there, otherwise it will be on a non-halt cell. This works because there are only 2**n possible states (ignoring halt cells) for the Foo machine to be in, since each non-halt cell has only two states. Okay yes, there are states than that, but due to the limited possible transitions between pointers (and therefore states) there will be less than 2**$_ states... I think

Explanation

{                                  }  # Anonymous codeblock
                     xx 2**$_         # Repeat 2**len(n) times
            .[0]*=-1                  # Negate the first element
 $_.=rotate(        )                 # Rotate the list by that value
                             ;!.[0]   # Return if the first element is 0

Answer 6

05AB1E, 14 13 bytes

goFć©(š®._}®_

Try it online!

Takes the input as a list of integers with 0 as the halting instruction. Returns 1 for halting and 0 for not halting.

Thanks to @KevinCruijssen for saving 2 bytes!

Answer 7

Java 8, 78 79 73 bytes

a->{int k=0,l=a.length,i=0;for(;i++<1<<l;k%=l)k-=(a[k]*=-1)%l-l;k/=a[k];}

Straight-forward port of @EmbodimentOfIgnorance's C# .NET answer, so make sure to upvote him!
Thanks to @Arnauld for finding two bugs (which also applies to some other answers).

Results in an java.lang.ArithmeticException: / by zero error when it's able to halt, or no error if not.

Try it online.

Explanation:

a->{                   // Method with integer-array as parameter and no return-type
  int k=0,             //  Index integer, starting at 0
      l=a.length,      //  The length `l` of the input-array
  i=0;for(;i++<1<<l;   //  Loop 2^length amount of times:
          k%=l)        //    After every iteration: take mod `l` of `k`
    k-=                //   Decrease `k` by:
       (a[k]*=-1)      //    Negate the value at index `k` first
                 %l    //    Then take modulo `l` of this
                   -l; //    And then subtract `l` from it
                       //  (NOTE: the modulo `l` and minus `l` are used for wrapping
                       //  and/or converting negative indices to positive ones
  k/=a[k];}            //  After the loop: divide `k` by the `k`'th value,
                       //  which will result in an division by 0 error if are halting

Answer 8

Haskell, 79 bytes

s x|m<-length x,let g(n:p)=(drop<>take)(mod n m)(-n:p)=iterate g x!!(2^m)!!0==0

Try it online!

Returns True for halting machines, and False otherwise. Input in the form of a list, with 0 representing a halting state.

Assumes a version of GHC greater than 8.4 (released Feb 2018).

Answer 9

Charcoal, 28 bytes

≔⁰ηＦＸ²Ｌ諧≔θ籧θη≧⁻§θη绬§θη

Try it online! Link is to verbose version of code. Outputs using Charcoal's default Boolean output, which is - for true and nothing for false. Explanation:

≔⁰η

Initialise the instruction pointer.

ＦＸ²Ｌθ«

Loop as many times as there are theoretically possible states.

§≔θ籧θη

Negate the value at the instruction pointer.

≧⁻§θηη

Subtract the new value from the instruction pointer. Charcoal's array accesses are cyclic so this automatically emulates Foo's circular tape.

»¬§θη

At the end of the loop, output whether the program halted.

Answer 10

JavaScript (Node.js), 71 67 bytes

x=>{for(p=l=x.length,i=2**l;i--;)p+=l-(x[p%l]*=-1)%l;return!x[p%l]}

Basically the same as @EmbodimentOfIgnorance's C# .NET answer

4 byte save thanks to @Arnaud

Try it online!

JavaScript (Node.js), 61 bytes

x=>{for(p=l=x.length,i=2**l;i--;p+=l-(x[p%l]*=-1)%l)x[p%l].f}

This version uses undefined as a halting symbol and throws a TypeError: Cannot read property 'f' of undefined when the machine halts and terminates quietly when the machine doesn't halt.

Try it online!

Answer 11

Scala, 156 bytes

Still golfable IMO, but I'm okay with it for now. Returns 0 for non-halting Foos and 1 for halting Foos. Takes the input in a as an Array[Int], so h is taken as 0.

var u=Seq[Array[Int]]()//Keep track of all states
var i=0//Index
while(u.forall(_.deep!=a.deep)){if(a(i)==0)return 1//Check if we are in a previously encountered step ; Halt
u:+=a.clone//Add current state in the tracker
var k=i//Stock temp index
i=(a(i)+i)%a.length//Move index to next step
if(i<0)i+=a.length//Modulus operator in Scala can return a negative value...
a(k)*=(-1)}//Change sign of last seen index
0//Returns 0 if we met a previous step

It is pretty long to run (around 4 seconds for all the test cases) because of the multiple full-array lookups I did, plus the .deep that create copies... But you can still try it online.

Answer 12

Stax, 11 bytes

Ç₧┬òE▐tµ|⌡1

Run and debug it

It takes input in the form of an integer array, with 0 representing halt.

It outputs 1 for a halting and 0 for a non-halting machine.

Answer 13

Perl 5 -ap, 88 bytes

for(;$F[$i]&&!$k{"$i|$F[$i]"};$i=($i+$F[$i])%@F){$k{"$i|$F[$i]"}=1;$F[$i]*=-1}$_=!$F[$i]

Try it online!

Answer 14

Pyth, 12 bytes

!hu.<+_hGtGh

Test suite!

Uses the straight-forward approach. Recurse until we see the list twice in an identical state. For programs that halt, the list will eventually have a leading 0 because that's where the recursion stops. For programs that don't halt, the list won't begin with the 0, but rather be in a state from which the process would be periodic and therefore the Foo machine wouldn't halt.

Answer 15

Attache, 40 bytes

Not@&N@Periodic[{On[0,`-,_]&Rotate!_@0}]

Try it online!

Explanation

{On[0,`-,_]&Rotate!_@0}

This performs a single iteration of the Foo machine; it negates the first member, then rotates the array by the (original, non-negated) first element of the array.

Periodic will apply this function until a duplicate result is accumulated. A machine either halts, or goes into a trivial infinite loop. If it halts, the first element will be 0. Otherwise, it will be non-zero.

&N is a golfy way of obtaining the first element of a numeric array. Then, Not returns true for 0 (halting machines) and false for anything else (non halting machines).