Turing Machines

title: 'Turing Machines' date: '2021-03-03'

Turing Machine

A Turing Machine (TM) is a 7-tuple: where are finite sets and,

• is the set of states
• is the input alphabet not including blank symbol #
• is the tape alphabet, where
• is the start state
• is the accept state
• is the reject state

Note:

• TM can both write and read from the tape
• The read-write head can move to both left and right
• The tape is infinite
• States for rejecting and accepting take effect immediately
• Input is written on the first entry on the left side of the tape, and all the rest boxes contains blank symbol #
• It is assumed (in this class) that we know when we are pointing at the first tape square
• TM is deterministic if not stated
• Notation: write for the configuration where the current state is , current tape content is and head location is
• Start configuration:

TM accepts input if a sequence of of configuration exists where:

1. is the start configuration of
2. each yields with a transition function
3. is the accept configuration

Def: A language is Turing-recognizable if some TM recognizes it, denoted . Def: A language is Turing-decidable if some TM decides it (leading to either acceptance or rejecting).

Variants of Turing Machine

Multi-tape Turing Machine with tapes Transition function allows for reading, writing, and moving all heads simultaneously. Theorem: Multi-tape Turing Machine has an equivalent single tape Turing Machine. has tapes. Sinlge tape TM simulates the effect of tapes by using a new symbol S$ keeps track of the heads using "virtual heads": by writing dots to mark where the heads would be.

Nondeterministic Turing Machine Transition function: We say NTM accepts if there's some way to compute that ends up in an accept configuration. Theorem: Every NTM can be simulated by a corresponding deterministic TM that accepts the same language.

Proof: Simulate any NTM with a deterministic TM (breath-first search):

• Tape 1: input string that is not altered
• Tape 2: copy of 's tape on some branch
• Tape 3: keep track of 's location and 's nondeterministic computation tree 231 meaning go to second child, then third child in the next level, and the first child next.

Let try all branches of 's computation on tape 2 with finite number of steps (indexed by tape 3). If no more symbols remain on tape 3 or if this nondeterministic choice is invalid, abort this branch, increment the number on tape 3 and simulate the next branch. If one branch accepts, accept. Otherwise does not terminate.

Idea: For each NTM, construct a 3-tape deterministic TM.

Theorem: A language is Turing recognizable some NTM recognizes it.

Def: A NTM is a decider if and only if halts and answers accept or reject on all branches of computation.

Theorem: is decidable if and only if both and are recognizable. Proof:
() Decider is automatically a decider. () Build a decider : Let recognizes and recognizes . Simulate with and on two tapes. One of the tapes must halt and accept. If accepts then accepts. If accepts then reject.

Universal Turing Machine

A Universal TM to run any DFA: Intuition: Can we write a program to do what DFA does? is recognizable? Proof: Construct 2-tape TM , one tape with the input and the rules of on another tape.

1. On input <>, first check that is in the right form and . Otherwise reject.
2. While the symbol on the input tape (head) is not blank, if DFA is in and reading , go to where and move right.
3. When symbol is blank, if DFA is in an accept state, accepts. Otherwise halts and rejects.

Theorem: is decidable. Proof idea: check if any accept state is reachable, by path finding.

Theorem: is decidable. Construct DFA such that accept strings iff both reject it: Thus, to prove is decidable, prove is decidable where is the input of .

Run TM on described above. If accepts, accepts. If rejects, rejects.