bfturing

A Turing machine simulator in Brainfuck.

Requirements

The program assumes that EOF is signaled by setting the cell to -1. The program uses $ to "crash"; if the interpreter does not implement this symbol, it loops indefinitely. (Program contains e.g. [$].)

Usage

The input to the program is the Turing machine description. This description consists of a set of rules, where each rule consists of 5 characters: the state and symbol that describe the current state and current symbol under the tape head, the new state, the written symbol, and the direction to move in.

The input should be no more than a number of such 5-character sequences; in particular, do not append a newline. Usage is e.g. as follows.

echo -n 'S q1>S1H*=q S0<' | bfinter_simple bfturing.bf

where bfinter_simple is one of the interpreters in this repository. This Turing machine has two states (S and q) and three rules: (S, blank) -> (q, 1, right), (S, 1) -> (Halt, *, stay) and (q, blank) -> (S, 0, left).

The head movements "left", "stay" and "right" are denoted with <, = and >, which conveniently have three consecutive ASCII values. Tape symbols can be any byte, and states can be any byte unequal to 0xff (since that indicates EOF). Execution halts normally when the state H is reached. If the machine runs over the left end of the tape or no rule matches the current machine state, the program crashes using [$].