[PDF] [PDF] 1 Reductions

[PDF] co-RE and Reducibility

The halting problem is the following problem: Given a TM M and string w, does M halt on w? ○ Note that M doesn' 

[PDF] Unsolvable Problems - Stanford University

Some Turing machines always halt; they never go into an infinite loop ○ If M is a TM and M halts on every possible input, then we say that M is a decider

[PDF] Chapter 5 - CS 341: Foundations of CS II Marvin K Nakayama

Halting Problem for TMs is Undecidable • Recall that ATM HALTTM = { 〈M, w 〉 M is a TM and M halts on string w } Does a TM halt on all inputs? • Does a  

[PDF] COMP481 Review Problems Turing Machines and - Computer

The complement of the Halting Problem, denoted by HP, and defined as HP = { 〈M,w〉M is a TM and it does not halt on string w} 2 I use “decidable” and 

[PDF] Harvard CS 121 and CSCI E-121 Lecture 16: Turings Theorem

29 oct 2013 · The Halting Problem: Given M and w, does M halt on input w? Proof: Suppose HALTTM = {(M,w) : M halts on w} were decided by some TM H

[PDF] Computability: Turing Machines and the Halting - Arizona Math

9 juil 2008 · a TM and x is the input, run M on input x, and accept if it accepts or Turing machine M may not halt), a co-recognizable language has a Turing 

[PDF] 1 Reductions

Will give reduction f to show Atm ≤m HALT =⇒ HALT undecidable Let f(〈M,w 〉) = 〈N,w〉 where N is a TM that behaves as follows: On input x Run M on x

[PDF] Lecture 9

TM is undecidable We also saw the original halting problem (of Shoshana and Uri :-), and it was shown (on board) this language is also undecidable H TM

[PDF] Encoding of TMs Universal Turing Machines The Halting

Halting Problem: Does a Turing machine halt on an input string? H TM = {(M,w) M is a TM and M halts on input w 

[PDF] accepts - CS5371 Theory of Computation

Halting Problem Theorem: HALT TM is undecidable •Recall that A TM is the language { 〈M, w〉 M is a TM that accepts w} and we have shown that A TM

[PDF] halting problem proof

[PDF] halting problem reduction

[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

1 Reductions

1.1 Introduction

Reductions

Areductionis a way of converting one problem into another problem such that a solution to the second problem can be used to solve the rst problem. We say the rst problemreducesto the second problem. Informal Examples: Measuring the area of rectangle reduces to measuring the length of the sides; Solving a system of linear equations reduces to inverting a matrix The problemLdreduces to the problemAtmas follows: \To see ifhMi 2Ldcheck if hM;hMii 2Atm."Undecidability using Reductions Proposition 1.SupposeL1reduces toL2andL1is undecidable. ThenL2is undecidable.

Proof Sketch.

Suppose for contradictionL2is decidable. Then there is aMthat always halts and decidesL2.

Then the following algorithm decidesL1

On inputw, apply reduction to transformwinto an inputw0for problem 2

RunMonw0, and use its answer.

This can be seen Pictorially as follows.Algorithm for Problem 1

ReductionfAlgorithm

for Prob- lem 2wf(w)yes no

Figure 1: Reductions schematically

The Halting Problem

Proposition 2.The language HALT=fhM;wi jMhalts on inputwgis undecidable. 1 Proof.We will reduceAtmto HALT. Based on a machineM, let us consider a new machinef(M) as follows:

On inputx

RunMonx

IfMaccepts then halt and accept

IfMrejects then go into an infinite loop

Observe thatf(M) halts on inputwif and only ifMacceptsw Suppose HALT is decidable. Then there is a Turing machineHthat always halts andL(H) =

HALT. Consider the following programT

On inputhM;wi

Construct programf(M)

RunHonhf(M);wi

Accept ifHaccepts and reject ifHrejects

TdecidesAtm. But,Atmis undecidable, which gives us the contradiction.1.2 Denitions and Observations

Mapping Reductions

Denition 3.A functionf: !iscomputableif there is some Turing MachineMthat on every inputwhalts withf(w) on the tape. Denition 4.Areduction(a.k.a. mapping reduction/many-one reduction) from a languageAto a languageBis a computable functionf: !such that w2Aif and only iff(w)2B In this case, we sayAisreducibletoB, and we denote it byAmB.

Convention

In this course, we will drop the adjective \mapping" or \many-one", and simply talk about reduc- tions and reducibility.Reductions and Recursive Enumerability

Proposition 5.IfAmBandBis r.e., thenAis r.e.

Proof.Letfbe a reduction fromAtoBand letMBbe a Turing Machine recognizingB. Then the Turing machine recognizingAis 2

On inputw

Computef(w)

RunMBonf(w)

Accept ifMBaccepts, and reject ifMBrejectsCorollary 6.IfAmBandAis not r.e., thenBis not r.e.Reductions and Decidability

Proposition 7.IfAmBandBis decidable, thenAis decidable. Proof.Letfbe a reduction fromAtoBand letMBbe a Turing MachinedecidingB. Then a

Turing machine that decidesAis

On inputw

Computef(w)

RunMBonf(w)

Accept ifMBaccepts, and reject ifMBrejectsCorollary 8.IfAmBandAis undecidable, thenBis undecidable.1.3 Examples

The Halting Problem

Proposition 9.The language HALT=fhM;wi jMhalts on inputwgis undecidable. Proof.RecallAtm=fhM;wi jw2L(M)gis undecidable. Will give reductionfto showAtmm

HALT =)HALT undecidable.

Letf(hM;wi) =hN;wiwhereNis a TM that behaves as follows:

On inputx

RunMonx

IfMaccepts then halt and accept

IfMrejects then go into an infinite loop

Nhalts on inputwif and only ifMacceptsw. i.e.,hM;wi 2Atmif(hM;wi)2HALTEmptiness of Turing Machines Proposition 10.The languageEtm=fhMi jL(M) =;gis not r.e.

Proof.RecallLd=fhMi jM62L(M)gis not r.e.

L dis reducible toEtmas follows. Letf(M) =hNiwhereNis a TM that behaves as follows: 3

On inputx

RunMonhMi

Acceptxonly ifMacceptshMi

Observe thatL(N) =;if and only ifMdoes not accepthMiif and only ifhMi 2Ld.Checking Regularity Proposition 11.The language REGULAR=fhMi jL(M)is regulargis undecidable. Proof.We give a reductionffromAtmto REGULAR. Letf(hM;wi) =hNi, whereNis a TM that works as follows:

On inputx

Ifxis of the form0n1nthen acceptx

else runMonwand acceptxonly ifMdoes Ifw2L(M) thenL(N) = . Ifw62L(M) thenL(N) =f0n1njn0g. Thus,hNi 2

REGULAR if and only ifhM;wi 2AtmChecking Equality

Proposition 12.EQtm=fhM1;M2i jL(M1) =L(M2)gis not r.e. Proof.We will give a reductionffromEtmto EQtm. LetM1be the Turing machine that on any input, halts and rejects i.e.,L(M1) =;. Takef(M) =hM;M1i. ObservehMi 2EtmiL(M) =;iL(M) =L(M1) ihM;M1i 2EQtm.4quotesdbs_dbs17.pdfusesText_23