Bitforth

How much Forth do you really need for Turing completeness? Surprisingly little.

Bitforth is an ultra-minimal subset of Forth that achieves Turing completeness using only:

• A data stack and a call stack
• Literals 0, 1, -1
• Colon definitions with calls/returns (including recursion)
• Multi-way branches (CASE/OF)

By using the data stack as a queue and employing a recursive technique to enqueue bits at the bottom of the data stack, Bitforth can simulate any tag system, and therefore any Turing machine.

In particular, Bitforth does not use the >R and R> words of Forth which can implement a two-stack pushdown automaton by providing direct access to the call stack as a second data stack. Instead, Bitforth manipulates the call stack only through standard calls and returns.

Furthermore, if the data is self-delimited, it should be possible to omit the -1 literal entirely and rely solely on 0 and 1, employing IF/ELSE/THEN in place of CASE.

Queue Implementation

To represent a queue, we store bits on the stack and terminate them with a sentinel value of -1. For example, the stack

(BOTTOM) -1 0 1 1 0 1 (TOP)

represents the queue [0, 1, 1, 0, 1].

Dequeuing a bit from the top is done with a CASE test, as usual. To enqueue a bit at the bottom, we use the word append defined thus:

: append ( -1 ... b -- -1 b ... )
  CASE
    0 OF
      CASE
        0 OF 0 recurse 0 ENDOF
        1 OF 0 recurse 1 ENDOF
       -1 OF -1 recurse 0 ENDOF
      ENDCASE
    ENDOF
    1 OF
      CASE
        0 OF 1 recurse 0 ENDOF
        1 OF 1 recurse 1 ENDOF
       -1 OF -1 recurse 1 ENDOF
      ENDCASE
    ENDOF
    -1 OF -1
    ENDOF
  ENDCASE
;

Each recursive call pushes its return address onto the call stack, encoding a bit for later recovery. This way the entire data stack contents are saved onto the call stack, while the bit to append is propagated to the bottom of the stack (marked by -1) and is inserted there. As calls return, each restores its corresponding bit, recovering the queue contents on the data stack with the newly appended bit now at the bottom of the stack.

Simulating tag systems

To simulate a tag system in Bitforth, encode the alphabet symbols as distinct bit strings, and write a word that:

1. Uses nested CASE statements to read and remove the first symbol in the queue.
2. Drops a fixed number of symbols at the head (again using CASE).
3. Appends a bit pattern via append
4. Repeats by recursion.

Reversibility

The append word above is designed to be step-by-step reversible to support RTM-universality (Axelsen and Glück). The discussion here, however, focuses on TM-universality.