Slide 1
Final Review
Turing Machines
Deterministic TM
Configuration; initial configuration
Computation
Halting
Accepting
Rejecting
Description
Graph
Shorthand
Deciding = the D class of languages
Semideciding = the SD class of languages
Computing functions
TM Extensions
Multiple tapes
Multi-tape TM is equivalent to deterministic TM
Nondeterministic TM
Accepting, Rejecting
Deciding, Semideciding, Computing functions
Nondeterministic TM are equivalent with deterministic TM
For deciding, semideciding, computing functions
One-way tape TM
One-way tape TM is equivalent to deterministic TM
PDA with two stacks can simulate a TM
TM can simulate real computers
Universal TM
TM encoding
States, tape alphabet, transitions
Encoding multiple inputs
Enumerating TMs
Universal TM
Specification
On input
Construction
Church-Turing thesis
The Halting Problem
Halting Problem for TM is in SD \ D
Semidecidable (in SD)
Not decidable (not in D)
Trouble
Diagonalization
H D D = SD
D and SD
D ⊂ SD
SD \ D ≠ (H is here)
SD is countable
SD is uncountable
D is closed under complement
SD is not closed under complement
L D iff L, L SD
H SD
Enumeration
TM enumerates
Turing-enumerable language
L SD iff L is Turing enumerable
TM lexicographically enumerates
Lexicographically Turing-enumerable language
L D iff L is lexicographically Turing enumerable
Reduction
Reduction:
L1 L2
L1 is reducible to L2
L2 is harder than L1
Using reduction for undecidability
Prove that L2 is not in D
Find suitable L1 not in D
Show that L1 L2
H, H, HANY, A, A, AANY SD \ D
Rice’s Theorem:
Any nontrivial property of SD is undecidable.
Practical implications on programs
Non-SD languages
Proving a language L in not in SD
L SD \ D
Reduction from non-SD language
H, HANY, EqTMs, HALL, AALL, TMreg, Aanbn SD
Unrestricted grammars
Unrestricted grammars
Equivalence with SD
Grammar TM
TM Grammar
Decision problems
Undecidability follows from SD
*
Non-TM problems
Post Correspondence Problem (PCP)
PCP SD \ D
La MPCP PCP
Problems of context-free languages
CFGALL D
Reduction from H
Computation histories
CFG=, PDAMIN D
Reduction from CFGALL
IntEmpty, CFGUNAMBIG D
Reduction from PCP