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
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 insymbols
. 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 instates
. This will be the machine's initial state.accept_state
: a string equal to one of the items instates
. The machine will halt and accept on reaching this state.reject_state
: a string equal to one of the items instates
. 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.
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).
{
"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", "_", "_"]]
]
}
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.
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"
.