/tuRingMachine

Turing machine examples in R

Primary LanguageRMIT LicenseMIT

Turing Machines in R

Specification

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

Initialisation

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.

Output

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

Usage

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.

Acknowledgement

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

License

tuRingMachine is open source software licensed as MIT.