[PDF] [PDF] Lecture Notes: The Halting Problem; Reductions - Computer

[PDF] Lecture Notes: The Halting Problem; Reductions - Computer

20 mar 2012 · The Halting Problem; Reductions COMS W3261 Columbia halts in an accepting state iff its input is in the language Definition 2 A language 

[PDF] 1 Reductions

Reductions A reduction is a way of converting one problem into another problem such that a solution to the second problem can be used to solve the first problem Proof We will reduce Atm to HALT Mapping Reductions On input w The Halting Problem On input x then accept x = {〈M1,M2〉 L(M1) = L(M2)} is not r e

[PDF] co-RE and Reducibility

Mapping Reductions ○ A tool The halting problem is the following problem: Given a Proof: By contradiction; assume HALT ∈ R Then there must be some

[PDF] Theory of Computer Science - Halting Problem and Reductions

10 mai 2017 · undecidability results from the undecidability of the special halting problem a new problem to an already known problem x ∈ A if and only if f (x) ∈ B Then we say that A can be reduced to B (in symbols: A ≤ B), and f is called reduction from A to B

[PDF] BBM402-Lecture 9: Reducibility

The Halting Problem Proposition The language HALT = {〈M,w〉 M halts on input w} is undecidable Proof We will reduce Atm to HALT Based on a machine  

[PDF] Reductions

The Halting problem HALTTM = {M,w M is a DTM and M halts on w} The reduction machine outputs a DTM that loops whenever M reaches the rejecting state

[PDF] 11 Reductions We mentioned above the idea of solving problems by

Question: Show, by reduction from Halting, that the Uniform Halting problem is unde- cidable Answer: It is a theorem that if Q can be reduced by a many–one ( or 

[PDF] Reducibility The Halting Problem for TMs - Computer Science Kent

ML that such TMaisM M E w string input on halts that TMaisM wM HALT TM A reduction is a way of converting one problem into another problem in such a

[PDF] Other undecidable problems Examples of undecidable problems

Languages and Automata Undecidability, problem reduction, and Rice's Theorem (12 2) Other undecidable problems • Once we have shown that the halting

[PDF] Chapter 7 Uncomputability

The problem of deciding if a Turing machine stops for at least one input word (the existential halting problem) is undecidable One proceeds by reduction from the 

[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

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