[PDF] Lecture Notes: The Halting Problem; Reductions

View - Download Lecture Notes: The Halting Problem; Reductions

Previous PDF

Next PDF

Lecture Notes:

The Halting Problem; Reductions

COMS W3261

Columbia University

20 Mar 2012

1 Review

Key point.Turing machines can be encoded as strings, and other Turing machines can read those strings to peform \simulations".

Recall two denitions from last class:

Denition 1.A language isTuring-recognizableif there exists a Turing machine which halts in an accepting state i its input is in the language. Denition 2.A language isTuring-decidableif it halits in an accepting state for every input in the language, and halts in a rejecting state for every other input. Intuitively, for recognizability we allow our TM to run forever on inputs that are not in the language, while for decidability we require that the TM halt on every input.

Now recall our two most important results:

Theorem 1.There exist (uncountably many!) languages which are not Turing-recognizable. Proof.(intuitive) There are as many strings as natural numbers, because every (nite) string over a nite alphabet can be encoded as a binary number. There are as many TMs as strings, because every TM can be encoded as a string. Thus, both the strings and the TMs are countably innite. There are as many languages as real numbers. Every language is a subset of the set of strings; we can think of this subset as being encoded by an innite binary sequence (i.e. a real number) with 1s at indices corresponding to strings in the language and 0s everywhere else. Thus there are more languages than Turing machines; we conclude that some (indeed, \most") languages are not recognized by any TM.Now we will construct a specic undecidable language. 1 Denition 3.The languageXTM=fhMi:Mdoes not accepthMig

Theorem 2.XTMis not Turing-decidable.

Question.Give the \paradox" proof.

Proof 1.(by Epimenides' paradox) Suppose we had a Turing machineMdeciding this lan- guage. What happens when we runMwith inputhMi? If we claim it accepts, then by denition it ought to reject; if it rejects, then it ought to accept! Either way, we have a contradiction.Alternatively, here's a proof that it's not even Turing-recognizable.

Question.Give the \diagonalization" proof.

Proof 2.(by diagonalization) Suppose we constructed an (innite) chart listing all the Turing machines and all encodings of Turing machines. We write 1 in cell [i;j] ifMiacceptshMji and 0 otherwise:hM1i hM2i hM3i M

10 1 1

M

21 1 1

M

31 0 1

(The particular arrangement of 1s and 0s is unimportant|it will depend on our encoding scheme.) Note that by reading the 1s from theith row, we get the language decided by M i. DoesXTMappear in any row of this list? Not the rst row:M1rejectshM1i, sohM1i must be inXTM. Not the second row:M2acceptshM2i, sohM2imust not be inXTM. Continuing with this procedure, we can show thatXTMis not the same as any row of this enumeration of TMs, and as a consequence is not decided by any TM.2 The Accepting Problem X TMis admittedly a rather strange language, and it's not obvious why we should really care that it's not recognizable. Let's look at a dierent one:

Denition 4.The languageATM= (fhMi;w) :Macceptswg

The question of whetherATMis decidable is precisely the question of whether one TM can predict the output of another TM!

Question.Is this language Turing-recognizable?

Yes. GivenhMi;was input, we can just simulateMonw.

Question.Is this language Turing-decidable?

2 No.

Theorem 3.ATMis undecidable.

Proof.Suppose, towards contradiction, that we had a TMMdecidingATM. Then we could construct a TMNdecidingXTM, as follows:

Given inputhPi:

RunMonhP;Pi.

IfMaccepts, reject.

IfMrejects, accept.

Clearly,Nis a TM decidingXTM. But we know that there no such TM exists! Because the

existence ofMimplies the existence ofN, we conclude thatMalso does not exist.Clarication.Understand whyATMis recognizable but not decidable.

Key point.There is no Turing machine which can predict the output of all other Turing machines. However, there are Turing machines which can predict the output ofsomeother

Turing machines.

3 The Halting Problem

Let's try a more modest goal: rather than actually attempting to predict output, let's just predict whether a Turing machinehaltson its input, or runs forever. Denition 5.The languageHALTTM=f(hMi;w) :Mhalts on inputwg

Question.Is this language Turing-recognizable?

Yes: again, it just simulates (but it will run forever if the simulated machine does!).

Question.Is this language Turing-decidable?

No.

Theorem 4.HALTTMis undecidable.

Proof.This is very much like the previous proof. Suppose we had a TMMdeciding HALT TM. The we could construct a TMNdecidingATM, as follows:

Given input (hPi;w):

RunMon (hPi;w).

IfMrejects, reject:Pruns forever given inputw, so does not acceptw. 3 Otherwise, we know thatPterminates, and it is \safe" to simulate it onw. Do so.

IfPaccepts, accept.

IfPrejects, reject.

Clearly,NdecidesATM. Similarly to the previous proof, we know thatATMis undecidable, soMcannot exist.Key point.There is no Turing machine which nds innite loops in all other Turing ma- chines (though again, it may do so for a restricted subset). This is a problem which would have real, practical benets if it were soluble, but it's not.

Clarication.Is this clear?

4 Other Undecidable Languages

Denition 6.The languageETM=fhMi:L(M) =;g

Question.Is this language decidable?

No: we can construct a decider forATMagain.

Proof.SupposeMdecidesETM.

Given inputhP;wi:

Construct a new TMP0which rejects if its input is notw, and otherwise simulatesP onw.

RunMonhPi.

IfMaccepts, reject.

IfMrejects, accept.

We have a contradiction.5 Reductions

In working through these examples we've come across a very powerful proof technique: to prove that some language is undecidable, we assume that we have a decider, and show that this implies the existence of a decider for a known undecidable problem. This technique is calledreduction. There are several dierent kinds of reduction; the kind that we've discussed so far is calledTuring reduction(for reasons that are hopefully obvious). The general idea is that 4 we assume we have a TM which computes the solution to one problem, and we use that to compute the solution to another problem. To say that a solver forBallows us to solveA(\Areduces toB"), we write ATB (I've always found this notation weird. An easy way to remember it is that ifAis reducible toB, the machine that computesBis at least as powerful as the machine that computes A: it is denitely powerful enough to solveA, and maybe other problems as well. SoAis \easier than"B.)

Question.ATMTXTM, or vice-versa?

Vice-versa.

Let's formalize the proof technique we've been using so far:

Theorem 5.ATBandBdecidable!Adecidable.

Corollary 1.ATBandAundecidable!Bundecidable.

6 Other Undecidable Languages, continued

Now let's try a few more reductions:

Denition 7.The languageREGTM=fhMi:L(M)is regularg

Question.Prove that this is undecidable. (Hint: reduce fromATM)

Proof.Suppose we have a deciderMforREGTM.

Given inputhP;wi:

Construct a new TMP0as follows:

{If the input is of the form 0n1n, accept. {Otherwise, ignore the input and runPonw

RunMonP0

IfMdoesn't acceptw,L(P0) =f0n1ng, and is not regular. IfMacceptsw,L(P0) = . Thus,

IfMaccepts, accept.

IfMrejects, reject.

Once again, a contradiction.5

Denition 8.The languageEQTM=f(hMi;hNi) :L(M) =L(N)g Question.Prove that this is undecidable. (Hint: reduce fromETM) Proof.Suppose we have a deciderMforEQTM. Construct the following decider forETM:

Given inputhPi:

Construct a TMQwhich rejects immediately on all inputs.

RunMon (hPi;hQi), and accept i it accepts.

Once again, a contradiction.7 Next Class

It seems like every interesting language of Turing machines we've come up with is undecid- able. Is there any property of Turing machines which can be decided? 6quotesdbs_dbs17.pdfusesText_23

[PDF] halton till

[PDF] ham cooking temperature chart

[PDF] ham cooking time calculator

[PDF] ham radio codes 10 codes

[PDF] ham radio programming software for mac

[PDF] ham roasting times

[PDF] hamiltonian of coupled harmonic oscillators

[PDF] hamiltonian path

[PDF] hamiltonian path and circuit

[PDF] hamlet act 1

[PDF] hamlet act 2

[PDF] hamlet passage

[PDF] hamlet pdf with footnotes

[PDF] hamlet website

[PDF] hamlet with explanatory notes