serin-delaunay/tmtracery

Turing Machine to Tracery compiler

Turing Machine Tracery

This project implements a Turing Machine - to - Tracery compiler. The compiler relies on a bug in some Tracery versions which allows delayed expansion of variables, and shows that these versions of Tracery are Turing-complete

To convert a Turing machine defined in machine.json to Tracery, run the following command:

python tmtracery.py machine.json

The resulting Tracery grammar will be written to machine.json.tracery.json.

You can specify a different output filename using a command line argument:

python tmtracery.py machine.json -o machine.t.json

You can add initial tape data from input.txt, using another command line argument:

python tmtracery.py machine.json -i input.txt

Turing machine file format

TMT uses a JSON encoding of Turing machines. The machine must be encoded as a single object containing seven keys:

• states: an array of unique strings naming all of the machine's states, including an accepting and rejecting state.
• symbols: an array of unique single-character strings naming all of the machine's symbols, including a blank symbol.
• blank_symbol: a string equal to one of the items in symbols. The machine's tape will initially be filled with this, apart from the input data.
• start_state: a string equal to one of the items in states. This will be the machine's initial state.
• accept_state: a string equal to one of the items in states. The machine will halt and accept on reaching this state.
• reject_state: a string equal to one of the items in states. The machine will halt and reject on reaching this state.
• delta: a complete array of transitions for all symbols and all states except the accept and reject state.

Any other keys are ignored.

Transition format

Each transition in delta is an array containing two arrays. The first identifies the state and symbol under the tape head which will prompt this transition. The second identifies the new state, the symbol to write at the tape head, and the direction to move the tape head after writing. Valid tape head directions are < (left), > (right), and _ (remain).

Example machine

{
    "function": "Accepts a string iff it is empty, or starts with 0 and consists of alternating 1s and 0s."
    "states": ["A", "B", "Y", "N"],
    "symbols": ["0", "1", "_"],
    "blank_symbol": "_",
    "start_state": "A",
    "accept_state": "Y",
    "reject_state": "N",
    "delta": [
		[["A", "0"], ["B", "0", ">"]],
		[["A", "1"], ["N", "1", "_"]],
		[["A", "_"], ["Y", "_", "_"]],
		[["B", "0"], ["N", "0", "_"]],
		[["B", "1"], ["A", "1", ">"]],
		[["B", "_"], ["Y", "_", "_"]]
	]
}

Execution model

The simulated machine has one double-sided infinite tape, implemented as a pair of stacks. When either end of the tape is reached, an additional blank symbol is automatically appended to that side.

Limitations

The produced Turing machine grammars only work on Tracery versions which have a bug allowing delayed expansion of dynamically specified tags. A simple example grammar using this bug is:

{
    "origin": "[tweet:#start#]#tweet#",
    "start": "\\#helloworld\\#",
    "helloworld": "omg what how"
}

This project is supported only on Tracery versions where this grammar evaluates to "omg what how".

tmtracery's Issues

Print correct state on halt

License

MIT

Print tape on halt

To do this:

• Move everything from tape_left onto a new stack (reversing it)
• Print everything from the new stack
• Print the first element on tape_right surrounded by *
• Print the remainder of `tape_right

Use halting state set rather than specific accept and reject states

A lot of machines presented in literature only use one halting state, no need to add extra complexity.

Schema for Turing machine format

Inline explanation tags in base grammar?

Some sort of in-depth exposition of how the compiler works is necessary.

Different execution modes

Different degrees of verbosity, etc. enabled by compiler switches.

Continuous integration

Needs a compatible tracery version running on the command line. And #3.

Multi-tape machines

This is not a high priority!

Use branching call system to avoid callstack overflow

Each state transition currently expands a symbol one step deeper in the tracery call stack. This may cause stack overflows in machines that use many steps. Eli Dupree has made a prototype of a branching call system which doubles the number of execution steps every two levels deeper in the call stack. It requires an exit method before it can be used.

"run_many_steps": "[execute_run_many:#activate_run_many#]#execute_run_many#[execute_run_many:POP]",
"activate_run_many": "\\#run_many_switch_#run_many_stack#\\#",
"run_many_switch_END": "#run_step#",
"run_many_switch_CONTINUE": "[run_many_stack:POP]#run_many_steps##run_many_steps#[run_many_stack:CONTINUE]",

"run_steps_forever": "#run_many_steps#[run_many_stack:CONTINUE]#run_steps_forever#",
"run_many_stack": "END",

Tests?

Tests!

Include minimal example of required bug in docs

{
    "origin": "#[tweet:#start#]tweet#",
    "start": "\\#helloworld\\#",
    "helloworld": "omg what how"
}

List tracery commits and online environments by whether the bug works there

Apparently CBDQ/CBTS frontend works and backend doesn't - frontend uses galaxykate/master, backend uses tracery2 branch.