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.

Turing Machine

$$>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:

$$wqv⊢w^{\prime }{q}^{\prime }{v}^{\prime }$$ $$\delta (q,v)=(q^{\prime },v,R)$$

→ where the configuration is denoted as $(\text{state},\text{write symbol},\text{move left/right})$

In this case the head is reading the first symbol of $v$, i.e. the right-side letter.

---

Turing Machines as Language Recognizers/Acceptors §

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

⇒ Then $w$ is in the language of the TM.

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