42
\$\begingroup\$

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 , 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
\$\endgroup\$
  • 5
    \$\begingroup\$ Just so I'm sure, about the algorithm to resolve this. I'm not that of an algorithm master so I prefer asking before going in the wrong direction. Will a non-halting Foo machine always get back to its exact original state? Or are there "chaotic-behaviored" non-halting machines? \$\endgroup\$ – V. Courtois Aug 9 at 6:56
  • 5
    \$\begingroup\$ @V.Courtois All non-halting Foo machines will end up in a loop of states, because there are only finitely many possible states a Foo machine can be in (there are n possible places the instruction pointer can be, and 2^n possible tape configurations). Each state has one and only one "next state". So, if a Foo machine ends up back in a state it's already been in, it'll just keep looping. Because there are only finitely many states, it can't keep chaotically jumping around between states because it'll end up eventually going to one it's already been in. \$\endgroup\$ – Leo Tenenbaum Aug 9 at 7:09
  • 3
    \$\begingroup\$ Suggested test case: 1 2 h 42 (does not halt) \$\endgroup\$ – Arnauld Aug 9 at 11:34
  • 6
    \$\begingroup\$ Suggested test case: 3 2 1 1 4 h. This one halts but requires more iterations than twice the number of elements. \$\endgroup\$ – Arnauld Aug 9 at 12:32
  • 10
    \$\begingroup\$ Suggested extra-long test case: 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, which halts after 786430 steps. \$\endgroup\$ – Magma Aug 9 at 15:13

15 Answers 15

11
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Golfed your code by 2 bytes: tio.run/… \$\endgroup\$ – IQuick 143 Aug 9 at 6:09
  • \$\begingroup\$ @IQuick143 Nice catch, thanks \$\endgroup\$ – Embodiment of Ignorance Aug 9 at 6:27
  • \$\begingroup\$ I'm not sure if there are any edge cases for which it won't work, but without breaking any of the current test cases you could replace 1<<f with 2*f to save a byte. \$\endgroup\$ – Kevin Cruijssen Aug 9 at 9:13
  • 1
    \$\begingroup\$ 77 bytes with horrible LINQ magic and Arnauld's fix. I have no idea how does this solution work, so I may have broken it. \$\endgroup\$ – someone Aug 9 at 12:08
  • 1
    \$\begingroup\$ 63 bytes via a normal sane 1-byte golf and changing IO to error/no error. Link to link \$\endgroup\$ – someone Aug 9 at 13:13
7
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ OK, I'll bite: how do you know x+x is enough? \$\endgroup\$ – Neil Aug 9 at 11:12
  • 4
    \$\begingroup\$ @Neil It's actually not enough. A counter-example is [ 3, 2, 1, 1, 4, 0 ], which does halt in more than 12 iterations. \$\endgroup\$ – Arnauld Aug 9 at 12:33
  • 1
    \$\begingroup\$ @Jitse len(x)*x would not work. For instance, [8,7,6,5,7,4,0,3,6] halts in more than \$9^2\$ iterations. \$\endgroup\$ – Arnauld Aug 9 at 14:59
  • 2
    \$\begingroup\$ Isn't 2**len(x) still a bit short of the maximum? I calculate the number of states as n*(2**n) (with n=len(x)-1). \$\endgroup\$ – O.O.Balance Aug 9 at 15:07
  • 1
    \$\begingroup\$ @O.O.Balance I see what you mean, since each state can have a pointer in each cell... however, I feel likes there's some other limit applied by the fact that each cell can only possibllly transition to two other cells. As a side note: nothing in the challenge says there has to be a halting state in the input \$\endgroup\$ – Jo King Aug 9 at 15:24
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Save a byte by rotating by all the entries and then just keeping the first result: N1¦ṙ⁸ḢƊÐLḢẸ \$\endgroup\$ – Jonathan Allan Aug 9 at 16:58
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @JoKing 109 bytes by doing the variable assignments in the first line. \$\endgroup\$ – Jitse Aug 9 at 7:10
  • \$\begingroup\$ 92 bytes by changing tuple conversion to starred expansion, not starting with an empty set and rephrasing the while condition. \$\endgroup\$ – Jitse Aug 9 at 7:51
  • \$\begingroup\$ @JoKing Damn, I never learn :p. 93 bytes then. \$\endgroup\$ – Jitse Aug 9 at 7:59
  • \$\begingroup\$ 91 bytes \$\endgroup\$ – Jitse Aug 9 at 15:07
  • \$\begingroup\$ @JoKing thanks! \$\endgroup\$ – HyperNeutrino Aug 9 at 18:26
5
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ The state of the Foo machine also includes the location of the pointer, not just the signs of each cell. \$\endgroup\$ – Magma Aug 9 at 15:29
  • 1
    \$\begingroup\$ Sketch of a proof for a Foo machine with tape a_1 ... a_n 0 . Consider an n-cube of the signs of each cell with directed edges (= an iteration of Foo) between vertices (= states), visiting the same vertex via any loop of edges will result in the IP being in the same position it started with. Proof: In a loop, the IP travels in each dimension an even number of times, ie the IP changes by k×(a_j + (-a_j)) % n ≡ 0 for each dimension, hence it always returns to the same position, only ever seeing 1 state out of n states for each vertex, ie a total max of 2^n states (= number of vertices of cube). \$\endgroup\$ – Kritixi Lithos Aug 9 at 17:54
  • \$\begingroup\$ Just an empirical result, but brute-forcing the longest cycle among halting machines on a tape of length \$n\$ suggests that a tighter upper bound is \$\lfloor2^n.log(n)/n\rceil\$. \$\endgroup\$ – Arnauld Aug 10 at 12:34
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Oh nice, so that's what your Jelly answer does! Great use of the rotate and ć! I was waiting for an explanation in the hope to golf my answer, but you beat me to it, haha. ;p -1 byte by doing the same golf as my answer though: g·F to «v (Try it online.) \$\endgroup\$ – Kevin Cruijssen Aug 9 at 9:39
  • \$\begingroup\$ And one additional -1 by using ©® instead of the DŠs: «vć©(š®._}®_ (Try it online.) \$\endgroup\$ – Kevin Cruijssen Aug 9 at 9:43
  • \$\begingroup\$ As Arnauld noted on your Python answer, looping two times the length isn't enough. So you can change the «v to goF. \$\endgroup\$ – Kevin Cruijssen Aug 9 at 14:04
  • \$\begingroup\$ @KevinCruijssen thanks \$\endgroup\$ – Nick Kennedy Aug 9 at 15:44
3
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Just wondering, are you allowed to take the length as an additional argument? The default for IO post on meta doesn't say so, and the only reason my second answer takes a length is because it takes in a int*(from codegolf.meta.stackexchange.com/a/13262/84206) \$\endgroup\$ – Embodiment of Ignorance Aug 10 at 0:26
  • \$\begingroup\$ @EmbodimentofIgnorance Ah, when I saw your answer I assumed there was some kind of of meta rule that allowed the length to be taken as additional input, but that only applies to pointers. Thanks for letting me know. I've removed the length parameter (but still use the error/no-error to determine the result). \$\endgroup\$ – Kevin Cruijssen Aug 10 at 8:25
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 28 bytes

≔⁰ηFX²L諧≔θ籧θη≧⁻§θη绬§θη

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.

FX²Lθ«

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.