43
9
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
5Just 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? – V. Courtois – 2019-08-09T06:56:51.137
5@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. – Leo Tenenbaum – 2019-08-09T07:09:14.803
Okay, good to know. Thanks! I'll have to write an answer using this now. Or something else, I'm still thinking. – V. Courtois – 2019-08-09T07:37:17.250
Oh no, if I do it like that I have to keep track of all the states (first non-halting test case) because it loops with a known position which is not the start position. – V. Courtois – 2019-08-09T08:53:36.327
In the end, I still did it this way.
– V. Courtois – 2019-08-09T09:22:44.5403Suggested test case:
1 2 h 42
(does not halt) – Arnauld – 2019-08-09T11:34:53.280Is there a maximum value for the step-size? Or can it (theoretically) be arbitrary large? – Kevin Cruijssen – 2019-08-09T11:50:48.477
@KevinCruijssen The step size can be any integer (but you can ignore integer overflow). – Leo Tenenbaum – 2019-08-09T11:56:37.360
Thanks @Arnauld you just broke my answer xD. Good thing I haven't published it yet. – IQuick 143 – 2019-08-09T11:57:03.507
6Suggested test case:
3 2 1 1 4 h
. This one halts but requires more iterations than twice the number of elements. – Arnauld – 2019-08-09T12:32:20.370Suggested trivial test case
2 h
, which does not halt. – Jitse – 2019-08-09T14:56:24.73010Suggested 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. – Magma – 2019-08-09T15:13:36.987