[PDF] [PDF] Chapter 7 Uncomputability

[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

Chapter 7

Uncomputability

190

7.1 Introduction

Undecidability of concrete problems.

First undecidable problem obtained by diagonalisation. Other undecidable problems obtained by means of the reduction technique. Properties of languages accepted by Turing machines. 191

7.2 Proving undecidability

Undecidability classes

Correspondence between a problem and the language of the encodings of its positive instances.

Denition

The decidability class R is the set of languages that can be decided by a

Turing machine.

The class R is the class of languages (problems) that are decided by a Turing machine, recursive, decidable, computable, algorithmically solvable. 192

Denition

The decidability class RE is the set of languages that can be accepted by a Turing machine. The class RE is the class of languages (problems) that are accepted by a Turing machine, partially recursive, partially decidable, partially computable, partially algorithmically solvable, recursively enumerable. Lemma

The class R is contained in the class RE (RRE)

193

A rst undecidable language

Aw

0w1w2. . .wj. . .M

0Y N N . . . Y . . .

M

1N N Y . . . Y . . .

M

2Y Y N . . . N . . .

M iN N Y . . . N . . . A[Mi;wj] = Y (yes) if the Turing machineMiaccepts the wordwj; A[Mi;wj] = N (no) if the Turing machineMidoes not accept the word w j(loops or rejects the word). L

0=fwjw=wi^A[Mi;wi] = Ng:

is not in the class RE. 194

A second undecidable language

Lemma The complement of a language in the class R is also in the class R. Lemma If a languageLand its complementLare both in the class RE, then both

LandLare in R.

Three situations are thus possible:

1.LandL2R,

2.L62RE andL62RE,

3.L62RE andL2RE\R.

195
Lemma

The language

L

0=fwjw=wi^Miacceptswig

is in the class RE.

Theorem

The languageL0is undecidable (is not in R), but is in RE. REL 0R L 0196

The reduction technique

1. One p rovesthat, if there exists an algo rithmthat decides the language L

2, then there exists an algorithm that decides the languageL1. This

is done by providing an algorithm (formally a Turing machine that stops on all inputs) that decides the languageL1, using as a sub-program an algorithm that decidesL2. This type of algorithm is called areductionfromL1toL2. Indeed, it reduces the decidability of L

1to that ofL2.

2. If L1is undecidable, one can conclude thatL2is also undecidable (L262R). Indeed, the reduction fromL1toL2establishes that ifL2 was decidable,L1would also be decidable, which contradicts the hypothesis thatL1is an undecidable language. 197

Theuniversal languageUL

UL =f< M;w >jMacceptswg

is undecidable. Reduction fromL0: to check if a wordwis inL0, proceed as follows. 1.

Find the value isuch thatw=wi.

2.

Find the T uringmachine Mi.

3. Apply the dec isionp rocedurefo rUL to the wp rd< Mi;wi>: if the result is positive,wis accepted, if not it is rejected.

Note : UL62RE

198

More undecidable problems

The halting problem

H =f< M;w >jMstops onwg

is undecidable. Reduction from UL. 1.

Apply the algo rithmdeciding H to < M;w >.

2. If the algo rithmdeciding H gives the answ er\no" ( i.e.the machineM does not stop), answer \no" (in this case, we have indeed that < M;w >62UL). 3. If the algo rithmdeciding H gives the answ er\y es,simulate the execution ofMonwand give the answer that is obtained (in this case, the execution ofMonwterminates and one always obtains an answer). 199
The problem of determining if a program written in a commonly used programming language (for example C or, Java) stops for given input values is undecidable. This is proved by reduction from the halting problem for Turing machines. 1. Build a C p rogramPthat, given a Turing machineMand a wordw, simulates the behaviour ofMonw. 2. Decide if the p rogramPstops for the input< M;w >and use the result as answer. 200
The problem of deciding if a Turing machine stops when its input word is the empty word (the empty-word halting problem) is undecidable. This is proved by reduction from the halting problem. 1. F oran instance < M;w >of the halting problem, one builds a Turing machineM0that has the following behaviour: it writes the wordwon its input tape; it then behaves exactly asM. 2. One solves the empt y-wordhal tingp roblemfo rM0and uses the result as answer. 201
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 empty-word halting problem. 1. F oran instance Mof the empty-word halting problem, one builds a

Turing machineM0that behaves as follows:

it erases the content of its input tape; it then behaves asM. 2. One solve the existential halti ngp roblemfo rM0and uses the result as answer. 202
The problem of deciding if a Turing machine stops for every input word (the universal halting problem) is undecidable. The reduction proceeds from the empty-word halting problem and is identical to the one used for the existential halting problem. The only dierence is that one solves the universal halting problem forM0, rather than the existential halting problem. 203
Determining if the language accepted by a Turing machine is empty (empty accepted language) is undecidable. Reduction from UL. 1. F oran instance < M;w >of UL, one builds a Turing machineM0that simulates the execution ofMonwignoring its own input word; ifMacceptsw, it accepts is input word, whatever it is. ifMdoes not acceptw(rejects or has an innite execution) it does not accept any word. 2. One solves the empt yaccepted language p roblemfo rM0and uses the result as answer. 204

This reduction is correct given that

L(M0) =;exactly whenMdoes not acceptw, i.e., when

< M;w >2UL; L(M0) = 6=;exactly whenMacceptsw, i.e. when< M;w >62UL. 205
Determining if the language accepted by a Turing machine is recursive (recursive accepted language) is undecidable. Reduction from UL. 1. F oran instance < M;w >of UL, one builds a Turing machineM0that simulates the execution ofMonwignoring its own input word; ifMacceptsw, it behaves on its own input word as a universal turing machine. ifMdoes not acceptw(rejects or has an innite execution) it does not accept any word. 2. One solves the recursive accepted language problemforM0and uses the result as answer. 206

This reduction is correct since

L(M0) =;and is recursive exactly whenMdoes not acceptw, i. e. when< M;w >2UL; L(M0) = UL and is not recursive exactly whenMacceptsw, i.e. when < M;w >62UL. 207
Determining if the language accepted by a Turing machine is not recursive (undecidable) (undecidable accepted language) is undecidable. Reduction from UL. 1. F oran instance < M;w >of UL, one builds a Turing machineM0that simulates the execution ofMonw, without looking at its own input wordx; simultaneously (i.e. interleaving the executions), the machineM0 simulates the universal Turing machine on its own input wordx; As soon as one of the executions accepts, (i.e., ifMacceptswor if the input word is inUL),M0accepts. 208

2.If neither of the t woexecutions accepts (i.e., if Mdoes not acceptw,

or if the input wordx62UL),M0does not accept. 3. One solves the undecidable acce ptedlanguage p roblemfo rM0and uses the result as answer. 209

This reduction is correct since

L(M0) = UL and is undecidable exactly whenMdoes not acceptw, i.e., when< M;w >2UL; L(M0) = and is decidable exactly whenMacceptsw, i.e. when < M;w >62UL. 210
In the preceding reductions, the language accepted by the machineM0is either UL, or;, or . These proofs can thus also be used to establish that the problem of determining if the language accepted by a Turing machine is regular (or non regular) is undecidable. Indeed,;and are regular languages, whereas UL is not a regular language. 211

7.4 Properties of

recursively enumerable languages

The recursively enumerable languages are :

The languages computed by a Turing machine,

the languages generated by a grammar, The languages that can be enumerated by an eective procedure (which explains why they are called \recursively enumerable"). 212

The languages computed by a Turing machine

Denition

LetMbe a Turing machine.IfMstops on an input wordu, letfM(u) be the word computed byMforu. The language computed byMis then the set of words fwj 9usuch thatMstops foruandw=fM(u)g:

Theorem

A language is computed by a Turing machine if and only if it is recursively enumerable (accepted by a Turing machine). 213
LetLbe a language accepted by a Turing machineM. The Turing machineM0described below computes this language. 1. The machine M0rst memorises its input word (one can assume that it uses a second tape for doing this). 2.

Thereafter, it b ehavesexactly as M.

3. If Maccepts,M0copies the memorised input word onto its tape. 4.

If Mdoes not accept,M0keeps running forever.

214
LetLbe a language computed by a Turing machineM. The nondeterministic Turing machine described below accepts this language. 1.

The machine M0rst memorises its input wordw.

2. Thereafter, it gene ratesnondeterministically a w ordu. 3. The machine M0then simulates the behaviour ofMonu. 4. If Mstops onu,M0compareswtofM(u) and acceptswifw=fM(u). 5.

If Mdoes not stop onu,M0does not acceptw.

215

The languages generated by a grammar

Theprem

A language is generated by a grammar if and only if it is recursively enumerable. LetG= (V;;R;S), The Turing machineMdescribed below accepts the language generated byG. 1. The machine Mstarts by memorising its input word (we can assume it uses a second tape to do so). 2. Then, it erases its tap eand writes on it the sta rtsymb olSof the grammar. 216

3.The follo wingcycle is then rep eated:

(a) nondeterministically ,the machine cho osesa rule Rand a string appearing on its tape; (b) if the selec tedstring is identical to the left-hand side of the rule, it is replaced by the right-hand side; (c) the content of the tap eis compa redto the memo risedinput w ord, and if they are identical the machine accepts; if not it carries on with its execution. 217
LetM= (Q;;;;s;B;F) be a Turing machine. One builds a grammar G

0= (VG0;G0;RG0;SG0)

such thatSG0)wwithw2(Q[)if and only ifwdescribes a conguration (q;1;2) ofMwritten as1q2.

The grammarG0is dened by

VG0=Q[[ fSG0;A1;A2g,

G0= ,

RG0is the set of rules below.

218

1.Initial conguration of M:

S

G0!sA1

A

1!aA18a2

A 1!A2

A2!BA2

A2!": 2.

T ransitions.F orall p;q2QandX;Y2 such that

(q;X) = (p;Y;R) we include the rule qX!Y p:

Similarly, for allp;q2QandX;Y;Z2 such that

(q;X) = (p;Y;L) we include the rule

ZqX!pZY:

219

Problem: the input word is lost.

Solution: simulate a Turing machine with two tapes. G

1= (VG1;G1;RG1;SG1) where

VG1= [Q[(([ feg))[ fSG1;A1;A2g(we represent an element of (([ feg)) by a pair [a;X]), G1= ,

RG1is the set of rules described below.

220

1.Initial conguration of M:

S

G1!sA1

A

1![a;a]A18a2

A 1!A2

A2![e;B]A2

A2!": 2. T ransitions.F orall p;q2Q,X;Y2 anda2[ fegsuch that (q;X) = (p;Y;R) we include the rule q[a;X]![a;Y]p: Similarly, for allp;q2Q,X;Y;Z2 anda;b2[ fegsuch that (q;X) = (p;Y;L) we include the rule [b;Z]q[a;X]!p[b;Z][a;Y]: 221

3.F oral lq2F,X2 anda2[ feg, we include the rules

q[a;X]!qaq [a;X]q!qaq ifa6=eand q[a;X]!q [a;X]q!q ifa=e. These rules propagate a copy ofqnext to each nonterminal [a;X] and extract its rst component. Finally, we add q!" that allows the copies of the stateqto be removed. 222

The languages enumerated by an eective procedure

Turing machine that enumerates the words accepted byM. Generate all words in lexicographical and increasing length order, simulateMon each newly generated word and keep this word only if it is accepted byM. Incorrect: the Turing machine can have innite executions.

Solution: other enumeration order.

223
wnn1 2 3 4 w

1(w1;1)!(w1;2) (w1;3)!(w1;4). % .

w

2(w2;1) (w2;2) (w2;3)# % .

w

3(w3;1) (w3;2) (w3;3).

w

4(w4;1)#

One considers the pairs (w;n) in the order of their enumeration. For each of these pairs, one simulates the execution ofMonw, but limits the execution tonsteps. On produces the wordwif this execution acceptsw.

On then moves to the next pair (w;n).

224

7.5 Other undecidable problems

The problem of determining if a wordwis in the language generated by a grammarGis undecidable. Reduction from the problem UL. Let< M;w >be an instance of the problem UL. It can be solved as follows: 1. one builds the gramma rGgenerating the language accepted byM 2. one determines if w2L(G) and uses the result as answer. 225
The problem of deciding if two grammarsG1andG2generate the same language is undecidable. Reduction from the membership problem for the language generated by a grammar. An instance< w;G >of this problem can be solved as follows: 1.

Let G= (V;;R;S). One builds the grammarsG1=Gand

G

2= (V;;R0;S0), with

R

0=R[ fS0!S;S0!wg:

2. One checks if L(G1) =L(G2) and uses the result as answer. One has indeed thatL(G2) =L(G1)[ fwgand thus thatL(G2) =L(G1) if and only ifw2L(G). 226
The problem of determiningvalidity in the predicate calculusis undecidable The problem of determining theuniversality of a context-free language, i.e., the problem of determining if for a context-free grammarGone has

L(G) = is undecidable.

227
The problem of determining theemptiness of the intersection of context-free languagesis undecidable. The problem is to determine if, for two context-free grammarsG1andG2, one hasL(G1)\L(G2) =;. Hilbert's tenth problemis undecidable. This problem is to determine if an equation p(x1;:::;xn) = 0 wherep(x1;:::;xn) is an integer coecient polynomial, has an integer solution. 228

Noncomputable functions

A total function

f: 1!2 is computable if and only if the following questions are decidable. 1.

Given n2Nandw21, do we have thatjf(w)j> n?

2. Given k2N,w21anda22, do we have thatf(w)k=a? (is the k thletter off(w)a?). 229
quotesdbs_dbs21.pdfusesText_27