Sloopy

Sloopy is a pedestrian C-like Turing-complete language intended to be used in proofs of Turing-completeness.

Overview

There are four global variables in every Sloopy program:

• done, a boolean, initially false
• state, an unbounded integer, initially 0
• head, an unbounded integer, initially 0
• tape, an unbounded array of integers, intially filled with 0's

A Sloopy program always takes the following form:

while (!done) {
  if (state == 0) {
    if (tape[head] == 0) {
      ...
    } else if (tape[head] == 1) {
      ...
    } /* etc */
  } else if (state == 1) {
    if (tape[head] == 0) {
      ...
    } else if (tape[head] == 1) {
      ...
    } /* etc */
  } /* etc */
}

The template shown above is prescriptive. The program must begin with while (!done) {, it must consist of a list of equality comparisons against state, and each of those must consist of a list of equality comparisons against tape[head].

The etcs indicate that these if-else-if chains can be extended to be as long as desired (e.g. 200 states, 200 possible tape cell values.)

The ...s are placeholders for a list of assignments that change the state. These assignments are drawn from the following, where c represents an arbitrary literal integer constant, and 1 is literally the number one:

tape[head] = c;
head += 1;  /* or */  head -= 1;
state = c;
done = TRUE;  /* optional */

The assignments to tape, head, and state must appear, in this order, in every assignment block.

The following EBNF grammar states the structure of Sloopy programs more formally.

Sloopy          ::= "while" "(" "!" "done" ")" "{" StateTests "}".
StateTests      ::= StateTest {"else" StateTest}.
StateTest       ::= "if" "(" "state" "==" IntLit ")" "{" CellTests "}".
CellTests       ::= CellTest {"else" CellTest}.
CellTest        ::= "if" "(" "tape" "[" "head" "]" "==" IntLit ")" "{" Assigments "}".
Assignments     ::= TapeAssignment ";" HeadAssignment ";" StateAssignment ";" [DoneAssignment ";"].
TapeAssignment  ::= "tape" "[" "head" "]" "=" IntLit.
HeadAssignment  ::= "head" ("+=" "1" | "-=" "1").
StateAssignment ::= "state" "=" IntLit.
DoneAssignment  ::= "done" "=" "TRUE".

Semantics

The semantics are close enough to C's that an program could, after checking that the input Sloopy program is syntactically correct, simply

• output a prelude defining the global variables (and defining TRUE to be 1) and the start of main,
• output the input Sloopy program,
• output a tiny postlude

and send the whole thing off to a C compiler to generate an executable, and it would be a semi-reasonable implementation of Sloopy.

Computational class

Sloopy is Turing-complete. It should be obvious that every Turing machine that consists of a single loop can be translated to a Sloopy program; and it is also the case that every Turing machine can be simulated by some Turing machine with a single loop (see, for example, page 281 of Computation: Finite and Infinite Machines.)

Variations

Sloopy can also be translated to various restricted versions of Sloopy, meaning these variations are also Turing-complete. The translation is usually mostly straightforward, and quite dull. Some of these variations include:

• head is an unbounded nat
• tape cells contain unbounded nats
• only tape modifications are tape[head] += 1 and tape[head] -= 1 (brainfuck)
• only tape modification is tape[head] = 1 - tape[head] (Boolfuck)
• done = TRUE can only appear in a final `else` block

Sloopy can also be translated to various relaxations of Sloopy (for example, allowing head += c) but these are less interesting in this context as they are generally a superset of Sloopy and thus the translation is trivial.

These variations may also be translated back to Sloopy. From the perspective of translation though this doesn't tell us anything about their Turing-completeness (lots of non-Turing-complete languages may be translated to Sloopy.)

Tape-only Sloopy

One variation of particular interest to the author is Sloopy without the state variable. Instead the state is stored on the tape (in the odd cells), and left and right head shifts are actually shifts by two cells (so always landing on an even cell) which copy the new state into the adjoining odd cell.

To show that Tape-only Sloopy is Turing-complete, we must show that every Sloopy program can be translated to a Tape-only Sloopy program.

In any given branch, we know what state we are in, and what state we want to be in next. For example,

if (state == 3) {
  if (tape[head] == 0) {
    /* We know we are in state 3 here */
    tape[head] = 1;
    head += 1;
    state = 4;
  } else /* etc */
}

We can replace all head += 1 with head += 2, and replace all head -= 1 with head -= 2, and this preserves behaviour of the program.

We can then retrieve the state from the tape and write the new state back to the tape:

if (tape[head + 1] == 3) {
  if (tape[head] == 0) {
    tape[head] = 1;
    head += 2;
    tape[head + 1] = 4;
  } else /* etc */
}

We can in fact say that Tape-only Sloopy programs must all have this general form. The grammar of Tape-only Sloopy is the same as the grammar of Sloopy, save for the following three productions which are slightly modified.

StateTest       ::= "if" "(" "tape" "[" "head" "+" "1" "]" "==" IntLit ")" "{" CellTests "}".
HeadAssignment  ::= "head" ("+=" "2" | "-=" "2").
StateAssignment ::= "tape" "[" "head" "+" "1" "]" "=" IntLit.

And since every Sloopy program can be translated to a corresponding Tape-only Sloopy program, Tape-only Sloopy is Turing-complete.