Simulate a universal turing machine. To define a Turing machine, the caller must supply two things: a machine configuration (c.f. default_config/5), and a set of machine rules (c.f. rules/5). The file turing_test.pl (the name is a joke, yes) contains two examples of Turing machines.

This code is known to be compatible with SWI-Prolog and YAP Prolog. Other dialects may require alteration.

author

- Michael T. Richter <ttmrichter@gmail.com>

version

- 1.0.0

See also

- http://en.wikipedia.org/wiki/Turing_Machine#Formal_definition

copyright

- (c)2013 Michael T. Richter

license

- This program is free software. It comes without any warranty, to the extent permitted by applicable law. You can redistribute it and/or modify it under the terms of the Do What The Fuck You Want To Public License, Version 2, as published by Sam Hocevar. Consult http://www.wtfpl.net/txt/copying for more details.

 turing(+Config, +Rules, +TapeIn, -TapeOut) is semidet

Execute a Turing machine based on the provided Rules on TapeIn rendering TapeOut. Note that turing/4 is a meta-predicate and that Parameters and Rules are module-delimited as a result.

Arguments:

Config	- C.f. default_config/5.
Rules	- C.f. rule/5.
TapeIn	- A list of symbols representing the input tape.
TapeOut	- A list of symbols representing the output tape.

 default_config(-IState, -FStates, -RStates, -Blank, -Symbols) is det

These are the default parameters for a Turing machine used mainly as a means of demonstrating the making of a custom machine. The params call provides the legal states and symbols for use in the Turing machine. The Turing engine enforces state names and symbols as a strict subset of those provided.

Note that this is a model of how a machine configuration should be coded. It may be called, but in reality is not very useful a setup.

Arguments:

IState	- The initial state of the machine when starting.
FStates	- A list of the terminating states of the machine.
RStates	- A list of the running states of the machine (must include the initial state).
Blank	- The blank symbol.
Symbols	- The complete list of legal tape symbols (must include the blank symbol).