Turing-machine

Not to be confused with Turing machine.

Turing-machine is invented by User:A.

Syntax

All of the rules look like this:

currentCondition currentSymbol : nextCondition tapeHeadMoveDirection newSymbol

like:

Q1:E<0

If the condition (state) is Q, and the number (symbol) on the tape is 1, the change the condition into E, change the tape into 0, and move left. The four available conditions are:

Condition	Remarks
Q
E
O
F	Represents the final state; when this condition is encountered the Turing-machine halts.

Numbers are:

Symbol	Remarks
0	By default the tape's initial symbol.
1

They are on the tape, which is written onto it in input. When the Turing-machine halts, it prints the tape. Directions are:

Direction	Effect
<	Move the tape head one cell to the left.
>	Move the tape head one cell to the right.
-	Do not move the tape head at all.

Examples

Truth-machine (Beta version)

Q1:E>1
Q0:O>0
E0:E>1
O0:F<0

To make it print 1 forever, it changes the whole tape into 1s. But, that still proves that is has halting, decision, repetition, input, and output.

3-state Busy Beaver

This is explained on Turing Machine. See the pastebin website to see the code (because of technical limitations):[1]

This 3-state busy beaver program generates six 1-bits on the tape:

Q0:E>1
Q1:O<1
E0:Q<1
E1:E>1
O0:E<1
O1:F>1

Computational class

A Turing-machine program trivially describes a Turing machine, but with very few states and symbols, and not one of the combinations known to be sufficient for Turing completeness. It is therefore not clear if it can simulate all of them, which is the deciding criterion. (Note that universal Turing machines include the initial tape as part of the setup to simulate other Turing machines, so it's not trivial to show that it is not Turing-complete, either. I don't know if anyone has proved it.)

Interpreter

• Common Lisp implementation of the Turing-machine programming language.