Turing-machine

From Esolang
Jump to: navigation, search

Not to be confused with Turing machine.

Syntax

All of the rules look like this:

cnd.num.:cnd.direction num

like:

Q1:E<0

If the condition is Q, and the number on the tape is 1, the change the condition into E, change the tape into 0, and move left. conditions are:

Q, E, O, F

When the condition is F, the Turing-machine halts. Numbers are:

0, 1

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

<, >, -

<: move left. >: move right. -: stay the same.

Truth-machine(Beta version)

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

To mak 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 tecnical limitations):[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.)