Foo machine

Foo machine is a hypothetical machine created by Leo Tenenbaum in order to demonstrate that determining whether a simpler machine than the Turing-machine halts is possible.

Reference

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.