ENTMPL

ENTMPL (for Easy Numeric Turing Machine Programming Language) is a very concise and obfuscated language for programming Turing machines, designed by Abraham Karplus. It simply consists of a list of nonnegative decimal integers and asterisks, separated by one or more whitespace characters. Comments may be included in parentheses.

Machine

The Turing Machine is a single tape (infinite in both directions), finite symbol count, finite head state count machine with IO being the initial and final states of the tape. The initial head state is 0, and the tape is initially filled with zeroes to the left of the tape head, and the input under and to the right of the tape head (with the rest of the tape to the right after the input filled with zeroes). Zeroes may not occur in the input, and output is read from the starting position of the tape head to the right until a zero is reached.

Program

The first two numbers in the program are the number of different tape symbols and the number of head states, respectively. The number of symbols or states may be replaced by an asterisk, indicating that it should be determined by the highest value in the source code (or input, for tape symbols). When a specific number in specified, all symbol or state numbers are taken modulo it. Following these two numbers are any quantity of five-tuples of numbers, each representing a rule.

Rules

The five numbers in a rule have the following meaning:

• Initial Tape Symbol
• Initial Head State
• Resultant Tape Symbol
• Resultant Head State
• Direction

Multiple rules may not have the same initial tape symbol and head state. A direction of 0 indicate left and 1 indicates right. Some or all of numbers in a rule may be replaced by single asterisks, with varying meanings. As an initial symbol or state, the asterisk is a wildcard, matching anything. As a resultant symbol or state, it indicates no change, and as a direction it indicates halting the program.

Examples

Cat

( CAT ) * (Determine # of tape symbols from input.) 1 (Only one head symbol needed.)
(First rule:) * (Whatever first tape symbol is,) 0 (the head state will be zero,) * * (so keep both) * (and end the program.)

Wolfram's 2,3 Machine

(WOLFRAM 2,3) 3 2
0 0 (->) 1 1 (R) 1
0 1 (->) 2 0 (L) 0
1 0 (->) 2 0 (L) 0
1 1 (->) 2 1 (R) 1
2 0 (->) 1 0 (L) 0
2 1 (->) 0 0 (R) 1