**Lecture
16 (Multitape TMs), 10/31/17**

**Concepts, definitions (in italics):**

- Variants of TMs:
- allow STAY move, allow read-only
transitions, allow star transitions
- do not allow move left changes expressiveness to that
of DFAs!!
*Multitape*Turing Machine: a variant of a TM- k tapes 1, 2,
k
- delta = Q x Gamma
^{k}-> Q x Gamma^{k}x {L,R,S}^{k} - Initially the input is on tape 1, and all heads are in
position 1
- TMs are always in exactly one state at a time, even
when they have many tapes and/or reading heads.
- Example of multitape computation
*: w#w*(2 tapes) *Simulating A with B: *simulation- For each configuration of A, there must be way to encode it in B
- The simulation must simulate each transition of this process in
turn (so if A does not halt, B will not either)
- The simulation of a transition transforms the encoding of each
configuration to the encoding of the next one
- Theorem: Every multitape TM-k has an equivalent single-tape TM-1
- TM-1 simulates TM-k
- Often, its easier to
design a TM for some task if we can use multiple tapes, and/or we can
make the task much
*faster* - Simulating
- Representing multiple tapes with one

**Reading:**

·
Chapter
3.2 to end of p. 177

**Skills:**

- Know new definitions, understand new concepts.
- What does a configuration for a Multitape
TM look like?
- What does transition function for a Multitape
TM look like?
- Be able to describe a program for a Multitape
TM machine
- How to represent a configuration of a Multitape TM on a single-tape TM? Given a transition
table for a Multitape Turing Machine, simulate
this machine

**Notes:**

- Turing's original paper assumed that Sigma is always {0,1}. Our TMs with an arbitrary Sigma are actually a
variant of the original version.