A poem by Piet Hien
- A problem worthy of attack
- Proves it's worth
- By hitting back.
Recall:
- An algorithm is a TM that always halts.
- A recursive language has an algorithm that determines if a string
is in the language or not.
- A recursively enumerable(RE) language has a TM that determines if a
string is in the language, but if it is not in the language, or may
halt or it may not stop.
- If a language is non-RE then there is no TM that always accepts
the right strings... sometimes it fails on acceptable strings.
Failing includes not halting.
9.3.1 Reductions 383
Here is an analogy:
We can reduce the problem run a Java program
to run the Java Virtual machine because we can write a compiler
from Java into bytecode and the JVM runs bytecode.
We can take this reduction a little further because Sun provides
a Java Compiler that is avaliable as a bytecode application... so
if we can run the JVM then we can compile any program and run the
result.
So we can conclude: if their exists a JVM then we can run Java.
We can also conclude: if we can't run Java then we can't have a
JVM.
Some reductions are clever in this chapter.
Before we reduced problem P1 to Problem P2 by showing how to
construct P1 from P2 by adding extra algorithms or machines A
and B to P2.
The idea was that if if there is a solution to P2 then there must be a solution
to P1 -- but we knew that P1 could not be solved.
In this chapter we do something subtle. We design an extra machine
or algorithm A that takes in the description of a machine and its
data and produces a new machine description (and its data perhaps).
This is then fed to a hypothetical machine that solves P2 -- as data,
and as a result P2 solves P1 on the original machine.
Again we argue that if we have an algorithm for P2 then we would
have an algorithm for P1. Or that IF we have a TM that solves P2
(but it sometimes fails to halt), THEN we would have a similar TM for
P1. In either case we have already shown that algorithms/machines
for P1 don't exist... so they don't exit for P2.
This is subtle. The simpler reduction was a hardware technique: wire
up a solution to P1 to other algorithm/machines and solve P2. Now we have
a software technique. We construct a compiler that lets us convert
P1 problems into P2 problems. So if we can solve P2, we must have
a solver for P1 too... . So if P1 can not be solved, neither can P2.
If there is a reduction from P1 to P2 then
- If P1 is undecidable then so is P2,
- If P2 is non-RE then so is P2
The structure of the proof: prove each part in turn. Each part has form
if hyp then Conc and is proved by assuming hyp and using it
to prove the conc.
Structure
Let
- There be a reduction from P1 to P2
Let- P1 be undecidable,
- ...
- P2 is undeciadable
(Close Let )
Let- P1 be non-RE,
- ...
- P2 is non-RE
(Close Let )
(Close Let )
Can you give an example of this theorem, so it will make more sense
Example 1.
If you have a program that would can
be used to solve the Halting Problem -- then you know that your
program doesn't always work.
Example 2.
Theorem 9.8 L[ne] is RE
Use a NTM to guess a string that fits the input machine and
then use the universal TM U to verify the guess.
Theorem 9.9 L[ne] is not Recursive
If we had a machine that halts having decided that machine M accepts
something.... then we can construct U from it. But U is
not recursive. So our L[ne] machine is also not recursive.
Ch 9.3 pp 386 -- Theorem 9.9
Please explain Theorm 9.9. Is w always constant?
The idea is to construct an algorithm that will take
any (M,w) and make a new machine M from them.
So w is not a constant but a parameter or argument of the algorithm.
It could be any string/word, and each time our algorithm will produce
a different M'. In C/C++/Java it would be like this:
Machine algorithm(Machine M, Input w){ ....; return M';}
9.3.3 Rice's Theorem and Properties of the RE Languages 387
[ Rice's_theorem ]
Box page 388 Problems and their complements are often different
Theorem 9.11 Rice's Theorem
Ch 9.3 pp 388 -- Could you please explain theorem 9.11
Theorem 9.11 means that just about any question you ask about the outputs
of a computer can not be computed by a computer, OR it is a question
where the answer is always the same -- a trivial question.
- Does this TM machine accept anything?
- Does this TM accept 17 strings, no more and no less?
- L_e
- L_ne
- Does this TM print a rude word on its tape?
With a trivial property the answer does not depend on the TM at all.
The answer is always the same.
Notice
When we talk about a property we are not talking about one
language but a collection of languages. For example: not the set of
strings with an even number of 1's, but the languages that have an even
number of strings!
We decide a property P if we can construct a TM that reads in
the description of a TM and decides if the input TM meets the property.
When we say P is an undecidable property
we mean the language of codes for TM M that satisfy P is undecidable.
Also note: the theorem involves the RE languages AND undecidability.
This is a powerful result and so needs a complex and subtle proof.
Can you explain Theorem 9.11. I do not understand why Every nontrivial
property of the RE languages is undecidable.
This is not an obvious result hence the complex proof.
Could you go over Theorem 9.11, I am having trouble understanding the given
proof?
The book says the proof of Theorem 9.11 is a proof by construction, but it
looks (from #3 on page 389) like it is a proof by contradiction. Are they
constructing a proof by construction out of a proof by contradiction, or is
there something I am not seeing?
Ch 9.3 pp 389 -- Rice\'s Theorem
What is the M-sub-L mentioned in the reduction proof for Rice\'s theorem?
I found it difficult to estract the structure of this proof. Here is my
third attempt. I'm using the notation from my
[ ../maths/logic_25_Proofs.html ]
page.
Outline of proof
Let
- (let)|- (1): P be a property of RE languages and non-trivial.
- Lp::=language of TM codes M such that M decides P.
- (1)|-P is a set of RE languages that is neither empty nor all of them,
- (set theory)|-{} is in P or {} is not in P.
Case
- (let)|- (1.1): {} is not in P.
- (1.1)|-some L!={} is in P.
- (1)|-L is RE,
- (above)|-Some TM Ml accepts L ,
- (ei)|-Ml is a TM that accepts L.
- Reduce Lu to Lp
-- showing an algorithm that given (M,w), uses Ml and M, to construct a machine M' that accepts (M,w) if and only if M accepts w.
- If Lp is decidable then when applied to M' it decides Lu.
- but Lu is undecidable,
- (above)|-Lp is undecidable,
- (above)|-P is an undecidable property
(End of Case)
Case
- (let)|- (2): {} is in P
- Consider the complement of P and use previous case
- ...
- (above)|-P is an undecidable property
(Close Case )
- (above)|-in either case P is an undecidable property.
(Close Let )
- (above)|-If P is a non-trivial property of RE languages then P is an undecidable property.
- (above)|-nontrivial==>undecidable!
Notes:
- Lu::=The universal Language of all (M,w) such that M accepts w,
[ 10.html#9.2.3 The Universal Language 377 ]
(ei): Existential Instantiation lets us deduce from "some x(F(x))" that "F(v)" as long as "v" is a free variable.
[ ../maths/logic_25_Proofs.html#ei_explained ]
[ Rice.html ]
Ch 7, ch9 pp 390-390 -- Example 9.12
This section re-iterates that Rice's theorem shows the undecidability of
any problems where acceptance of a language for a particular TM is our
goal. But questions about the states of a Turing machine might be
decidable. Are any questions that involve a numeric component, like in
Example 9.12, decidable?
Yes. Example 9.12 (does this machine have 5 states?) is easy to decide.
It is like the question: does this C++ program "ttt.cpp" have 200 lines?
wc -l ttt.cpp
Contrast the above question with the question: Does ttt.cpp have any bugs?
"If a TM makes five moves, then it does so looking only at the nine cells of its tape surrounding its initial head position." Why nine?
Because that it can not move more than 5 steps in either direction from
the starting point. I figure 4 to the left + 4 to the right + the starting
cell.
Exercise 9.3.4 (c) -- Context free languages
Not part of this course.
Exercise 9.3.7 (b) and (c) -- Hint
The inputs have either 2 or 3 machines. If you choose one or two
of these cleverly then the resulting machine does something impossible.
Exercise 9.3.8 -- Not in this course