# ITEC 420 - Section 3.1 - Turing Machines

## Turing Machine: Introduction

• Turing Machines can recognize all computable languages
• We will leave the notion of computable language as intuitive
• We will see well-defined languages that are NOT computable with a TM (or in any other known way)
• We will see that all known ways of computing have the same power as the TM (or less)

• Implementation: TM = FSM + Tape!

## A Turing Machine's Tape

• Tape is infinite (in one direction)

• Tape is initialized with input at left end
• Rest of tape has blanks
• Blank not in input alphabet

• Reads and writes the symbol under the head at each transition
• Moves one symbol left or right at each transition
• Attempts to move past left end of tape leave tape at left end of tape
• Machine can NOT tell where on the tape the head is

## Example Turing Machine

• A = {w#w | w ∈ {`0,1`}*}
• Algorithm intution: ... (p 139)

## Turing Machine: Halting a Computation

• Computation can do one of three things:
1. End (immediately) by entering a special Accept state
2. End (immediately) by entering a special Reject state
3. Continue forever (ie never enter Accept or Reject state)

• For comparison, consider the halting conditions for these machines:
• DFA
• NFA
• PDA

## Turing Machine Accepts a String

• Machine M accepts string w if w takes M to the Accept State of M

## Turing Machines: More Examples

• A = {w#w | w ∈ {`0,1`}*}
• Formal specification of machine: (Example 3.9, p. 145)

• B = {ww | w ∈ {`0,1`}*}
• Algorithm: How would we find the center of the string? ...

• C = {`a`n`b`n`c`n | n ≥ 0}
• Algorithm: ...

• D = {02n | n ≥ 0} (Example 3.7, p 143, 144)

## Formal Definition of a TM

• Must define seven items:
1. Q is the set of state
2. Σ is the input alphabet (does not include the blank symbol)
3. Γ is the tape alphabet, blank ∈ Γ and Σ ⊆ Γ
4. δ: (state, tape symbol) → (state, tape symbol, L/R)
5. Start state
6. Accept state
7. Reject state (different from start state)

• Transition function: δ(q,b) → (r,c,D) means the machine is in state q and the tape head is over a b. The machine then writes an c onto the tape (erasing the b), goes into state r, and moves direction D on the tape.
• Shorthand notation: a → D means to read and write and a and to move direction D

• Deterministic or non-deterministic?

## Configuration of a TM

• Show tape head position by writing current state to left of symbol it is over:

• Example: `1011`q7`01111`
• Tape contents are ` 101101111`, tape head is over rightmost 0, and machine is in state q7
• tape head is over rightmost 0, and machine is instate q7
• machine is in state q7

• Accepting/Rejecting Configuration
• Machine halts when machine enters Accept or Reject State!
• Tape head can be anywhere!

## TM Computation: Formal Definition

• A computation is a sequence of configurations of machine M in which
• First configuration in the sequence has M in the start state with M's head at the left of the tape

• Each step in the sequence moves M to the next configuration with a single read, a single write, and a single move

## TM Accepts a String: Formal Definition

• Machine M accepts string w iff there is a computation that
• Starts with the start configuration of w on M (ie w written on left end of tape and R/W head at left end)
• M takes each configuration in the computation to the next configuration
• The computation ends in an accepting configuration (ie in the accept state)

• No surprises here, but remember the head can be anywhere at the end of the computation

## Recognizing a Language

• The language recognized by machine M is the collection of strings accepted by M

## A Turing Recognizable Language

• A language that is recognized by a machine is called a Turing Recognizable language

• Later we'll see that there is some subtlety here

• For now, remember that language L is TR, if there is a TM M for which all strings in L put M in its accept state.

• So, how do we prove that a language is TR?

• Question: What about strings that are not in L?