CS311Computational Structures
Problems, Languages,
Machines, Computability,
Complexity
Lecture 1
Andrew P. Black
Andrew Tolmach
1
The Geography Game
Could you write a computer program to
play the geography game?
Face Recognition
Are these the
same person?
Can you
program a
computer to
recognize
people?
3
Face Recognition
Are these the
same person?
Can you
program a
computer to
recognize
people?
3
Face Recognition
Are these the
same person?
Can you
program a
computer to
recognize
people?
3
Face Recognition
Are these the
same person?
Can you program
program
a
computer
a to
computer to
recognize
recognize
people?
people?
3
Computer Programs
Can you write a
computer program that
looks at a windows
driver and decides if it
will terminate within
100 ms?
Whats the course about?
What it really means to be a computer
Problems as formal language recognition
Algorithms as formal machine programs
Different models of computation.
What computers can do, and what they cant do
Whats easy to compute, and whats hard
Whats the course about?
What it really means to be a computer
Problems as formal language recognition
Algorithms as formal machine programs
Different models of computation.
What computers can do, and what they cant do
Whats easy to compute, and whats intractable
Major Technical Topics
Regular languages and regular expressions,
deterministic and nondeterministic automata,
closure properties, pumping lemma.
Context-free languages and pushdown automata,
parsing, closure properties, pumping lemma.
Turing machines, Church-Turing thesis, equivalent
models of computation.
Computability: decidable and undecidable problems.
Complexity classes: P, NP, completeness.
8
Official Course Objectives
Upon the successful completion of this course students will be able to:
1.
Find regular grammars and context-free grammars for simple
languages whose strings are described by given properties.
2.
Apply algorithms to: transform regular expressions to NFAs, NFAs
to DFAs, and DFAs to minimum-state DFAs; construct regular
expressions from NFAs or DFAs; and transform between regular
grammars and NFAs.
3.
Apply algorithms to transform: between PDAs that accept by final
state and those that accept by empty stack; and between contextfree grammars and PDAs that accept by empty stack.
4.
Describe LL(k) grammars; perform factorization if possible to
reduce the size of k; and write recursive descent procedures and
parse tables for simple LL(1) grammars.
5.
Transform grammars by removing all left recursion and by
removing all possible productions that have the empty string on the
right side.
9
6.
Apply pumping lemmas to prove that some simple languages are not
regular or not context-free.
7.
State the Church-Turing Thesis and solve simple problems with
some of the following models of computation: Turing machines
(single-tape and multi-tape); while-loop programs; partial recursive
functions; Markov algorithms; Post algorithms; the lambda calculus;
and Post systems.
8.
Describe the concepts of unsolvable and partially solvable; state the
halting problem and prove that it is unsolvable and partially
solvable; and use diagonalization to prove that the set of total
computable functions cannot be enumerated.
9.
Describe the hierarchy of languages and give examples of languages
at each level that do not belong in a lower level.
10.
Describe the complexity classes P, NP, and PSPACE.
11.
Use an appropriate programming language as an experimental tool
for testing properties of computational structures.
10
Course Tools
What you need for this course:
Textbook Hopcroft, Motwani & Ullman
Pencil and paper
Brain and time
What you dont need for this course:
Knowledge from the prerequisite courses (esp. CS250)
A computer (except just a little bit now and then)
An attitude of fear and loathing
This is a theoretical subject...embrace it!
11
Things to Do
Read the syllabus
Register for the course!
Attend class and take notes
Read the class web page
[Link]
Sign up for the email list
Read Chs. 1,2.1-2 of the IALC textbook
Take the Entrance Exam
12
Gradiance
On-line tutoring and quiz tool from AddisonWesley
Set up an account and connect to this course:
[Link]
SSOConnectorLogin
Course Token is TBA
This token is NOT on the web site, so write it down!
13
Warning!
I expect you to read the class web page
I expect you to read the class email list
I expect you to read and work problems
from the textbook!
If you cant or wont or dont have time
to work independently, you will have trouble
with this course.
14
Review of languages
Languages are sets of strings of symbols
drawn from some alphabet
Some language examples:
L1 = {anbn | n 2}
L2 = {anbm | n, m 0}
L3 = {anbn | n 0}
L4 = {anbmcp | n, m, p 0}
L5 = {anbncn | n 0}
L1 L3 L2 L4
L5 L4
15
Problems as Languages
Why do we care about languages (in this sense)?
They show up everywhere in CS
programming languages, HTML and XML documents, ...
(They also show up in human linguistics...)
But the big reason for this course: we can use
formal languages to describe problems
In particular, we can reduce decision problems (is
P true?) to language membership problems (is
the encoding of P in some language L?)
16
Example: tic-tac-toe
O_X
O_X
_ O_
___
___
___
O_X
O__
___
Decision problem: for a given configuration, can
the next player always win?
Encode configurations as strings, e.g.
OBXOBXBOB BBBBBBBBB OBXOBBBBB
Define language L = set of configuration strings for
which the next player can always win.
For configuration C, we ask is the encoding of C
in L?
17
Example: arithmetic
Decision problem: given p,q,r , is pq = r?
Encoding is simple
E.g. 67 = 42? 79 = 64? 88 = 91?
E.g. 6B7B42 7B9B64 8B8B91
Define L = {pBqBr | p,q,r {0..9}* and pq=r}
For a particular p,q,r, ask is pBqBr L?
18
Is restriction to decision problems too limiting?
19
and its cardinality
= {0, 1, 2, 3, 4, }
How can we define without ?
By induction
1. 0
2. if x , then x+1
3. these are the only elements of
20
and its cardinality
= {0, 1, 2, 3, 4, }
How can we define without ?
By induction
1. 0
2. if x , then x+1
3. these are the only elements of
20
Cardinality of Sets
21
Cardinality of Sets
How can we decide if two sets are of the
same size?
21
Cardinality of Sets
How can we decide if two sets are of the
same size?
Set up a bijection (one-to-one and onto
mapping) between the elements of the
sets
21
Cardinality of Sets
How can we decide if two sets are of the
same size?
Set up a bijection (one-to-one and onto
mapping) between the elements of the
sets
Is there a bijection between and even ?
21
Cardinality of Sets
How can we decide if two sets are of the
same size?
Set up a bijection (one-to-one and onto
mapping) between the elements of the
sets
Is there a bijection between and even ?
Sure!
21
Countability
A countable set is one that is either
finite or has the same cardinality as
Any subset of a countable set is countable
, even are countable
We reason about countable sets using
induction
22
Proofs by Induction
23
Proofs by Induction
For example, to prove some property P(n)
for all natural numbers n, it suffices to prove
Base case: P(0) is true.
Inductive step: If P(n) is true, then P(n+1) is
true, forall n 0.
23
Proofs by Induction
For example, to prove some property P(n)
for all natural numbers n, it suffices to prove
Base case: P(0) is true.
Inductive step: If P(n) is true, then P(n+1) is
true, forall n 0.
Why is this enough?
Every natural number can be produced by
starting with 0 and repeatedly adding 1.
So, we can prove P(n) for any n by applying
inductive step n times, then base case.
23
Prove by Induction
Theorem: 0 + 1 + 2 + ... + n = n(n+1)/2.
State the induction hypothesis:
let H(n) be 0 + 1 + 2 + ... + n = n(n+1)/2
Prove the base case: H(0)
H(0) is 0 = 0 (1)/2
This is true because 0 is the zero of multiplication
24
A simple inductive proof
Prove the inductive step:
We have to show that H(n)
H(n + 1)
H(n) is 0 + 1 + 2 + ... + n = n(n+1)/2
add (n+1) to both sides:
0+1+2+...+n + (n+1)
= n(n+1)/2 + (n+1)
= n(n+1)/2 + 2(n+1)/2
= (n+2)(n+1)/2
H(n + 1)
= (n+1)((n+1)+1)/2
QED.
25
Countability of
its countable because
we can line up its
elements in order and
count them
Why do we do it in this
wierd zig-zag fashion?
26
Uncountability of
To Prove: The set of real numbers {x | 0 < x < 1}, is uncountable.
Proof by contradiction: Suppose that the set of reals is countable. Then we
can claim to make an enumeration of all of them, and that it looks something
like this:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
0.38602563708....
0.57350762050....
0.99356753207....
0.25763200456....
0.00005320562....
0.99035638567....
0.55522730567....
..........................
..........................
27
Now we claim to have listed every decimal between 0 and 1. But you can
always give me a decimal which is not in my table! Do it like this:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Take the first digit = 7 (not 3); Decimal = 0.7.....
Take the second digit = 3 (not 7); Decimal = 0.73.....
Take the third digit = 6 (not 3); Decimal = 0.736.....
Take the fourth digit = 7 (not 6); Decimal = 0.7367.....
Take the fifth digit = 4 (not 5); Decimal = 0.73674.....
Take the sixth = 4 (not 6); Decimal = 0.736744.....
................ 0.736744?.....
................ 0.736744??.....
................
The rule is: make sure that the kth digit of the new decimal is not equal to
the kth digit of the kth number in my original list. (We avoid using 9 and 0.)
28
Complete the Argument
-
If the author of the enumeration says: the number that you
wrote is already in my list, at position 153, you can say:
No! My number differs from that in the 153rd decimal digit.
So, the number you wrote in not in the list.
Therefore, the list was not a complete enumeration of all the
real numbers.
But we can repeat this argument for any supposed
enumeration
So there is no effective enumeration of
29
Uncomputability
Is there anything a computer cannot do,
given sufficient time, memory, etc.?
Yes, and we can prove it!
Informally today
By a counting argument
By showing a particular uncomputable problem
More formally in the remainder of the course
30
More countability facts
For any alphabet , the set of all finite strings *
over that alphabet is countable
E.g., if = {a,b,c}, then
* = {,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,...}
But the set of infinite strings over even the very
simple alphabet {0,1} is uncountable
By simple modification of diagonalization argument for reals
31
So many problems...
Each language A over corresponds to a unique
infinite string XA over {0,1}, its characteristic
sequence:
Enumerate * as {s,s,s,...}
Define i = 1 if si A, Xi = 0 otherwise
XA = X1X2X3...
So the set of all languages over is uncountable
Since each language corresponds to a problem,
there are an uncountable number of problems
32
... so few solutions
Lets assume that every algorithm can be written
down as a finite sequence of symbols over a
fixed alphabet
For example as a computer program written in ASCII
Then the number of algorithms is countable
Since there are uncountably many decision
problems and only countably many algorithms,
there must be some decision problems for which
there is no algorithm!
Indeed, uncountably many of them...
33
A specific uncomputable
problem
Suppose wed like to write a program H that
behaves as follows:
H reads as input the text of another program G and an input
string I.
H answers the following question: when G is run on input I,
does it print the string Hello World! ?
If so, H prints the string yes; otherwise it prints no
(Assume all programs are written in the C language; it
doesnt really matter.)
34
Graphically...
yes
H
no
35
Examples of how H works
For example, if H is given the program G =
void main() {
if (getc() == a) printf(Hello world!\n);
}
it should surely output yes if the input I begins
with an a and no otherwise
Of course, sometimes it will be harder, e.g., G =
void main() {
if (foo(bar(baz(...))) /* will have to look at these */
printf(Hello world!\n);
}
36
Another H example
Still worse, we might give it something like G =
void main() {
int n, total, x,y,z;
scanf(%d,&n); /* read n from standard input */
for (total = 3;; total++) {
for (x = 1; x <= total-2; x++)
for (y = 1; y <= total-x-1; y++) {
z = total - x - y;
if (pow(x,n) + pow(y,n) == pow(z,n))
printf(Hello,world!\n); }}}
Now G has to be at least as smart as 300+ years
of human mathematicians
from Fermat (1637) to Wiles (1995)
But still, why not?
37
Why H is impossible
Lets assume we have H, and show that this
leads to an impossibility.
If we have H, we can easily modify it in two ways,
producing a new program H'.
Instead of printing no, H' prints Hello world!
Instead of reading both G and I as input, it uses the same
input G twice as program to test and as input for that
program
38
Graphically
H'
G
yes
no
yes
Hello world!
39
Self-application
H'
G
yes
yes
H
no
Hello world!
Now, what will H' do if it is given itself as input?
If it would not print Hello, world! then it prints
Hello, world! oops!
Paradoxical situation!
If it would print Hello, world! then it prints yes
oops!
So H' cant exist. So H cant exist either.
40
Complaints?
Not a very realistic problem?
The argument was too vague?
Once we have one unsolvable problem about programs, we
can easily produce others. In fact, every non-trivial property
of programs is undecidable
Well spend most of the course learning to be more careful
So theres no C program. But does that mean
theres no algorithm?
Cant prove this, but well give convincing evidence for the
so-called Church-Turing Hypothesis
41
