CT111-3-2
Computing Theory
Introduction
CT111-3-2- Computing Theory Introduction
Contact
• Lecturer: Prof. Dr. R. Logeswaran
• Email: Logeswaran@apu.edu.my
Important: APU Student Email Policy -
students must only use their official APU
email account for correspondence.
• Consultation: email to check availability.
CT111-3-2- Computing Theory Introduction
Learning Outcomes
LO1: Design automata and generate regular
expressions for specified languages.
LO2: Design and analyse context-free
grammars for specific syntactic rules.
LO3: Describe and Design Turing machines
to accomplish specified computations.
LO4: Explain and discuss complexity and
decidability of problems.
CT111-3-2- Computing Theory Introduction
Assessment
• COURSEWORK (50%) (LO1, 2 and 4):
– Individual assignment to design different types of
FSM and grammars, convert between equivalently
powerful notations for a language, determine string
membership to a language, and research about
complexity and decidability problems and their
significance.
• EXAM (50%) (LO1,2 and 3):
– Written examination to demonstrate understanding
automata, regular expressions, context free
grammars, and the Turing machines.
CT111-3-2- Computing Theory Introduction
Main References
• Hopcroft, J.E, Motwani, R., Ullman, J.D. (2007),
Introduction to Automata Theory, Languages, and
Computation (3rd Edition). Pearson (ISBN: 978-
0321455369)
• Sipser, M. (2012). Introduction to the Theory of
Computation (3rd Edition). Course Technology (ISBN:
978-1133187790)
• Maheshwari, A., Smid, M. (2014), Introduction to Theory
of Computation. Carleton University, Ottowa CA. e-book
available at:
http://cglab.ca/~michiel/TheoryOfComputation/TheoryOf
Computation.pdf
•
CT111-3-2- Computing Theory Introduction
Computation
• Computation is a general term for any type of
information processing that can be represented
as an algorithm precisely. (mathematically)
Examples:
• Adding two numbers in our brain, on a piece of
paper or using a calculator.
• Converting a decimal number to its binary
presentation or vise versa.
CT111-3-2- Computing Theory Introduction
What is computable?
• Examples:
– check if a number n is prime
– compute the product of two numbers
– sort a list of numbers
– find the maximum number from a list
• Hard but computable:
– Given a set of linear inequalities, maximize a linear
function
Eg. maximize 5x+2y
3x+2y < 53
x < 32
5x – 9y > 22
CT111-3-2- Computing Theory Introduction
Computing Theory
Primary aim of the course: What is “computation”?
• Can we define computation without referring to a modern computer?
• Can we define, mathematically, a computer?
(yes, Turing machines)
• Is computation definable independent of present-day engineering
limitations, understanding of physics, etc.?
• Can a computer solve any problem, given enough time and disk-
space?
Or are they fundamental limits to computation?
In short, understand the mathematics of computation
CT111-3-2- Computing Theory Introduction
Computing Theory
-What can be computed?
-Can a computer solve any
Computability
problem, given enough time and disk-
space?
Complexity - How fast can we solve a
problem?
- How littledisk-space can we
use to solve a problem
Automata
-What problems can we solve
given really very little space?
(constant space)
CT111-3-2- Computing Theory Introduction
Computing Theory
What problems can a computer solve?
Not all problems!!!
Computability Eg. Given a C-program, we
cannot check if it
will not crash!
Verification of correctness of programs
is hence impossible!
Complexity
(The woe of Microsoft!)
Automata
CT111-3-2- Computing Theory Introduction
Computing Theory
What problems can a computer solve?
Even checking whether a C-program will
Computability halt/terminate is not possible!
input n;
assume n>1; No one knows
Complexity while (n !=1) { whether this
if (n is even) terminates on
n := n/2; on all inputs!
else
n := 3*n+1;
Automata }
17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
CT111-3-2- Computing Theory Introduction
Computing Theory
How fast can we compute a function?
Computability How much space do we require?
• Polynomial time computable
• Non-det Poly Time (NP)
• Approximation,
Complexity Randomization
Functions that cannot be computed
fast:
Automata • Applications to security
• Encrypt fast,
• Decryption cannot be
done fast
CT111-3-2- Computing Theory
• Introduction
RSA cryptography,
Computing Theory
Machines with finite memory:--
traffic signals, vending machines
Computability hardware circuits
Tractable.
Applications to pattern matching,
Complexity modeling,
verification of hardware, etc.
Automata
CT111-3-2- Computing Theory Introduction
Computing Theory
What can we compute?
-- Most general notions of
Computability computability
-- Uncomputable functions
What can we compute fast?
-- Faster algorithms, polynomial time
Complexity
-- Problems that cannot be solved fast:
* Cryptography
What can we compute with very little space?
Automata -- Constant space (+stack)
* String searching, language parsing,
hardware verification, etc.
CT111-3-2- Computing Theory Introduction
I
N
Computing Theory
C Turing machines (1940s):
-- The most general
R notion of computing
Turing machines
-- The Church-Turing
E thesis
-- Limits to computing:
A Uncomputable
Context-free languages
Context-free functions
--- Grammars, parsing
S
C --- Finite state machines with recursion (or stack)
I . languages --- Still a simple setting; but infinite state
O
N
Automata:
M
Automata --- Foundations of computing
G
--- Mathematical methods of argument
P
--- Simple setting
L
E
CT111-3-2- Computing Theory Introduction
Alonzo Church
First notions of computable functions
• First language for programs
• -- lambda calculus
• -- formal algebraic language
• for computable functions
Alonzo Church:
1903 - 1995
CT111-3-2- Computing Theory Introduction
Alan Turing
• “Father of computer science”
• Defined the first formal notion of a
computer (Turing machine) in 1936:
Proved uncomputable functions exist
(“halting problem”)
• Church-Turing thesis: all real
world computable functions are
Alan Turing: 1912 - 1954
Turing m/c computable
• Cryptanalysis work breaking
Enigma in WW-II
CT111-3-2- Computing Theory Introduction
Noam Chomsky
• Introduced the notion of formal
languages arguing generative grammars
are at the base of natural languages
• Hierarchy of formal languages that
coincides with computation
• Eg. Context-free grammars capture
most skeletons of prog. languages
Noam Chomsky: 1928-
“Logical Structure of Linguistic Theory” (1957)
CT111-3-2- Computing Theory Introduction
Rabin and Scott
• Automata: machines with
finite memory
• “Finite Automata and Their
Decision Problem”
- Rabin and Scott (1959)
• Introduced nondeterministic automata
and the formalism we still use today
• Initial motivation: modeling circuits
• Turing Award (1976)
CT111-3-2- Computing Theory Introduction
I
N
Theory of Computation
C
Turing: 1931
R
Turing machines
E
A
Context-free Chomsky: 1957
S
C
I . languages
O
N
M
G Automata Rabin-Scott: 1959
P
E
CT111-3-2- Computing Theory Introduction
A result you would know at the end...
• Proving that it is impossible to check if
a C program will halt.
• Formal proof!
You can convince a friend using a paper-
argument
• No computer *ever* will solve this
problem (not even a quantum computer)
CT111-3-2- Computing Theory Introduction
Textbook
Michael Sipser
Introduction to Theory
of Computation
(2nded; 1st ed may be
ok)
Hopcroft-Ullman
CT111-3-2- Computing Theory Introduction
How to do well…
• This is essentially a math course:
– you must learn the concepts well; if you don’t there’s
almost no chance of success
– if you do learn the concepts, there is very little else (facts,
etc.) to learn; you can do really well!
– You must do problems. There’s no replacement for this.
– Attending lectures is highly adviced!
• It will be very hard to learn the concepts by yourself / from
textbook.
– Don’t postpone learning; you will not be able to “make
up” later. Topics get difficult quickly.
– Come regularly to discussion sections; you will learn a lot
by working out problems and learning from fellow
CT111-3-2- Computing Theory Introduction
