Skip to content

13. TM Variations

Feb 17/22, 2022

  • Turing thesis: any computation carried out by mechanical means can be performed by a Turing machine

  • An algorithm for a problem is a TM which solves the problem

    • the algorithm describes the steps in mechanical means, this is easily translated into computation steps of a Turing machine

    • saying "there exists an algorithm" means "there exists a TM that executes the algorithm"

  • Standard model TM is deterministic, has infinite tape, head moves left/right

  • the following variants all have the same power, but differ in speed

  • equal power between two machines means both accept the same set of languages: \(L(M_1) = L(M_2)\)

Simulation

Simulation is a technique to prove two machines have equal power => simulate machine of one class with a machine of the other class

Configurations in the original machine \(M_1\) has a corresponding configurations in the simulation machine \(M_2\)

  original             simulation
   machine               machine
                      ╭-----------╮
    [M1]              | M2   [M1]   |
                      ╰-----------╯


M1:   \(d_0 \succ d_1 \succ \dots \succ d_n\)
          🠗         🠗                 🠗
M2:   \(d_0^{'} \overset{*}{\succ} d_1^{'} \overset{*}{\succ} \dots \overset{*}{\succ} d_n^{'}\)

Accepting configuration

  • original machine:   \(d_f \leftrightarrow d^{'}_f\)   simulation machine
  • the original machine and simulation machine accept the same strings \(L(M_1) = L(M_2)\)

Multiple track tape

  • standard TM but each tape alphabet symbol describes a pair of symbols
  • helps more complicated simulations

Example: one head, one symbol \((a, b)\)

 one tape
 ... | a | b | a | b | ...   track 1 
 ... | b | a | c | d | ...   track 2
       H

Variants

Stay-Option

Machine where the head can stay in the same position => possible head moves \(\{L, R, S\}\). To prove this has equal power as standard TM:

  1. Stay-option machine simulates standard TM
    => trivial: any TM is also a stay-option machine

  2. Standard TM simulates stay-option machine
    => simulate stay head options with two head moves, one left one right.

Semi-infinite tape

The tape extends infinitely only to the right. Initial position is the leftmost cell. When head moves left of the border, it returns back to leftmost position. 

    [ a | b | a | b | ⎵ | ⎵ | ...

  1. Semi-infinite machine simulates standard TM
    => represent infinity of both directions using one direction only: (1) create a reference point in the standard machine (2) use semi-infinite tape machine with two tracks => when control reaches left boundary change move direction L/R.

  2. Standard TM simulates semi-infinite machine
    => (1) insert a special symbol # at the left of input string (2) add a self-loop to every state (except states with no outgoing transitions)

Multi-tape machine

Machine with multiple tapes, each tape has its own head. Input appears on tape 1.

  1. Multi-tape machine simulates standard TM
    => trivial: use one tape

  2. Standard TM simulates multi-tape machine
    => use a multi-track tape to simulate the multiple tapes; a tape of the multi-tape machine corresponds to a pair of tracks. Repeat for each multi-tape state transition:

    • 1: return to reference point
    • 2: find current symbol in track 1 and update
    • 3: return to reference point
    • 4: find current symbol in tape 2 and update.

Multidimensional

Has 2D tape and moves \(\{L, R, U, D\}\)

  1. Multidimensional machine simulates standard TM
    => trivial: use one dimension

  2. Standard TM simulates multidimensional machine
    => use a two-track tape; store symbols in track 1, store coordinates in track 2. Repeat for each transition followed in the 2-dimensional machine

    • 1: update current symbol
    • 2: compute coordinates of next position
    • 3: find next position on tape

Nondeterministic

Allows nondeterministic choices. Input string \(w\) is accepted is there is a computation \(q_0w \overset{*}{\succ} xq_fy\), i.e. there is a computation from initial configuration to final configuration that ends in accept state.

  1. Nondeterministic machine simulates standard TM
    => trivial: every deterministic machine is also nondeterministic.

  2. Standard TM simulates nondeterministic machine
    => use a 2D tape (equivalent to standard TM with one tape); store all possible computations of the non-deterministic machine to the 2D tape. The deterministic machine simulates all possible computation paths: simultaneously, step-by-step, with breadth-first search (DFS can get stuck exploring infinite path before finding accepting path). Repeat, for each configuration in the current step of non-deterministic machine, if there are two or more choices: (1) replicate configuration (2) change the state in the replicas, until either the input string is accepted or rejected in all configurations.

    • If the nondeterministic machine accepts the input string, the deterministic accepts and halts too. This simulation takes in the worst-case exponential time compared to the shortest length of an accepting path.

    • If the non-deterministic machine does not accept the input string: the simulation halts if all paths reach a halting state -OR- the simulation never terminates is there is a never-ending path (infinite loop) => in either case the deterministic machine rejects too.