Transcript i+1
CS 208: Computing Theory
Assoc. Prof. Dr. Brahim Hnich
Faculty of Computer Sciences
Izmir University of Economics
Computability Theory
Decidability
Motivation
Turing machines:
a general purpose computer;
Formalizes the notion of an algorithm (Church-Turing
thesis)
We now turn our attention into the power of
algorithms (i.e. Turing machines) to solve
problems
Try to understand the limitation of computers
Is studying decidability useful?
An example of a decidable problem:
Is a string a member of a context-free language?
This problem is at the heart of the problem of
recognizing and compiling programs in a
programming language
Preliminaries
Acceptance problem: Does DFA B accept input
string w?
For convenience we use languages to represent
various computational problems
So, the acceptance problem can be expressed as a
language
ADFA = {<B,w>| B is a DFA that accepts input
string w}
Preliminaries
ADFA = {<B,w>| B is a DFA that accepts input
string w}
The problem of testing whether a DFA B accepts a
string w is the same as testing whether <B,w> is a
member of the language ADFA
Thus, showing that the language is decidable is the
same as showing that the computational problem is
decidable!
Examples of Decidable Languages
ADFA = {<B,w>| B is a DFA that accepts input
string w}
Theorem: ADFA is a decidable language
Proof idea: Design a TM M that decides ADFA
How?
On input <B,w>
Simulate B on input w
If simulation ends in accepting state, accept, otherwise reject
Examples of Decidable Languages
ANFA = {<B,w>| B is a NFA that accepts input
string w}
Theorem: ANFA is a decidable language
Proof idea: Design a TM M that decides ANFA
How?
On input <B,w>
Convert NFA B into equivalent DFA C
Run previous TM on input <C,w>
If that TM accepts, accept, otherwise reject
Examples of Decidable Languages
AREX = {<R,w>| R is a regular expression that
generates string w}
Theorem: AREX is a decidable language
Proof idea: Design a TM M that decides AREX
How?
On input <R,w>
Convert R into equivalent NFA C
Run previous TM on input <C,w>
If that TM accepts, accept, otherwise reject
Examples of Decidable Languages
ACFG = {<G,w>| G is a CFG that generates string
w}
Theorem: ACFG is a decidable language
Proof idea: Design a TM M that decides ACFG
How?
(Interested students can read the book p. 156)
Examples of Decidable Languages
Theorem: Every CFG is a decidable
Relationships among classes of
languages
Context-free
regular
decidable
enumerable
The Haling Problem
One of the most philosophically important
theorems of the theory of computation
Computers (and computation) are limited ina very
fundamental way
Common, every-day problem are unsolvable
Does a program sort an array of integers?
Both program and specification are precise
But, automating the verification is undecidable
No computer program can perform the task of checking the
program against the specification!
Halting Problem
Halting problem: Does a Turing machine accept a
string?
ATM = {<M,w>| M is a Turing machine that accepts
string w}
Theorem: ATM is undecidable
Halting Problem
Before proving that ATM is undecidable, note that
ATM is enumerable
How? Design a Turing Machine U that
recongnizes ATM
On input <M,w>
Simulate M on w
If M ever enters its accept state, accept, and if M ever
enters its reject state reject
U is called a universal Turing machine
Diagonalization
Diagonalization: a very crucial technique that is
useful to prove undecidability ATM
Question: what does it mean to say that two
infinite sets are the same size?
Answered by Georg cantor in 1873
How? Pair them off!
Correspondence
Recall a correspondence f: A B is a bijection:
Injective
Surjective
Question: what does it mean to say that two
infinite sets are the same size?
Answer: A and B are the same size if there is a
correspondence from A to B
Correspondence
Question: in a crowded room, how can we tell if
there are more people than chairs, or more chairs
than people?
Correspondence
Question: in a crowded room, how can we tell if
there are more people than chairs, or more chairs
than people?
Answer: Establish a correspondence: ask
everyone to sit down!
Correspondence
Claim: The set of Natural numbers has the same
size as the set of even numbers!
Correspondence
Claim: The set of Natural numbers has the same
size as the set of even numbers!
Proof: Establish a correspondence
Let f(i)=2i
Remark: a proper subset of A can be the same size
as A!!!!
Countable
Definition: A set A is countable iff
Either it is finite, or
It has the same size as N, the set of natural numbers
We have just seen that the set of even numbers is
countable
Claim: The set Z of integers is countable
Proof: Define f:NZ by
f(i)=i/2
f(i)=-(ceil(i/2) +1)
If i is even
if i is odd
Challenge
In Heaven, there is a hotel with a countable
number of rooms
One day, the society of Prophets, Oracles, and AI
researchers hold a convention that books every
room in the hotel
Then one more guest arrives, angrily demanding
a room
You are the manager. What to do?
Challenge
Then one more guest arrives, angrily demanding
a room
You are the manager. What to do?
Answer: Ask the guest in room i to move to room
i+1, and put the new comer in room 1!
Challenge
Then a countable number of guests arrive, all
angrily demanding a room
Now What to do?
Challenge
Then a countable number of guests arrive, all
angrily demanding a room
Now What to do?
Answer: Ask the guest in room i to move to room
2i, and put the new comers in odd numbered
rooms !!!!
(Infinity is such an amazing thing!!)
Rational Numbers
Let Q ={m/n | m and n are natural numbers}
Theorem: Q is countable
What is the correspondence between N and Q?
Rational Numbers
1/1
1/2
1/3
1/4
1/5
1/6
1/7
1/8
……..
2/1
2/2
2/3
2/4
2/5
2/6
2/7
2/8
……..
3/1
3/2
3/3
3/4
3/5
3/6
3/7
3/8
……..
4/1
4/2
4/3
4/4
4/5
4/6
4/7
4/8
……..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Rational Numbers
1/1
1/2
1/3
1/4
1/5
1/6
1/7
1/8
……..
2/1
2/2
2/3
2/4
2/5
2/6
2/7
2/8
……..
3/1
3/2
3/3
3/4
3/5
3/6
3/7
3/8
……..
4/1
4/2
4/3
4/4
4/5
4/6
4/7
4/8
……..
Enumerate numbers along Northeast and Southwest diagonals,
and skip duplicates
Rational Numbers
1/1
1/2
1/3
1/4
1/5
1/6
1/7
1/8
……..
2/1
2/2
2/3
2/4
2/5
2/6
2/7
2/8
……..
3/1
3/2
3/3
3/4
3/5
3/6
3/7
3/8
……..
4/1
4/2
4/3
4/4
4/5
4/6
4/7
4/8
……..
Does this mean that every infinite set is countable?
The Real Numbers
Theorem: R, the set of reals is uncountable
Cantor introduced the diagonalization method to
prove this theorem!
The Real Numbers
Theorem: R, the set of reals is uncountable
Proof: By contradiction
Assume there is a correspondence between N and R
Write it down
n
f(n)
1 3.143……
2 55.435….
3 3456.75…
4 456.655…
We show now that there a number x not in the list!
Diagonalization
Proof: By contradiction
n
1
2
3
4
f(n)
3.143……
55.435….
3456.75…
456.655…
Pick x between 0 and 1, so non-zero digits follow decimal point
First fractional digit of f(1) is 1
Pick first fractional digit of x to be different, say 2
Second fractional digit of f(2) is 4
Pick second fractional digit of x to be different, say 6
And so on ….
X=0.2487….
Thus x is not the image of any natural which is a contradiction
So, R is uncountable!
Important implications
Previous theorem has an important application to
the theory of computation
It shows that some languages are not decidable!
Or even Turing machine recognizable
There are languages that are not enumerable
The set of Turing machines is countable
The set of languages is uncountable
Important implications
Theorem: The halting problem is undecidable
Proof uses diagonalization technique (see bok those
interested)
Theorem: A language is decidable if and only if it
is both Turing-recognizable and co-Turing
recognizable
In other words, a language is decidable if and
only if it and its compliment are Turingrecognizable (enumerable)
A non-enumerable language
Corollory: if L is not decidable, then either L or its
compliment is not enumerable
????
Co-enumerable
enumerable
decidable
Conclusions
Decidable languages
Halting problem
diagonalization method
undecidable example