Q2, 3, 4 2. Recall that a language L is decidable if there exists a Turing machine M such that M(x)accepts for all x E L and M(x) rejects for all æ ¢ L. Also, M is Turing recognizable if thereexists a Turing machine M such that M(x) accepts for all x E L and M(x) either rejects orloops for all a ¢ L. Let HALT = {(M, x)| M(x) halts}. Recall that HALT is not decidable.Show that every Turing recognizable language L is Turing-reducible to HALT.3. Suppose that each DTM M is encoded as (M) over some alphabet E. Define two languagesover E as followsA = {(M)| M rejects the input (M)}B = {(M)| M accepts the input (M)}For the sake of this problem, you should assume that the statements “M accepts the input(M)" and "M rejects the input (M)" are both false if it so happens that there are symbolsin the string (M) that are not contained in the input alphabet of M. Prove that there doesnot exist a decidable language C C E* for which both the inclusions A C C and BC C aretrue.4. Consider the languageL = {(M, w) | M on input w tries to move its head past the left end of the tape}.Prove whether L is decidable or not.

It is defined as An automaton can be represented by a 5-tuple (Q, ∑, δ, q0, F), where − Q is a…

2. Recall that a language L is decidable if there exists a Turing machine M such that M(x) accepts for all x € L and M(x) rejects for all x¢ L. Also, M is Turing recognizable if there exists a Turing machine M such that M(x) accepts for all r E L and M(x) either rejects or loops for all a ¢ L. Let HALT = {(M,x) | M(x) halts}. Recall that HALT is not decidable. Show that every Turing recognizable language L is Turing-reducible to H ALT. %3D 3. Suppose that each DTM M is encoded as (M) over some alphabet E. Define two languages over E as follows A = {{M)| M rejects the input (M)} {{M)| M accepts the input (M)} B =

2. Recall that a language L is decidable if there exists a Turing machine M such that M(x) accepts for all x € L and M(x) rejects for all x¢ L. Also, M is Turing recognizable if there exists a Turing machine M such that M(x) accepts for all r E L and M(x) either rejects or loops for all a ¢ L. Let HALT = {(M,x) | M(x) halts}. Recall that HALT is not decidable. Show that every Turing recognizable language L is Turing-reducible to H ALT. %3D 3. Suppose that each DTM M is encoded as (M) over some alphabet E. Define two languages over E as follows A = {{M)| M rejects the input (M)} {{M)| M accepts the input (M)} B =

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Let Σ = {0, 1}. Define the language L0000 = { ⟨M1,M2⟩ | M1 and M2 are deterministic Turing machines, and L(M1)∩L(M2) contains only the string ‘0000’ }. Show that L0000 is an undecidable language.
Fact: ATM {{M, w) | Turing machine M accepts w} is undecidable. So is HALT {(M, w) | Turing machine M halts on w}. = Prove that the following language is undecidable. Here M is a Turing machine. L= {(M) | M halts on at least one input and infinite loops on at least one other input} .
A = {w € {0,1}* | Iwlo = 2*|wl1} wo denotes the number occurrences of 0 in w and w1 denotes the number occurrences of 1 in w Show that by detail a formal description of a Turing machine M which decides A.
Create a Turing machine that computes a mapping reduction from L1 ≤ m L2 where L1 ＝ {w : w ∈ {a,b}* and |W| is even} and where L2 ＝ {anbn : n ≥ 0}
Let L = { <D> | D is a DFA that accepts sR whenever it accepts s } . Show that L is Turing-decidable.
Let L={<G,M> | G is a CFG, M is a TM, and L(M) is a subset of L(G)}. Classify L as (a) decidable (b) Turing-recognizable but no co-Turing-recognizable (c) co-Turing -recognizable but not Turing- recognizable, (d) neither Turing-recognizable nor co-Turing recognizable. Justify your answer
Give a Turing Machine that decides {<M> | M is a Turing machine and L(M) is Turing recognizable} (L(M) is Turing recognizable not decidable)
Let Σ = {0, 1}, and let L10101 ⊆ Σ∗ be a language of exactly all the strings that contain the substring ‘10101’. Define the language L10101 = { ⟨M⟩ | M is a deterministic Turing machine, and L(M) = L10101 } . Show that L10101 is an undecidable language.
Computer Science Show that the language {M: M is a Turing machine with L(M) to be a finite set} is undecidable. You need to establish its connection to ATM= {[ Turing machine M accepts input w}
Let M be a Turing machine and w be a string in the input alphabet of M. Consider the problem A = {(M, w)|M moves left at some point during its computation on w} %3| Show that A is decidable.
draw all Turing machine by hand
4. LetΣ ={a, b}. LetL={aibai|i≥0}.Give a Turing machine (TM) that accepts the languageL.Assume (as in the examples done in our course videos) that, when theTM starts, the head is on a blank symbol,∆, and the input string isimmediately after that blank symbol on the tape. For example, if theinput string wereaaabaaa, then the inital tape configuration would be∆aaabaaa