Skip to content

12. Turing Machines

Feb 15, 2022

  • Deterministic machine with infinite tape, read-write head, head moves to left or right

  • Behavior at each time step: \(a \rightarrow b, R\)

    • reads a symbol (\(a\))
    • writes a symbol (\(b\))
    • moves left or right \(\{L, R\}\)

  • \(\Sigma\) is the input alphabet, \(\Gamma\) is the tape alphabet

    • special blank symbol (e.g. ⎵) where \(⎵ \notin \Sigma\) and \(⎵ \in \Gamma\)

Example

Time 0     ...| ⎵ | a | b | a | c | ⎵ | ⎵ | ...     reads a, writes k, moves left
                             H

Time 1     ...| ⎵ | a | b | k | c | ⎵ | ⎵ | ...     reads b, writes f, moves right
                         H

Time 2     ...| ⎵ | a | f | k | c | ⎵ | ⎵ | ...     
                             H

  • head starts at the leftmost position of the input string

  • read and write can operate on the same symbol, to not change the tape

  • no \(\epsilon\)-transitions => if there is no allowed transition in a state the machine halts

  • accepting states have no outgoing transitions => the machine immediately accepts and halts

    • in order to accept, it is not necessary to process all input
    • accepting necessitates halting

  • rejecting can happen if:

    • machine halts in a non-accepting state
    • machine enters an infinite loop

Example

\(\Sigma = \{a, b\}\) accepts the language \(a^*\)

  • Scans all symbols \(a\), and once it reaches a blank symbol moves to accepting state and halts.
  • If ever \(b\) is encountered, the machine halts and rejects.

Special case: \(\Sigma = \{a\}\) accepts the language \(a^*\)

  • it is not necessary to scan any input, machine always accepts


If machine enters an infinite loop:

  • accepting state cannot be reached
  • machine never halts
  • the input is rejected

Formal definition

  • (these definitions may vary slightly and machines are usually not defined in formally and in detail)

  • \(M = (Q, \Sigma, \Gamma, \delta, q_0, ⎵, F)\) where

    • \(Q\) is a set of states
    • \(\Sigma\) is input alphabet
    • \(\delta\) is transition function :   \(\delta(q_1, a) = (q_2, b, R)\)   \(\delta(q_1, c) = (q_2, d, L)\)
    • \(q_0\) is start state
    • \(⎵\) is blank tape symbol
    • \(F\) is accept states

  • The accepted language, for any Turing machine \(M\): \(L(M) = \{w: q_0w \overset{*}{\succ} x_1 q_f x_2 \}\)

    • if language \(L\) is accepted by Turing machine \(M\) then \(L\) is Turing-recognizable
    • alternative terms: Turing-acceptable, recursively enumerable

Configuration

  • configuration describes the machine state at time step
 ... | a | a | a | b | b | b | ... 
                   H

  • we can describe configuration as: aaaqbbb where

    • aaa is the tape content to the left of the head
    • q is the current state (\(q_i\)) and position of the head wrt the tape
    • bbb is the tape content to the right of the head

  • a move:   \(q_2 xayb \succ x q_0 ayb\)

  • a computation is a sequence:   \(q_2xayb \succ xq_0ayb \succ xxq_1yb \succ xxyq_1b\)
    • equivalent notation:   \(q_2xayb \overset{*}{\succ} xxyq_1b\)