Turing Machine

A Turing machine:

• Is most powerful type of automation (probably.)
• Cannot solve the halting problem.
• Can be used to prove Limits of Math and Computing.

def. Turing Machine $M$ is a turing machine defined as a tuple:

$$M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,F)$$

where the previously unencountered symbols are:

• $Q$: States
• $\Sigma$: Input Alphabet
• $\Gamma$: Tape Alphabet (superset of $\Sigma$)
• $q_0$: Start state
• $F$: Set of en states
• $B$: Blank (also written as $\square$)
• $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ Configuration and transition of a TM is denoted:
• Configuration: $wqv⊢w^{\prime }{q}^{\prime }{v}^{\prime }$
  • In this case the head is reading the first symbol of $v$, i.e. the right-side letter.
  • the ”$⊢$” indicates a state transition
• Transition function $\delta$: $\delta (q,v)=(q^{\prime },v,R)$
  • The configuration is denoted as $(\text{state},\text{write symbol},\text{move left/right})$

Turing Machines as Language Recognizers/Acceptors §

def. Language of a turing machine. For turing machine $M$ with language $L$, String $w\in L$ if:

$$L(M)=\{w|q_{0}w⊢v{q}_{f}w\}$$

You can also think of it as the turing machine “halting” on the final state.

• If TM halts on a final state, $w$ is accepted
• If TM halts on a non-final state $w$ is not accepted
• If TM doesn’t halt, $w$ is not accepted

Turing Machines as a Transducer (=Transformation on a language) §

def. Turing-Computable. A function $f(w)$ is Turing-Computable if:

$$\forall w,q_{0}w{⊢}^{\ast }{q}_{f}f(w)$$

Example of a Turing Machine representing a turing-computable function:

Turing Machine Building Blocks §

1. $M_1\to M_2$
2. $M_1\stackrel{x}{\to }{M}_2$: run if $x$ is the current output ← you can also have multiple conditionals

You have the building blocks of commonly-used TMs.

1. $s$: start, $h$: halt
2. $x$: write symbol $x$ onto tape
3. $L,R$: Move left, right
4. $L_a,R_a$: Move left or right until you see $a$ in tape ← make sure there is an $a$ on tape or it won’t halt
5. $L_{\neg a},R_{\neg a}$Move left or right until you don’t see $a$ in input
6. $\stackrel{a,b}{\to }\}\stackrel{w}{\to }$: symbols $a,b$ are represented as variable $w$ ← avoids having to write two identical machines for each symbol

Some more advanced building blocks:

1. $C$: Copy with a zero in the middle. e.g. $abba\to abba0abba$. Tape head starts and ends in the beginning symbol.
2. $S_L,S_R$ Shift left what is on the right, v.v. The symbol on the head is erased.

Example of using building blocks to simplify a turing machine:

---

Turing Machine Equivalents §

1. TM with Stay option: $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R,S\}$
2. Multitrack TM: One tape, but split into $n$ cells: $\delta :Q\times {\Gamma }^n\to Q\times {\Gamma }^n\times \{L,R\}$
   • Diagram
3. Semi-infinite TM: The tape is infinite only in one direction → Proof by “folding over” the standard TM into multi-track.
4. Multi-tape TM: $\delta :Q\times {\Gamma }^n\to Q\times {\Gamma }^n\times \{L,R{\}}^n$
5. Off-line TM: Two-tape; one tape is input, the other the read/write tape. $\delta :Q\times {\Gamma }^2\to Q\times \Gamma \times \{L,R{\}}^2$
6. Non-deterministic TM
   1. NPDA with 2 stacks

Universal Turing Machine §

Every TM can be binary encoded by a binary number:

The Universal Turing Machine is a 3-tape turing machine that simulates a standard Turing Machine $M$. Each of the tapes are:

1. Tape A: Binary encoding of a simulation of $M$
2. Tape B: The tape of $M$
3. Tape C: $M$’s current state