[PDF] [PDF] Reductions HALTTM is undecidable since ATM





Previous PDF Next PDF



Note on ETM

Skip ahead to section 2.2 or 2.3 and show that ETM is not recognizable. Then by the theorem that. “a language is decidable iff it is both recognizable and 



Reductions

This in turn implies that ETM is undecidable. At least one of them must be not recognizable. ETM is recognizable. ETM is not recognizable.



Homework 8 Solutions

Consider the emptiness problem for Turing machines: ETM = { ?M?



Homework 10 Solutions

However ETM is Turing-recognizable (HW 8



Tutorial 5

If both L and L are recognizable then L is decidable. As we know that ATM HALTTM



5.4 No. For example consider A = {0 1

But ¬ETM is Turing recognizable and ¬ATM is not



10 Reducibility

HALTTM is Turing-recognizable since it can be recognized by TM U. HALTTM is not Turing-decidable. ETM = {< M >



CS 341: Foundations of CS II Marvin K. Nakayama Computer

Since ETM is undecidable (Theorem 5.2) EQTM must be undecidable. • We'll see later that EQTM is not Turing-recognizable not co-Turing-recognizable 



Problem 1 Problem 2

Show that the language ETM = {?M?



COMPSCI 501: Formal Language Theory Reducibility so far

4 Mar 2019 But ETM is Turing-recognizable (why?) which would mean ATM recognizable (false). ? Mapping reductions may not exist!



[PDF] Note on ETM

Skip ahead to section 2 2 or 2 3 and show that ETM is not recognizable Then by the theorem that “a language is decidable iff it is both recognizable and 



[PDF] Homework 10 Solutions

However ETM is Turing-recognizable (HW 8 problem 4) and ATM is not Turing-recognizable (Corollary 4 23) contradicting Theorem 5 22 3 Consider the language



[PDF] CS 341: Foundations of CS II Marvin K Nakayama Computer

Rice's Theorem: any nontrivial property of the language of a TM is undecidable • ETM is not Turing-recognizable • EQTM is neither Turing-recognizable nor co- 



[PDF] Problem 1 - JHU CS

Show that the language ETM = {?M?M is a Turing machines and L(M) = ? } is not Turing-recognizable Proof: We provide two different proofs Proof 1: We 



[PDF] Tutorial 5

As we know that ATM HALTTM ETM are recognizable their complements cannot be rec- ognizable because then the languages would be decidable and we know that 



[PDF] 10 Reducibility

HALTTM is Turing-recognizable since it can be recognized by TM U HALTTM is not Turing-decidable Proof: We will reduce ATM to HALTTM Assume TM R decides 



[PDF] 1 Reducability

HALTTM = {?Mw? M is a TM that halts on input w} is undecidable If A ?m B and B is recognizable then A is recognizable Corollary 5 23



[PDF] Reducibility Decidable vs Undecidable vs Recognizable ?

26 oct 2020 · Theorem: Every nontrivial property about recognizable languages (of Turing machines) is undecidable • The proof is a generalization of the 



[PDF] reducibility

29 juil 2013 · We mentioned that ETM is co-TM recognizable We will prove next that ETM is undecidable Intuition: You cannot solve this problem UNLESS



[PDF] Reductions

HALTTM is undecidable since ATM is undecidable This in turn implies that ETM is undecidable At least one of them must be not recognizable

Skip ahead to section 2.2 or 2.3 and show that ETM is not recognizable. Then by the theorem that. “a language is decidable iff it is both recognizable and 

  • Is ETM Turing-recognizable?

    ETM is not Turing-recognizable. Rice's Theorem: Every nontrivial property of the Turing-recognizable languages is undecidable.

  • Is ETM undecidable proof?

    Note that ?M1? ? ETM ?? L(M1) = ? ?? M accepts w ?? ?M, w? ? ATM. But then TM S decides ATM, which is undecidable. Therefore, TM R cannot exist, so ETM is undecidable.

  • Is EQTM Turing-recognizable?

    EQTM is not recognizable.
  • ATM = {?M,w?M is a Turing machine and M accepts w} However, unlike ADFA and ACFG, ATM is not decidable. But ATM is Turing-recognizable.

Reductions

LetAandBbe languages over the same alphabet .

Analgorithmthat transforms:

Strings inAto strings inB.

Strings not inAto strings not inB.

Bis decidable)Ais decidable.

Ais undecidable)Bis undecidable.

One way to show a problemBto be undecidable is to reduce an undecidable problemAtoB. 1

Reductions

A Turing machineMcomputesa functionfif:

Mhalts on all inputs.

On inputxit writesf(x) on the tape and halts.

Such a functionfis called acomputablefunction.

Examples: increment, addition, multiplication, shift. Any algorithm with output is computing a function. 2

Reductions

LetAandBbe languages over .

AisreducibletoBif and only if:

there exists a computable functionf: !such that for allw2; w2A,f(w)2B.

Notation:AmB.

FACT:AmB,AmB.

w2A,f(w)2Bis equivalent tow62A,f(w)62B. 3

Reductions

To Re-iterate:

1.Construction:f(w) fromwby an algorithm.

2.Correctness:w2A,f(w)2B.

4

An Example involving DFAs

EQ

DFA=fA;BjA;Bare DFAs andL(A) =L(B)g.

E

DFA=fAjAis a DFA andL(A) =;g.

Areduction machineon inputA;Btwo DFAs:

1. Constructs the DFAA0such thatL(A0) =L(A).

2. Constructs the DFAB0such thatL(B0) =L(B).

3. Constructs the DFAM1such thatL(M1) =L(A)\L(B0).

4. Constructs the DFAM2such thatL(M2) =L(A0)\L(B).

5. Constructs the DFACsuch thatL(C) =L(M1)[L(M2).

6. OutputsC.

Correctness:

SupposeL(A) =L(B). Then,L(C) =;.

SupposeL(A)6=L(B). Then,L(C)6=;.

That is,EQDFAmEDFA.

5

An Example involving CFGs

ALLCFG=fGjGis a CFG andL(G) = g.

EQ

CFG=fG;HjG;Hare CFGs andL(G) =L(H)g.

Areduction machineon inputGa context-free grammar with alphabet :

1. Constructs a CFGHwith rules of the formS0 aS0j, for alla2.

2. Outputs (G;H).

L(H) = .

Correctness:

SupposeGgenerates all strings in . Then,L(G) =L(H). SupposeGdoes not generate some string in . ThenL(G)6=L(H).

That is, ALLCFGmEQCFG.

6

The Halting problem

HALT

TM=fM;wjMis a DTM andMhalts onwg.

The reduction machine outputs a DTM that loops wheneverMreaches the rejecting state.

On inputM;w:

1. Constructs the following machineM0:

Read inputx.

SimulateMonx.

IfMaccepts, halt and accept.

IfMhalts and rejects, enter a loop.

2. OutputsM0;w.

That is,ATMmHALTTM.

HALT

TMis undecidable sinceATMis undecidable.

7

The Halting problem

Three machines:

A reduction machine that is a DTM.

Input to the reduction machine isM;w, whereMis a DTM. Output of the reduction machine isM0;w, whereM0is a DTM. 8

The Halting problem

The output DTMM0has the inputMhard-coded into it.

LetM= (Q;;;;qs;qa;qr). What isM0?

M

0= (Q0;;;0;qs;qa;qr0):

Q

0=Q[ fql;qr0g.

Dene0as follows:

For all statesp, for all statesq6=qr, for all symbolsa;b, for allD2 fL;R;Sg: if(p;a) = (q;b;D) then0(p;a) = (q;b;D). For all statesp, for all symbolsa;b, for allD2 fL;R;Sg: if(p;a) = (qr;b;D) then0(p;a) = (ql;b;S). For all symbolsa, include the transition0(ql;a) = (ql;a;S). M

0is constructed fromMby the reduction machine.

9

ETM=fMjMis a TM andL(M)6=;g

A reduction machine on inputM;w:

1. Constructs the following machineM0:

Read inputx.

Ifx6=wthen reject.

Ifx=w, SimulateMonw.

IfMaccepts, halt and accept.

2. OutputsM0.

Correctness:

IfMacceptswthenL(M0) is not empty.

IfMdoes not acceptwthenL(M0) is empty.

That is,ATMmETM.

10

ETM=fMjMis a TM andL(M)6=;g

A

TMmETM.

This implies thatETMis undecidable.

This in turn implies thatETMis undecidable.

At least one of them must be not recognizable.ETMis recognizable. E

TMis not recognizable.

11

EQTM=fM1;M2jM1andM2are TMs andL(M1) =L(M2)g

EQ

TMis undecidable.

IsEQTMrecognizable?

See the text book.

12

Language is Context-free

CONTEXTFREETM=fMjMis a TM andL(M) is contextfreeg

A reduction machine on inputM;w:

1. Constructs the following machineM0:

Read inputx.

Ifxhas the form 0n1n2nthen halt and accept.

Ifxis not of this form, simulateMonw.

IfMaccepts, halt and accept.

2. OutputsM0.

Correctness

L(M0) is ifMacceptsw.

L(M0) is not context-free ifMdoes not acceptw.

A

TMmCONTEXTFREETM.

CONTEXTFREETMis undecidable sinceATMis undecidable. 13 Language is Not RegularREGULARTM=fMjMis a TM andL(M) is NOT regularg

A reduction machine on inputM;w:

1. Constructs the following machineM0:

Read inputx.

Ifxis not of the form 0n1nthen halt and reject.

Ifxis of this form, simulateMonw.

IfMaccepts, halt and accept.

2. OutputsM0.

Correctness:

L(M0) is;ifMdoes not acceptw.

L(M0) is not regular ifMacceptsw.

A TMmREGULARTM.REGULARTMis undecidable sinceATMis undecidable. 14

Not Recognizable

A TMmREGULARTM=)ATMmREGULARTM.REGULARTMis not recognizable. A

TMmREGULARTM=)ATMmREGULARTM

REGULAR

TMis not recognizable.

15

Properties of Reductions

1.AmBandBmC=)AmC.

2.AmB=)AmB

3.AmBandBis decidable =)Ais decidable.

4. LetAbe recognizable. Then,AmAif and only ifAandAare decidable.

5.AmBandBis recognizable =)Ais recognizable.

16quotesdbs_dbs14.pdfusesText_20
[PDF] is expedia good for car rentals

[PDF] is fog a colloid

[PDF] is form 8332 necessary

[PDF] is france constitution written or unwritten

[PDF] is full fat milk homogeneous or heterogeneous

[PDF] is glucose a crystalloid

[PDF] is green a primary color

[PDF] is hamburg a rich city

[PDF] is hand sanitizer dangerous goods

[PDF] is handset leasing profitable for telecom companies

[PDF] is high alkalinity in drinking water bad

[PDF] is interest income taxable in singapore

[PDF] is iphone packaging recyclable

[PDF] is iron a pure substance

[PDF] is iron filings a mixture