The TuRingMachine repo uses a single tape Turing machine ("TM") specified as a 7-tuple:
TM := <Q, L, b, S, d, q(0), F>
Where:
-
Q is a finite, non-empty set of states;
-
L is the set of tape alphabet symbols: {0, 1};
-
b (in L) is the blank symbol: {0} (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
-
S is the set of input symbols that are allowed to appear in the initial tape contents: {0, 1};
-
q(0) (belonging to Q) is the initial state: {0};
-
F (subset of Q) is the set of final states or accepting states. The initial tape contents is said to be accepted by TM if it eventually halts in a state from F.
-
d is the transition function, which takes as inputs:
- State q(x) (in Q)
- Alphabet symbol l (in L)
And outputs:
- State q(y) (in Q)
- Alphabet symbol l (in L)
- A move direction:
- "L" (i.e. move the tape head one position to the left), and
- "R" (i.e. move right)
Specifically the Turing machine instructions are encoded using Penrose's schema:
- 0 for
0
- 10 for
1
- 110 for
R
, move the tape right - 1110 for
L
, move the tape left - 11110 for
H
, the halting move
Any TuRingMachine in this repo is initialised as:
function_name(input, blank_symbol, instruction_set, tape_moves = 999)
Where:
- function_name is a tuRingMachine
function
within/R
- input is an
atomic vector
- instruction_set is a
data.frame
that has the following column entries:- current_state
- tape_symbol
- next_state
- print_symbol
- move_tape
Here the instruction_set is used by the TM as the transition function.
There are two types of tuRingMachine functions for each type of operation:
- The base function will output a
data.frame
with the following columns:
- input as an
atomic vector
- output as an
atomic vector
- status providing a binary outcome
"Accepted"
or"Rejected"
- moves, as an
integer
, being the number of times the tape was moved by the TM
- The equivalent function with
_log
appended to the function name will output adata.frame
with the following columns:
- input as an
atomic vector
- current_state for each tape move from the instruction_set
- tape_symbol as the current tape symbol read by the TM for each tape move
- tape_position as the position along the input that the TM is for each tape move
This allows you to track the internals of the TM.
Examples of using a turRingMachine function
is given in /examples
.
Pre-configured instruction sets are given in /data
.
Using Penrose's schema we find that the Turing machine that adds one in binary ("XN + 1") is represented by the 450,813,704,461,563,958,982,113,775,643,437,908th Turing machine, as shown in /examples/TuringMachines.R
.
We also find that Turing machine 177,642 (under Penrose's encoding schema) corresponds to a machine that adds one to a unary input ("UN + 1"), again shown in /examples/TuringMachines.R
.
This repo is an R
implementation of the Turing machines specified in Chapter 2 "Algorithms and Turing Machines" in Roger Penrose's book "The Emperor's New Mind".
tuRingMachine is open source software licensed as MIT.