CSC-4890
Introduction to the Theory of
Computation
Costas Busch - LSU 1
General Info about Course
Instructor: Konstantin (Costas) Busch
Books
• Introduction to the Theory of Computation,
Michael Sipser
• An Introduction to Formal Languages and
Automata, Peter Linz
Costas Busch - LSU 2
Course Goals
Provide computation Models
Analyze power of Models
Answer Intractability questions:
What computational problems
can each model solve?
Answer Time Complexity questions:
How much time we need to
solve the problems?
Costas Busch - LSU 3
A widely accepted model of computation
CPU memory
Costas Busch - LSU 4
The different components of memory
temporary memory
input
CPU
output
Program memory
Costas Busch - LSU 5
3
Example: f ( x) x
temporary memory
input
CPU
output
Program memory
compute xx
2
compute x x
Costas Busch - LSU 6
3
f ( x) x
temporary memory
input
x2
CPU
output
Program memory
compute xx
2
compute x x
Costas Busch - LSU 7
3
temporary memory f ( x) x
z 2*2 4
f ( x) z * 2 8
input
x2
CPU
output
Program memory
compute xx
2
compute x x
Costas Busch - LSU 8
3
temporary memory f ( x) x
z 2*2 4
f ( x) z * 2 8
input
x2
CPU
f ( x) 8
Program memory output
compute xx
2
compute x x
Costas Busch - LSU 9
Automaton
temporary memory
Automaton
input
CPU
output
Program memory
Costas Busch - LSU 10
Automaton
temporary memory
Automaton
input
output
transition
state
CPU+ProgramMem = States + Transitions
Costas Busch - LSU 11
Different Kinds of Automata
Automata are distinguished by the temporary memory
• Finite Automata: no temporary memory
• Pushdown Automata: stack
• Turing Machines: random access memory
Costas Busch - LSU 12
Memory affects computational power:
More flexible memory
results to
The solution of more computational
problems
Costas Busch - LSU 13
Finite Automaton
temporary memory
input
Finite
Automaton
output
Example: Elevators, Vending Machines,
Lexical Analyzers
(small computing power)
Costas Busch - LSU 14
Pushdown Automaton
Temp.
memory Stack Push, Pop
Pushdown input
Automaton
output
Example: Parsers for Programming Languages
(medium computing power)
Costas Busch - LSU 15
Turing Machine
Temp.
memory Random Access Memory
input
Turing
Machine
output
Examples: Any Algorithm
(highest known computing power)
Costas Busch - LSU 16
Power of Automata
Simple More complex Hardest
problems problems problems
Finite Pushdown Turing
Automata Automata Machine
Less power More power
Solve more
computational problems
Costas Busch - LSU 17
Turing Machine is the most powerful
known computational model
Question: can Turing Machines solve
all computational problems?
Answer: NO
(there are unsolvable problems)
Costas Busch - LSU 18
Time Complexity of Computational Problems:
P problems:
(Polynomial time problems)
Solved in polynomial time
NP-complete problems:
(Non-deterministic Polynomial time problems)
Believed to take exponential
time to be solved
Costas Busch - LSU 19