COMP0017
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture ten and eleven 1
Copyright By PowCoder代写 加微信 powcoder
Previously on COMP0017 We proved that:
1. the Halting Problem (HALT) is undecidable.
2. the Empty Tape Halting Problem (ETH) is
undecidable.
3. the complement of the Halting Problem (HALT -) is unrecognisable.
2 and 3 were proven as a consequence of 1. 2
This lecture
We introduce a simpler, more principled proof method for proving undecidability/unrecognisability of problems: mapping-reduction.
Towards mapping-reduction
In the mapping-reduction proof method the main insight is understanding how to reduce the instances of one problem to the instances of another problem.
For instance, the core of the proof that ETH was undecidable was how to turn a HALT-question into an ETH-question.
In a sense, this is all that matters. Decidability/ recognisability of the problems involved is not essential to the process, it is just our ultimate goal.
Towards mapping-reduction
Schematically, we want to define reduction more abstractly, in such a way that:
decidability of L’ reduces to decidability of L
L’ reduces to L
recognisability of L’ reduces to recognisability of L
So we take a more structured approach, were decidability/recognisability issues are shelved and we only focus on the relationship between problems.
This brings to a relation between problems called mapping-reducibility.
Mapping-reduction
Definition Given languages L and L’ over an alphabet Σ, we say that L’ mapping-reduces to L and write L’ ≤ L if there is a TM that computes a (total) function f : Σ* → Σ* such that
x∈L’ ↔ f(x)∈L
In essence, f converts the membership problem for L’
to the membership problem for L.
Intuitive reading of L’ ≤ L: L is at least as difficult as L’.
Reduction and decidability
Mapping-reducibility does not talk about decidability. However, it is a powerful tool in order to show that a language is (un)decidable.
Theorem 1 If L’ ≤ L and L is decidable, then L’ is
decidable.
Corollary 1 If L’ ≤ L and L’ is undecidable, then L is undecidable.
Thus, in order to prove L undecidable, we just need to show HALT ≤ L.
Corollary 2 If L is decidable and L’ is not, then L’ ≰ L. 7
Mapping-reduction in action
Halting problem on the empty tape
The empty tape halting (ETH) problem is defined by the following language.
ETH = { x ∈ Σ* | x = code(M) and M halts on 𝜀.} Theorem ETH is undecidable.
Proof outline It is enough to reduce HALT to ETH, because then the undecidability of HALT implies the one of ETH by Corollary 1.
Halting problem on the empty tape Proof We need to construct a computable f such that
If y ≠ code(M) for all M, then f(⟨y,x⟩) = y ∉ ETH.
If y = code(M), then f(⟨y,x⟩) = code(MM,x ), where MM,x is
constructed as follows:
1. MM,x enters a loop on any non-empty string.
2. On input 𝜀, write x on tape and simulate M on x.
f computable by a TM.
⟨y,x⟩ ∈ HALT ↔ f(⟨y,x⟩) ∈ ETH
The definition of f is as follows. On argument ⟨y,x⟩:
⟨y, x ⟩ ∈ y = code(M) and MM,x halts HALT M halts on x. on 𝜀.
f(⟨y,x⟩) = code(MM,x) and f(⟨y,x⟩) ∈ ETH
The “full language’’ problem
The “full language’’ problem (FL) is defined by the following language.
FL = { x ∈ Σ* | x = code(M) and M halts on all inputs.} Theorem FL is undecidable.
Proof outline We reduce HALT to FL.
The “full language’’ problem Proof We need to construct a computable f such that
⟨y,x⟩ ∈ HALT ↔ f(⟨y,x⟩) ∈ FL
The definition of f is as follows. On argument ⟨y,x⟩:
If y ≠ code(M) for all M, then f(⟨y,x⟩) = y ∉ FL.
• If y = code(M), then f(⟨y,x⟩) = code(MM,x ), where MM,x is
constructed as follows:
1. MM,x erases its input.
2. Write x on tape and simulate M on x.
⟨y, x ⟩ ∈ HALT
y = code(M) and M halts on x.
MM,x halts on an arbitrary
f(⟨y,x⟩) = code(MM,x ) and f(⟨y,x⟩) ∈ FL
The equivalence problem
The equivalence problem (EQ) for Turing machines is defined by the following language.
EQ = { ⟨y, x ⟩ ∈ Σ* x Σ* | x = code(M), y = code(Mʼ), and M and Mʼ compute the same partial function.}
Theorem EQ is undecidable. Proof outline We reduce FL to EQ.
Disclaimer: we could have used reduction from HALT rather than from FL. We just varied to show the flexibility of the approach.
The equivalence problem Proof We need to construct a computable f such that
z∈FL ↔ f(z)∈EQ
The definition of f is as follows. On argument z:
• If z ≠ code(M) for all M, then f(z) = ⟨z,z⟩ ∉ EQ.
If z = code(M), then f(z) = ⟨code(M1),code(M2)⟩, where • M1 runs M on its input and outputs 1 if M halts,
M1 and M2 are defined as follows.
and loops otherwise.
• M2 outputs 1 for all the inputs.
The equivalence problem
M1 runs M on its input and outputs 1 if M halts, and loops otherwise.
M2 outputs 1 for all the inputs.
M1 halts on all the f(z) = ⟨code(M1),code(M2)⟩ inputs with output 1. and f(z) ∈ EQ
z = code(M) and M M1 and M2 are halts on all the inputs. equivalent.
Reduction and recognisability
Reduction and recognisability
What it is true for reduction and decidability is also true for reduction and recognisability.
Theorem If L’ ≤ L and L is recognisable, then L’ is recognisable.
Corollary If L’ ≤ L and L’ is not recognisable, then L is not recognisable.
Corollary If L is recognisable and L’ is not, then L’ ≰ L. 17
The equivalence problem is unrecognisable Recall the equivalence problem (EQ) for TMs:
EQ = { ⟨y, x ⟩ ∈ Σ* x Σ* | x = code(M), y = code(Mʼ), and M and Mʼ compute the same partial function.}
We proved EQ to be undecidable. Now we show that EQ is even “harder’’: it is not recognisable.
Theorem EQ is not recognisable.
Proof outline We reduce HALT − (which we know is a
non-recognisable problem) to EQ. 18
The equivalence problem is unrecognisable Proof Recall the definition of HALT −:
HALT − = { ⟨y, x ⟩ ∈ Σ*x Σ* | y ≠ code(M) for any M or y = code(M) and M does
not halt on x.}
For the reduction, we have to come up with a function f
⟨y,x⟩ ∈ HALT − ↔ f(⟨y,x⟩) ∈ EQ which is the same as saying
⟨y,x⟩ ∈ HALT ↔ f(⟨y,x⟩) ∈ EQ −
so we seek the latter equivalence. 19
The equivalence problem is unrecognisable Proof On ⟨y,x⟩ define f as follows:
If y ≠ code(M) for all M, then we pick any Mʼ and let f(⟨y,x⟩) = ⟨code(M’), code(Mʼ)⟩. So f(⟨y,x⟩) ∈ EQ
and thus f(⟨y,x⟩) ∉ EQ −.
Otherwise y = code(M) and we let f(⟨y,x⟩) =
⟨code(M1),code(M2)⟩, where M1 and M2 are defined as
M1 runs M on x and halts if M halts, and loops
otherwise.
M2 loops on any input.
The equivalence problem is unrecognisable
M1 on all the inputs runs M on x and halts if M halts, and loops otherwise.
M2 loops on all the inputs.
In fact, the language of strings accepted by M1 is either
Σ* or ∅, depending on whether M halts on x.
⟨y,x⟩∈ HALT
M1 accepts some string.
f(⟨y,x⟩) = ⟨code(M1),code(M2)⟩
y = code(M) and M halts on x.
M1 and M2 are not equivalent.
and f(⟨y,x⟩) ∈ EQ −
Further properties of mapping-reduction
Reduction and decidability
We saw that knowing L decidable or L’ undecidable is useful.
Theorem 1 If L’ ≤ L and L is decidable, then L’ is decidable. Corollary 1 If L’ ≤ L and L’ is undecidable, then L is
undecidable.
Corollary 2 If L is decidable and L’ is not, then L’ ≰ L.
However, if L’ is decidable, reduction to some L is of little use.
Theorem 2 If L is any non-trivial language (so L ≠ Σ* and L ≠ ∅) then L’ ≤ L for any L’ decidable.
Reduction and decidability Theorem 2 If L is any non-trivial language (so L ≠ Σ*
and L ≠ ∅) then L’ ≤ L for any L’ decidable. Proof
As L is non-trivial we can pick x ∈ L and y ∉ L. Define the function f : Σ* → Σ* as follows:
f(z) = x if z ∈ L’
f(z) = y otherwise, i.e. if z ∉ L’
As L’ is decidable, f can be implemented by a TM which
internally simulates the TM for L’ and outputs x or y
accordingly. Moreover, z ∈ L’ ↔ f(z) ∈ L by definition of f. 24
Reduction as a relation Reduction is a relation between languages.
It is reflexive: for all L, L ≤ L.
It is transitive: L’ ≤ L and L ≤ L’’ implies L’ ≤ L’’.
However, it is not symmetric. Symmetry means that L’ ≤ L implies L ≤ L’.
The halting problem is the counterexample to symmetry. By Theorem 2, for any decidable L’, L’ ≤ HALT. If also HALT ≤ L’, then HALT would be decidable by Theorem 1, contradiction.
Therefore, reduction is not an equivalence relation.
Reduction and complement Theorem L1 ≤ L2 if and only if L1− ≤ L2−
Corollary L1− ≤ L2 if and only if L1 ≤ L2−
the last proof with L1 = HALT
Putting all together, we have “for free’’ a proof that EQ− is not recognisable.
Indeed, HALT ≤ FL ≤ EQ, thus HALT − ≤ EQ − by the
theorem. In this situation, non-recognisability of HALT −
implies non-recognisability of EQ −. 26
Implicitly used in and L2 = EQ.
A hierarchy of problems
Undecidable, but recognisable
Not recognisable, but complement recognisable Not recognisable, and complement not
recognisable
We proved all relations but one: HALT ≰ HALT −
(exercise!)
Decidable languages
Other notions or reducibility
Turing-reducibility
Mapping-reducibility is just one way of defining the concept of a problem being reducible to another one.
Another one is what is usually called Turing- reducibility.
An oracle for a language L is an external device (a “black box’’) that is capable of answering the question “x ∈ L ?’’ for all strings x.
A language L’ is Turing-reducible to L if we can
decide L’ given an oracle for L. 29
Comparing notions of reducibility
Mapping-reducibility implies Turing-reducibility but not vice-versa.
Example: we know HALT − ≰ HALT, i.e., HALT − is not mapping reducible to HALT.
But HALT − is Turing-reducible to HALT. Indeed, if we have an Oracle for the question “⟨y, x ⟩ ∈ HALT ?’’, then this obviously can be used to decide whether ⟨y, x ⟩ ∈ HALT −.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com