COMP0017
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture twelve 1
Copyright By PowCoder代写 加微信 powcoder
Previously on COMP0017
We commenced our investigation of unsolvable problems.
We saw various techniques, like mapping- reducibility, for proving that a problem is unsolvable (undecidable or unrecognisable).
In this lecture
We continue our investigation of unsolvable problems, focussing on general results that tell us something about the nature of solvability.
We prove that all the problems decidable by a Turing machine are in a sense trivial (Rice’s Theorem).
We prove that there are many more un-recognisable problems than recognisable ones
(Cantor’s diagonal argument). 3
Rice’s Theorem
Seeking positive results
We saw that we can’t decide whether a given Turing machine
halts on a given input
halts on empty input (the empty string)
halts on any input
is equivalent to another given Turing machine.
What problems about Turing machines we can decide then?
Seeking positive results
For instance, we can decide whether a given Turing machine
always halts within a certain number of steps. has less than a certain number of states.
How much else can we get?
Remainder: languages
Languages are just subsets of Σ*. Let’s fix Σ = {0,1}, which can be done without loss of generality modulo a suitable encoding of Σ* into {0,1}*.
The language of a Turing machine M is LM = {x ∈ {0,1}* | M accepts x}.
Properties of TM’s languages A TM language property P is a function from the set of
Turing machines to {0,1} (false/true), such that LM = LM’
implies P(M) = P(M’).
Such a property is nontrivial if there exists a TM M such
that P(M) = 1 and a TM M’ such that P(M’) = 0.
Formally, we will identify the TMs satisfying property P with the set { y ∈ Σ* | y = code(M) and P(M) = 1}.
This is just to
ensure that P depends only on the language the machine describes.
Example: “halts in 42 steps’’ is not a language property.
{ y | y = code(M) and LM is finite}
{ y | y = code(M) and LM is empty} { y | y = code(M) and LM = L}
These are non-trivial language properties. Some machines have them, some others don’t.
{y | y = code(M) and M recognises some language} This is a trivial language property. Every TM
recognises a language by definition. 9
Rice’s Theorem
Theorem If P is a nontrivial language property, then the
problem “Does M have property P’’ is undecidable. Proof strategy By contradiction. We are going to show
that if “Does M have property P’’ was decidable, then the halting problem would be decidable.
Rice’s Theorem
A TM whose recognised language is empty.
Fix a property P. We first suppose that P(M∅) = 0. As P is non-trivial, we can pick MP with P(MP) = 1. Fix M and x as parameters. We construct the following TM MM,x :
Simulate M on x.
Simulate MP on z.
If M halts.
If MP halts.
Otherwise.
Otherwise.
⇒LM=LM ⇒ P M,x
so MM,x has property P.
Rice’s Theorem
P(MM,x) = P(MP),
Conclusion: if we could decide if MM,x has the property
P, we could decide the halting problem.
Therefore, {y | y = code(M) and P(M) = 1} is undecidable.
P(MM,x) = P(M∅), so MM,x does not have
property P.
M halts on x.
MM,x halts on z whenever MP
M does not halt on x.
halts on z.
never halts on z.
Rice’s Theorem
We assumed P(M∅) = 0. What if P(M∅) = 1? If so, repeat the very same argument, but this time for
the property ¬P (“M has not property P‘’).
Notice that repeating the argument works because:
as P is non-trivial, ¬P is non-trivial too. as P(M∅) = 1, then ¬P(M∅) = 0.
Thus we are able to get to the conclusion that {y | y =
code(M) and ¬P(M) = 1} is undecidable. This implies
that also {y | y = code(M) and P(M) = 1} is undecidable. 13
Disclaimer: decidable properties
Beware of this common misconception with Rice’s Theorem.
Rice’s Theorem speaks about language properties, not machine properties. It’s about functions (specifications), not programs (implementations).
For instance, we cannot use Rice’s Theorem to derive the undecidability of the halting problem (and related ones). The associated properties would refer to machines rather than languages.
Disclaimer: decidable properties
Loosely speaking, there are three kinds of properties that one may consider about Turing machines.
Language properties. Non-trivial ones are
• Structural properties, like “M has 13 states’’. These
undecidable by Rice’s theorem.
are typically decidable, since they can be checked statically on the given description of a Turing machine in encoded form.
• Behavioural properties, like “M never moves left on input 0101’’ or “M halts on code(M)’’. Some of these
are decidable, some others aren’t, and the
classification is not obvious. 15
The cardinality of unsolvable problems
We want to prove that most languages are not recognisable (and, consequently, undecidable).
Ours is a size argument: there are many more languages than there are Turing machines.
In order to make this precise, we introduce an elegant proof method that turns out to be useful also in other settings: Cantor’s diagonalisation argument.
Countably infinite sets
A set S is countably infinite if there is a total bijective
function f: N→S.
Idea: a countably infinite set has as many elements as
there are natural numbers.
Example: the set of odd natural numbers, with the
function f(n) = 2n ⨪ 1.
S1 and S2 are countably infinite, S1 ∪S2 is countably infinite.
Countably infinite sets Example: the set Σ* of strings over a finite alphabet Σ.
Assuming |Σ| = n, the bijection with N is constructed as:
For instance, for Σ = {a,b}:
Counting Turing machines
We have already seen that any TM can be encoded as a string for an alphabet Σ with |Σ| = 2 (e.g., Σ = {0,1}).
Therefore, the set of all Turing machines is countably infinite.
Also, the set of all recognisable languages is countably infinite. This is because any language is by definition recognisable if there is a TM recognising it.
Moreover, for the same reason, the set of functions N→N computable by a Turing machine is countably infinite.
Uncountable sets
Recap: countably infinite sets (including the set of TMs) are those that have as many elements as the natural numbers (they can be “counted”).
However, (1845-1918) taught us that there are infinite sets that are uncountable. They have “more” elements than the natural numbers.
He introduced a technique (called diagonalisation) to show that a set is uncountable. He used it to show that the real numbers are uncountable.
Languages are uncountable Call SΣ the set of all languages over a finite alphabet Σ.
Theorem The set SΣ is not countable.
Proof Recall that a language L is a subset of Σ*. We have already seen that Σ* is countably infinite, so we can write it as Σ* = {𝜎1, 𝜎2, 𝜎3, …}.
Then a language, say L1 = {𝜎1, 𝜎4}, can be represented by
Languages are uncountable
Any language over Σ can be represented in this way.
Towards a contradiction, suppose now that SΣ is a countable set. If so, we can assign natural numbers to its elements, so that any Li ∈SΣ appears
as one of the rows on the right.
Languages are uncountable So, is it really any element L of SΣ on some row?
No! Look at the diagonal.
Languages are uncountable So, is it really any element L of SΣ on some row?
Define L as 00110…, so that 𝜎i ∈ L if and only if 𝜎i ∉ Li.
Then L is different from any language Li on a row.
So L itself cannot be on a row! Contradiction.
Therefore, SΣ is not countable.
For a finite alphabet Σ, we have seen that
the set of languages recognisable by a Turing the set of all languages is uncountable.
We have seen a few already: HALT −, EQ, EQ −
Therefore, there exist languages that are not recognisable by any Turing machine.
Further question: how many un-recognisable languages are there?
machine is countably infinite.
How many unrecognisable sets? Our answer will stem from a more general result.
Theorem If S is an infinite set that is not countable and S’ is a countably infinite subset of S, then S \ S’ is not countably infinite.
Proof Suppose that S \ S’ is countably infinite. Then, because countably infinite languages are closed under union (see previous Lemma), (S \ S’ ) ∪ S’ = S
is countable. Contradiction!
Corollary The set of un-recognisable languages is not countably infinite — so there are more un-recognisable than recognisable languages.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com