Turing machine emulator in PHP.
PHP
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
bin
doc
examples
src
.gitignore
LICENSE
README.md
composer.json
composer.lock

README.md

turing-php

turing machine

Turing machine emulator in PHP.

Usage

You can run the machine as follows:

$ bin/machine <file>

run

The default mode is the run mode that runs until the machine reaches an accept state at which point it halts and prints the current tape and configuration.

$ bin/machine examples/increment.php
Tape: 110(0)
Position: 3
State: 3
Steps: 6

You can also provide your own initial tape and start position with the -t and -p options:

$ bin/machine examples/increment.php -p 1 -t 10
Tape: 1(1)
Position: 1
State: 3
Steps: 2

Note that the rules may require you to provide a valid initial position.

debug

If you want to get better information about what the machine is doing while running, you can run it in debug mode. This will make it print the tape and configuration after every transition. This can be useful when inspecting non-terminating machines.

$ bin/machine debug examples/increment.php
Tape: 101(1)
Position: 3
State: 1
--------
...
--------
Tape: 1100(_)
Position: 4
State: 2
--------
Tape: 110(0)
Position: 3
State: 3
Steps: 6

until <n>

For potentially non-terminating machines, the until mode allows the maximum number of steps to be limited. If that number of steps is exceeded, an error is returned.

$ bin/machine until 10 examples/omega.php
ERROR: Exceeded maximum steps of '10'.

graphviz

You can dump the rules to the graphviz format and then feed that into dot to get a pretty graphical representation of the state transitions.

$ bin/machine graphviz examples/increment.php | dot -Tpng -o doc/increment.png

Output:

graph of increment state transitions

References