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:

1. 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

2. The equivalent function with _log appended to the function name will output a data.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.