Theory of Computation
(Introduction)
Pramod Ganapathi
Department of Computer Science
State University of New York at Stony Brook
January 24, 2021
Hand-axe
Longest-used tool in human history (1.5 million years)
Wheel
Idea behind transportation revolution
(Other uses: potter’s wheel, steering wheel, flywheel)
Simple machines
Lever
Screw
Pulley
Machines
Computing
Counting cattle
1 2 3 4 5
Machine for computing
How do humans compute or calculate or solve problems?
Is it possible to build a computing machine that can mechanically
(i.e., without thinking) simulate the computations performed by
a human brain like that of Galileo or Newton or Einstein?
If so, what problems can or cannot be solved by such a
computing machine?
< 2000 BC: Abacus
35 − 24 14
Not automatic
Operations: Addition, subtraction, multiplication, and division
1643: Pascal’s calculator (Pascaline)
35 + 24 59
Source: Computer Museum History Center
Inventor: Blaise Pascal
Operations: Addition and subtraction
World’s first mechanical calculator
1694: Leibniz’ calculator (Step reckoner)
35 × 24 840
Inventor: Gottfried Wilhelm Leibniz
Operations: Addition, subtraction, multiplication, and division
1820: Colmar’s calculator (Arithmometer)
√
35 5.9161
Inventor: Thomas de Colmar
Operations: Addition, subtraction, multiplication, division,
square root, involution, resolution of triangles, etc
Applications: Financial organizations
1822: Babbage’s calculator (Difference engine)
log 35 1.5441
Source: Science Museum London
Designer: Charles Babbage
The system was never built due to conflicts and insufficient
funding
Operations: Addition, subtraction, multiplication, division,
logarithmic, trigonometric functions, etc
1833: Babbage’s computer (Analytical engine)
Programs Numbers
Source: Science Museum London
Designer: Charles Babbage
The system was never built due to conflicts and insufficient
funding
World’s first general-purpose computer (Turing-complete)
Components: arithmetic logic unit, control flow in the form of
conditional branching and loops, and integrated memory
1843: Lovelace’s algorithm
n Bn
Pic by: Antoine Claudet
Designer: Ada Lovelace
World’s first programmer
Published the first algorithm to be implemented on a computer
The algorithm was used to compute Bernoulli numbers
1931: Gödel’s proof
Axioms Theorems
Source: geni.com
Discoverer: Kurt Gödel
Some mathematical truths cannot be proved
1931: Gödel’s proof
Axioms Theorems
Source: geni.com
Discoverer: Kurt Gödel
Some mathematical truths cannot be proved
(If you cannot prove a mathematical statement, then how do you
know that the statement is true?)
1936: Turing machine
Input Output
Discoverer: Alan Mathison Turing
Creator of computer science
Turing machine – the simplest, the most intuitive, the most
generic, and the most powerful mathematical model of a
computing human brain and a computer
Algorithm and computation
1936: Turing’s proof
Input Output
Discoverer: Alan Mathison Turing
Some computational problems cannot have algorithms
1936: Turing’s proof
Input Output
Discoverer: Alan Mathison Turing
Some computational problems cannot have algorithms
(If you cannot mechanically compute a computational problem,
then why is it called a computational problem?)
1941: Zuse’s Z3
Input Output
Source: http://www.horst-zuse.homepage.t-online.de/
Designer: Konrad Zuse
World’s first working programmable, fully automatic digital
computer (Turing-complete)
1943: McCulloch and Pitts’ finite automata
Input Output
Designers: Warren McCulloch and Walter Pitts
Finite automata – simple model of computation
1945: Mauchly and Eckert’s ENIAC
Input Output
Designers: John Mauchly, J. Presper Eckert
World’s first electronic general-purpose computer
(Turing-complete)
1957: Chomsky’s grammars
Input Output
Designer: Noam Chomsky
Context-free grammar and context-sensitive grammar – models
of computation
1985: Deutsch’s quantum machine
Input Output
Source: twitter
Discoverer: David Deutsch
Quantum model of computation
Model based on quantum physics and not classical physics
Exponentially faster than classical computing for some problems
1989: Lee’s world wide web
Input Output
Source: CERN
Designer: Tim Berners Lee
World wide web – led to Internet revolution
What is a computer/computation/algorithm?
What is a computer/computation/algorithm?
Input info Output info
What is an alphabet?
Definition
An alphabet, denoted by Σ, is a finite, non-empty set of sym-
bols.
Examples
Σ = {a, b}
Unary alphabet Σ = {1}
Binary alphabet Σ = {0, 1}
English alphabet Σ = {a, . . . , z, A, . . . , Z}
Alphanumeric alphabet Σ = {a-z, A-Z, 0-9}
Morse code alphabet Σ = {dot, dash, pause}
DNA alphabet Σ = {A, C, G, T }
Java programming language alphabet
Σ = {a-z, A-Z, 0-9, (, ), {, }, . . . , ; }
{1, 2, 3, . . .} is not an alphabet as the set is not finite
Powers of an alphabet
Definition
Σ = Some alphabet
Σk = Set of all strings of length k over Σ
Σ∗ = Σ0 ∪ Σ1 ∪ Σ2 ∪ · · · = Set of all strings over Σ
Σ∗ is the universal set of all strings
Σ+ = Σ1 ∪ Σ2 ∪ Σ3 ∪ · · · = Set of nonempty strings over Σ
Examples
Let Σ = {a, b}
Σ0 = {}
Σ1 = {a, b}
Σ2 = {aa, ab, ba, bb}
Σ∗ = {, a, b, aa, ab, ba, bb, . . .}
This ordering is called canonical ordering, which is different
from lexicographic ordering
Σ+ = {a, b, aa, ab, ba, bb, . . .}
What is a string?
Definition
A string or word is a finite sequence of symbols chosen from Σ.
A string x ∈ Σ∗ . An empty string is denoted by .
|x| = length of string x
nσ (x) = #occurrences of symbol σ ∈ Σ in the string x
Examples
x = abaaabb from Σ = {a, b}
x = 111 from Σ = {0, 1}
x = from Σ = {a, . . . , z, A, . . . , Z}
x = Bond007 from Σ = {a − z, A − Z, 0 − 9}
x = CGGT CCGC from Σ = {A, C, G, T }
x = a simple hello world C program from
Σ = {if, main, return, for, (, ), {, }, . . . , ; }
What is a language?
Definition
A language over Σ is a subset of Σ∗ .
Examples
The empty language φ.
{, a, aab} - a finite language.
Language of palindromes over {a, b}
{x ∈ {a, b}∗ | na (x) > nb (x)}.
{x ∈ {a, b}∗ | |x| ≥ 2 and x begins and ends with b}
What is a language?
Examples (continued)
Language of your favorite quotations
Language of legal Java identifiers
Language of legal algebraic expressions involving the identifier
a, the binary operations + and ∗, and parentheses
(strings: a, a + a ∗ a, and (a + a ∗ (a + a)))
Language of balanced strings of parentheses.
(strings: , ()(()), and ((((())))))
Language of numeric “literals” in Java (e.g: −41, 0.03, 5.0E −
3).
Language of legal Java programs.
Language of theorems (true statements) in arithmetic
Language of theorems (true statements) in geometry
How can we represent information?
Representation
Strings can be used to represent all types of information
Strings can encode information about names, numbers, dates,
text documents, images, videos, and literally any type of data
Binary strings are the simplest type of strings that can encode
any information
Binary strings can also be viewed as numbers
Hence, numbers can also be used to represent all types of in-
formation
Three major concepts in Theory of Computation
Concept Meaning
Model of computation An abstract but physically realistic machine
that does computation
Language Set of all strings that the computational
model accepts
Grammar Set of rules to derive any string from the
language
Core idea of Theory of Computation
Computation model Language Grammar
Finite automaton Regular language Regular grammar
Pushdown automaton Context-free language Context-free grammar
Linear-bounded Context-sensitive Context-sensitive
automaton language grammar
Turing machine Recursively enumerable Unrestricted grammar
language
No computer or Undecidable language ?
no algorithm
We will spend an entire semester for this course trying to
understand this table.
Three major topics of Theory of Computation
Covered topic Questions
Automata theory What can be computed with extremely lim-
ited space?
Computability theory What can be computed?
Can a computer solve all computational
problems, given enough (finite) time and
space?
Complexity theory How fast can we solve a problem?
How small space can we use to solve a prob-
lem?
Not covered topic Questions
Algorithms How can a given computational problem be
solved efficiently (less time and space)?
What can be computed?
Problem DFA PDA TM
Draw money from ATM 3 3 3
Check if a string is present in another string 3 3 3
Linux regular expressions 3 3 3
Parse if-else blocks and for loops in C/C++/Java pro- 7 3 3
grams
Parse nested arithmetic expressions 7 3 3
Parse markup languages such as HTML 7 3 3
Multiply two integers 7 7 3
Factorize an integer into two integers 7 7 3
Find a shortest path between two cities 7 7 3
Check if a computer program halts or terminates 7 7 7
Check if a computer program crashes 7 7 7
Check if a computer program is correct 7 7 7
DFA: Deterministic Finite Automaton
PDA: Pushdown Automaton
TM: Turing Machine
Applications of Theory of Computation
Topic Applications
Finite automaton Regular expressions
Traffic signals, Vending machines, ATMs
String matching
Lexical analysis in a compiler
Combination/sequential digital logic circuits
Spell checkers
Pushdown automaton Stack applications
Balanced parentheses
Syntax analysis in a compiler
Evaluating arithmetic expressions
Linear-bounded automaton Variable declaration and definition in a compiler
Genetic programming
Turing machine Understanding computation
Mother of classical computers and algorithms
Grandmother of quantum computers
Complexity theory Cryptography
Turing-complete systems
Time Turing-complete system Designer
1830s Analytical engine Charles Babbage
1930s Recursive functions Stephen Kleene
λ-calculus Alonzo Church
Turing machine Alan Turing
− Unrestricted grammar −
1940s Z3 Konrad Zuse
Tag systems Emil Leon Post
1960s Markov’s algorithms Andrey Markov, Jr.
Unlimited register machines John Shepherdson, Howard Sturgis
1970s C Dennis Ritchie
Game of life John Conway
1980s Rule 110 Stephen Wolfram
Quantum computers David Deutsch
What can be computed?
Problems
[Halting program]
Write a computer program that takes a computer program P
as input and outputs whether P halts (i.e., terminates) or not.
[Correctness program]
Write a computer program that takes a computer program P
and a specification s for P as input and outputs whether P is
correct or not (i.e., if P follows the input-output specification
s or not).
[Equivalence program]
Write a computer program that takes two computer programs
P1 and P2 as input and outputs whether P1 is functionally
equivalent to P2 or not.
[Self-replicating program]
Write a computer program that does not take any input and
outputs its own source code.
What can be computed?
Problems
[Halting program] B Impossible
Write a computer program that takes a computer program P
as input and outputs whether P halts (i.e., terminates) or not.
[Correctness program] B Impossible
Write a computer program that takes a computer program P
and a specification s for P as input and outputs whether P is
correct or not (i.e., if P follows the input-output specification
s or not).
[Equivalence program] B Impossible
Write a computer program that takes two computer programs
P1 and P2 as input and outputs whether P1 is functionally
equivalent to P2 or not.
[Self-replicating program] B Possible
Write a computer program that does not take any input and
outputs its own source code.
