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\to b,R$

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

• $\mathrm{\Sigma }$ is the input alphabet, $\mathrm{\Gamma }$ is the tape alphabet

  • special blank symbol (e.g. ⎵) where $⎵\notin \mathrm{\Sigma }$ and $⎵\in \mathrm{\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 $ϵ$-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

$\mathrm{\Sigma }=\{a,b\}$ accepts the language $a^{\ast }$

• 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: $\mathrm{\Sigma }=\{a\}$ accepts the language $a^{\ast }$

• 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,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,⎵,F)$ where

  • $Q$ is a set of states
  • $\mathrm{\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_{0}w\stackrel{\ast }{\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_{2}xayb\succ x{q}_{0}ayb\succ xx{q}_{1}yb\succ xxy{q}_{1}b$
  • equivalent notation:   $q_{2}xayb\stackrel{\ast }{\succ }xxy{q}_{1}b$