 Regular tm is undecidable      regular tm is undecidable g. I see the big picture idea with $M_2$: in step 1, $M_2$s construction gives a nonregular language and step 2 in $M_2$s construction gives a regular language if $M$ accepts $w$. The essence of "reducing one problem to another" is the existence of a function from one language to another. Construct a TM 𝑁𝑁as follows: 2. I get that the idea is to show that if we can decide $REGULAR_{TM}$ then we can decide $A_{TM}$, which is a contradiction and hence $REGULAR_{TM}$ is undecidable. The problem is undecidable if the language is re, but not recursive. Otherwise, reject This is a reduction from TM TM’s as Transducers We have regarded TM’s as acceptors of strings. If 𝑅𝑅accepts, accept. Undecidable Problems (cont. October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). A language L is decidable if there exists a TM M such that for all strings w: –If w ∈ L,M enters qAccept. (b) If H accepts, then reject. Consider the language CON TM = fhM 1;M 2;M 3ijM 1;M 2;M 3 are TMs and L(M 1) = L(M 2) L(M 2)g: Claim 9. Clearly, N is a TM deciding X TM. Undecidable Problems (3) Does a TM accept a regular language? REGTM = {hMi|M is a TM and L(M) is regular} Theorem: REGTM is undecidable. The solution is in the textbook and we’ll discuss in tutorial. ) REGULAR TM = fhMijM is a TM and L(M) is regularg. Then construct an algorithm such that the algorithm takes instance w as input and converts it into another instance x of P2. Can check if m × n = p by repeatedly subtracting out copies of n. A TM is undecidable. The proof (to be gone through in class) shows that, in fact, the more restricted language Lselfaccept = f< M;< M >>j M is a TM g is undecidable. Let L(R) be the language represented by regular expression R. This problem is the same as determining whether the Turing machine recognizes a regular language. In the Universal TM / Halting Problem we proved that the "halting problem" is undecidable, translating this into the question of whether a certain language L is undecidable. Let L (M) be the language accepted by a Turning machine M. . TM = { <M, w> | M is a TM that either accepts or rejects w } Theorem. Assume H exists. Run TM R on input <M,w>. Otherwise, reject. TM. Proof. 11. See Sipser. ===== Step 1. REGTM = fhMijMisaTMandL(M) is a regular languageg is T-unrecognizable. On input hM,wi, • Modify M so that whenever it is about to go into q reject, it instead goes into an inﬁnite loop. 3. Multiplication is in R. The TM we built last Wednesday is a decider. TM is undecidable Let REGULAR TM be the language { M | M is a TM and L(M) is regular} Test a TM with certain property Proof: By reducing A TM to REGULAR TM. Construct a TM ’as follows: 2. Emptyness Problem: Whether a given TM accepts Empty? Finiteness Problem: Whether a given TM accepts Finite? Equivalence Problem: Whether Given two TM’s produce same language?. Consider S = “On input hM;xiwhere M is a TM and x a string: 1 Use hMito construct M 2 = “On input x: 1 If x is of the form 0n1n, accept. We construct a decider for TM as follows: On input , : 1. Assumption: there is a decider R for REGTM Description of a decider S for ATM: On input hM,wi; (1) construct a new TM M1 by on input x if x = 0n1n for some n ≥ 0 ACCEPT else if M accepts w, ACCEPT Nov 12, 2021 · In this next section we show that the problem of Equivalence of Regular Expressions (in short ) over a binary alphabet in a shuffled encoding has an undecidable regular intersection emptiness problem. Any question not answered will be graded as incorrect. The standard example of an undecidable language is: LTMaccept = f< M;w >j M is a TM and M accepts wg Theorem. Regular ( Decidable ( Recursively Enumerable ( All languages DFA/NFA < Algorithms/Halting TM < Semi-algorithms/TM Properties 1. Decidable languages are closed under complementation. We assume that HALT Tv decidable and use that assumption to show that ATM is decidable, contradicz. Proof : ⇐ Assume A ≤m ATM. 1. Theorem. Theorem: TM is undecidable Proof: Suppose for contradiction that there exists a decider for TM. Matiyasevich's theorem proves that multivariable integral polynomials are undecidable. Let us just suppose that REGULAR_TM is decidable. Run 𝐻on input , 2. show A TM Other Undecidable •Is L(G) inherently ambiguous? •Is L(G) ∩ L(G’) = ∅? •If L (G )⊆ LG’? •Is complement of L(G) a cﬂ? •Is L(G) regular? Total CFG is Undecidable •Recall: Conﬁguration of TM M is a 4 tuple: •M’s current state •nonblank portion of the tape before the read head, •the character under the read head, 11/1 Regular Expressions 18. , if we could solve the problem of deciding whether a TM accepts the string Vassar, we could use this decider to solve A TM by constructing a special TM that accepts the string Vassar in exactly the cases where TM M run on string w would accept. If I can build a decider for A_TM, using a decider for REGULAR_TM, it is clear that REGULAR_TM is not decidable. TM = { (M,w) | M is a TM that halts on string w } Theorem: HALT TM is undecidable The Halting Problem Proof: Assume (for a contradiction) there is a TM H that decides HALT TM We use H to construct a TM M’that decides A TM M’(M,w): Run H(M,w) If H rejects then reject If H accepts, run M on w until it halts: If M accepts, then accept If M 11/1 Regular Expressions 18. Similar approach can be used to show that checking whether the language of a TM is a CFL or not is undecidable. Solution 2. Run 𝑅𝑅on input 𝑁𝑁 3. Then apply that algorithm to check whether x is in P2. Which of the following decision problems are undecidable? I. Given a regular expression R and a string $w$, is $\style{font-family:'Times New Roman'}{w\in L(R 11/1 Regular Expressions 18. In an undecidable language, there is no Turing Machine which accepts the language and makes a decision for every input string w (TM can make decision for some input string though). Example: The halting problem of Turing machine Regular,m = {Lm> I m is a TM and Kullis regular 1 theorems Regular tu, is undecidable P: we give a mapping reduction from Atm to Regularity, by showing how to construct a Tm Mw set umw,. E. , Decidable and Undecidable Testlet 6 will be administered on Canvas. Assume REGTM is decidable. Examples of undecidable problems • About Turing machines: – Is the language accepted by a TM empty, finite, regular, or context-free? – Does a TM meet its “specification,” that is, does it have any “bugs. •Use this to show Eq TM = {<M 1,M 2> | L(M 1) = L(M 2) } is undecidable. • In fact, we can show that any nontrivial property of the input/output behavior of programs is undecidable. M' is a TM that is build using the input given to M_A as follows: 1. e. Suppose, towards contradiction, that we had a TM M deciding A TM. Theorem Regular TM is undecidable. Instead, use this problem as a discussion point as you try to determine how the proof that A TM is undecidable speci cally uses that we’re working with Nov 12, 2021 · In this next section we show that the problem of Equivalence of Regular Expressions (in short ) over a binary alphabet in a shuffled encoding has an undecidable regular intersection emptiness problem. E but are undecidable. HALT TM is undecidable. ] A set (or language), L, is recognizable (or recursively enumerable) but undecidable if there exists a TM, M, such that (1) if the input string w belongs to L and M is run with input w, then M halts and accepts it (with acceptable solutions). Let RegularTM be {hMi : M is a TM and L(M) is regular}, where M is an FA, i. Create M’w 2. fi--hand " Imo!:&:&!!' [& if we L@I EaL@w) is regular if and onlyif an>cw> C-Atm so we need to show that a TM can construct MW from an>aw>-accept me-Tus tart Es Nov 12, 2021 · In this next section we show that the problem of Equivalence of Regular Expressions (in short ) over a binary alphabet in a shuffled encoding has an undecidable regular intersection emptiness problem. PROOF - Proof by contradiction. HALTTM is undecidable. a) L = { (M,w) | M is a dfa and on input w visits each one of its states} decidable b) L = { (M,w) | M is a TM and on input w makes an odd number of transitions} L is not decidable. D( M TM is undecidable • Assume REGULAR TM is decidable by some TM R • Given some M, R accepts if L(M) is regular • R rejects if L(M) is NOT regular • Construct S from R as decider for A TM ={<M,w>} as follows • Take M from its input <M,w> and modify M to M 2 that • recognizes non-regular language {0n1n|n≥0} if M does not accept w October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). We will show that ATM m REGTM. TM is undecidable) Today •A TM is unrecognizable •Reductions 10/26/2017 L15. Proof: Suppose !1!"is decidable and let TM )be its decider. Question: Which of the following problems are decidable? Does a given program ever produce an output? If L is context free language then L’ is also context free? All regular languages are in R. We construct TM S that decides A TM. 22: Prove that A is Turing-recognizable iff A ≤m ATM. We REGULARTM = {hMi | M is a TM and L(M) is regular} REGULARTM is undecidable. Proof Sketch: A TM for REGULARTM can be used to construct a TM for ATM. 1 HALT TM is undecidable. Let L(G) be the language generated by a context free grammar G. We know that the language A_TM is undecidable. Theorem: 𝐻 TM is undecidable Proof: Suppose for contradiction that there exists a decider 𝐻 for 𝐻 TM. Helpful programmer utility if it existed: Doesn’t Halt Halts However H does not exist. This proves that REG TM is not Turing recognizable. Time Limit = 20 minutes. / Assume that R decides RegularTM, we con-struct a TM S that decides ATM. Exercise: Try this one (use A TM as the other language). Given a Turing machine M, is L(M) recursive (Turing-decidable)? You can assume without proof that the halting problem for Turing machines is undecidable. Use R to construct S, a TM that decides ATM. Show that REGLEN TM is undecidable. This test is Rated positive by 86% students preparing for Computer Science Engineering (CSE). Yih-Kuen Tsay (IM. If M accepts w, accepts. TM = {<M,w> | M is a TM and M halts on input w}. If P1 is non-RE, then P2 is also non-RE. Nov 16, 2016 · Halting Problem: A halting problem is undecidable problem. Nov 12, 2021 · In this next section we show that the problem of Equivalence of Regular Expressions (in short ) over a binary alphabet in a shuffled encoding has an undecidable regular intersection emptiness problem. If hMi is an invalid TM encoding, then output a special symbol and reject. REGULAR TM REGULAR TM ={<M>|M is a TM and L(M) is regular} •It is undecidable •Proof idea: by contradiction –Assume there exists a decider R for REGULAR TM and use it to build a decider S for A TM –How to use R? •Recall input of S is a pair <M>,w •We construct a modified TM M2 which recognizes a regular language iffM accepts w Jun 28, 2021 · Option 3 is whether language generated by TM is regular is undecidable. TM = fhMi : M is a TM with ‘(M) a regular languageg. { | is a TM and L( ) } is undecidable ( ) 174 TM TM TM m TM EMM M EAE p =< > =∅ ≤ Theorem Proof { | is a TM and L( ) is a regular language} is undecidable ( ) 175 TM TM TM m TM REGULAR M M M REGULAR A REGULAR p =< > ≤ Theorem Proof n * Recognize {0 1 | 0}if does not accept and otherwise n nM w≥ Σ { 1, 2 | 1 and 2 are TMs and ( 1) ( 2 October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). There are 15 questions, a few True/False but mostly MultipleChoice. Then REGTM is undecidable. {TM}$ is undecidable: there's no way to automatically determine whether an arbitrary TM will reject an arbitrary string. Note: this problem is less concrete than some of the other problems we’ve encountered. 2 Otherwise, run M on the input w. If 𝐻accepts, simulate on 4. –If w ∉ L, M enters qReject. Theorem RegularTM is undecidable. 2. The crucial idea is diagonalization. From H we can construct a machine S which decides A TM as follows: S =“ On input <M, w> an encoding of a TM M and a string w: 1. 13 Proof: Suppose to the contrary that HALT TM is decidable, and let R be a TM that decides it. In a similar way we'll talk about other decision problems, ultimately talking about some underlying language. • If problem P reduces to problem Q, and P is undecidable, then Q is undecidable! ‣Otherwise, we could use Q to decide P. show A TM ≤ m REGULAR) –what should f(<M, w>) produce? February 4, 2019 CS21 Lecture 12 14 Undecidable problems Proof: –f(<M, w>) = <M’> described below on input x: •if x has form 0n1n, accept Warmup 6: TMs, Recursive, R. Let R be a TM that decides REGTM. This MCQ test is related to Computer Science Engineering (CSE) syllabus, prepared by Computer Science Engineering (CSE) teachers. If it rejects, reject. •Show E TM ≤ M Eq TM Reduction •To ﬁnd if <M> ∈ E TM: •Let M ∅ be a TM that never accepts anything: L(M ∅) = ∅. Therefore, Mdoes not accept w()L(M0) is regular. In other words, we show that, given hM,wi we can construct the October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). There exist languages that are not R. 3) REGULAR TM is undecidable. We build a new string <M´,w> where M´ is a machine which simulates M until M TM is undecidable HALT TM = { ,𝒘∣ is a TM that halts on string 𝒘} L17. Note: Two popular undecidable problems are halting problem of TM and PCP (Post Correspondence Problem). Eg. Run on input ′ 3. PROOF IDEA This proof is by contradiction. The idea is similar to showing E_TM un REGULAR TM Theorem REGULAR TM = fhMijM is a TM and L(M) is regulargis undecidable. We construct a TM P to decide ATM as follows: Operation of P: On an input < M;w > where M is a TM and w an input string for M we do the following: 1. TM is undecidable. According to Thm 4. TM is undecidable whenever S is non-trivial. Skeleton of Proof: By contradiction. LTMaccept is undecidable. Proof: Consider an instance w of P1. ” 2 Run R on October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). To prove this, we will show that if L is decidable, then HALT is decidable. Let L(M) be the language accepted by a Turning machine M. Then, S TM ={hMi|L(M) is a regular language } We show that if S is a non-trivial property of Turing-recognizable languages, then we can reduce A TM to S TM. Assume a TM exists that decides REGULARTM, call this R. • So must show how a TM that decides HALTTM can be used to decide ATM. , all the TMs that accept a regular language. Option 4 is whether language generated by DFA and NFA are same is decidable. A decision problem P is called “undecidable” if the language L of all yes instances to P is not decidable. For a correct proof, need a convincing argument that the TM always eventually accepts or rejects any input. We construct a decider for 𝐴𝐴. Build a TM *that decides !!": *= on input 4 TM is undecidable Let REGULAR TM be the language { M | M is a TM and L(M) is regular} Testing TM with a certain property (2) Proof Idea: Prove by reducing A TM to REGULAR TM = fhMi: M is a TM and L(M) is regularg: Theorem 3 REGULAR TM is undecidable. In other words: If TM M rejects w, then we want the language of TM,w to be regular. Semi-decidable Problems A semi-decidable problem is subset of undecidable problems for which Turing machine will always halt in finite amount of time for answer as ‘yes’ and may or may not halt for answer as ‘no’. The proof is by reduction from A TM. Suppose H decides HALT TM. Let M2(x) = acceptiﬀ x= 0n1n or M(w) = accept. HALT TM { (M, tv)l M is a TM and M halts on input w}. As before, make a new TM, M 2, that accepts a regular language iff M accepts w. Run REGULARTM = {<M> | M is a TM and L(M) ( Regular} is undecidable. By reduction from ATM. Otherwise, reject This is a reduction from TM to TM straightforward to reduce ATM to HALTTM, which is what we do in the following proof. E. If M rejects, accept. Although an FA is a TM, there is no way we can tell if a given TM is a FA or not. undecidable. S = \On input hM;wi, where M is a TM and w is a string: 1. Do not expect clean, crisp answers. For the sake of contradiction we assume that a TM N decides HALTTM. A problem is unthinkable if there is no tm that accepts the language. Rice’s Theorem: it is a property of the language of TM descriptions because L(M 1) = L(M 2) implies ‘(M 1) = ‘(M 2), which shows that either both are regular or not. Construct the following TM M 2. If the equation REGULAR TM = { M | M is a TM and L(M) is regular} Theorem: REGULAR TM is undecidable Proof: Assume, for a contradiction, that TM R decides REGULAR TM. Some More Undecidable Problems About TMs • The Halting Problem: Given M and w, does M halt on input w? Proof: Suppose HALT TM = {hM,wi : M halts on w} were decided by some TM H. M 2 = \On input x: I If x has the form 1n0n, accept. Hence A TM m REG TM. Exmaple Consider the property S REGULAR deﬁned above. Else (a) Run H on hM,hMii. If M accepts, reject. Each answer is locked as soon as you go to the next question. The key idea is to show that ATM is reducible to HALT TM. May 18, 2021 · We can prove a particular language is undecidable by reducing a known undecidable problem to it. •Suppose Another Undecidable Language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language } Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). Such a TM translates its input to its output. { 0n1n | n ∈ ℕ } is in R. To prove a language is decidable, we can show how to construct a TM that decides it. ” REGULAR = {<M>: M is a TM and L(M) is regular} is undecidable. 1. Proof: –reduce from A TM (i. Theorem 7 Let REGTM = {hMi : M is a TM for which L(M) is a regular language}. Here we show the problem of checking if a Turing Machine has regular language is undecidable (or CFL as its language). universal TM lang LA TM = fhM;wi j M is a TM and M accepts wg 3. More decidable/undecidable problems Problem (a) Is it decidable whether a given Turing machine has at least 481 states? Assume that the TM is given using the encoding below: 0n10m10k10s10t10r10u10v 1 0p10a10q10b10 1 0p 0 10a 0 10q 0 10b 0 100 1 0p 00 10a 00 10q 00 10b 00 10: 00010000100101001000100010000 1 01000101000100 1 0100100100100 1 11/1 Regular Expressions 18. (c) Else if H rejects, then accept. But we know that there no such TM exists! Because the Claim: !1!"={$,,:$,,are TMs and &\$=&(,)}is undecidable. If 𝐻rejects, reject 3. Problem 5. As before, make a new TM, M 2, that accepts a regular language 㱻 M accepts w. EQ TM Regularity of CFL, CSL, REC and REC: Given a CFL, CSL, REC or REC, determining whether this language is regular is undecidable. REGULARTM = { M | M is a TM and L(M) is regular} Theorem: REGULARTM is undecidable Proof:Assume, for a contradiction, that TM R decides REGULARTM Use R as a subroutine to decide ATM s M’w 1. NTU)ReducibilityTheory of Computing 2020 7 / 36 October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). This is how to build a decider for A_TM, M_A using a decider for REGULAR_TM, M_R: M_A = On input , run M_R on input . • Then there is a TM D that operates as follows, on input hMi. 10/26/2017 Classes of languages CFL regular recognizable decidable 1* {0 October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). The property of being regular (or a context free language, or the empty language, or the language of all strings, or) is non-trivial, so if a particular TM accepts a language with the property is undecidable, by Rice's theorem. 3 The language $$REGULAR_{TM} = \{ \langle M\rangle : M \textrm{ is a TM and } L(M) \textrm{ is regular} \}$$ is undecidable. S =  On input 〈 ,𝒘〉, where is a TM and w is a string: 1. But we could just as well visualize TM’s as having an output tape, where a string is written prior to the TM halting. Show that the following problem is undecidable. 11a (not in the book as theorem, but stated on page 174), ATM is Turing TM Therefore, U recognizes A TM U is a universal TM ATM = { (M,w) | M is a TM that accepts string w } ATM is undecidable: (proof by contradiction) Assume machine H decides A TM H( (M,w) ) = Accept if M accepts w Reject if M does not accept w Construct a new TM D as follows: on input M, run H on (M,M) and output the opposite of H. is undecidable. Assuming that a TM R decides REGULAR TM, we construct a decider S for A TM as follows. There exist languages that are R. Given a regular expression R and a string w, is w \in L(R)? II. But how? Apr 21, 2017 · REGULAR TMs. If TM M accepts w, then we want the language of TM,w to TM iﬀ <M’ w> ε Equality of TM’s •Showed a few lectures back that E TM ={<M> | M is a TM and L(M)=∅} is undecidable. This is a reduction from October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). H is a machine which uses two inputs on the tape: Nov 11,2021 - Test: Turing Machines & Undecidability- 2 | 20 Questions MCQ Test has questions of Computer Science Engineering (CSE) preparation. THEOREM 5. TM𝐸𝐸. We ﬁnd a computable function f such that hM,wi2ATM if and only if f(hM,wi) = TM,w 2REGTM. Since ATM is undecidable, it must be the case that our assumption that T is decidable is false, so T is undecidable. The problem is so hard you can't even think about it. Theorem 5. The trick is to design an M2 so Note: Two popular undecidable problems are halting problem of TM and PCP (Post Correspondence Problem). Semi-decidable Problems Let Regular TM be the problem of determining whether a given Turing machine has an equivalent ﬁnite automaton. (By contradiction) • Assume that A TM is decided by some TM H. R N Is L(N) Theorem:HALT TM is undecidable The Halting Problem Proof: Assume, for a contradiction, that TM H decides HALT TM REGULAR TM = { M | M is a TM and L(M) HALTTM is undecidable • HALTTM = { M,w ⃒M is a TM and M halts on input w} • Proof is by reduction from ATM. Undecidable problems Theorem: The language REGULAR = {<M>: M is a TM and L(M) is regular} is undecidable. Answers: Let M 1 be a TM that accepts A TM (see Sipser’s book), which is a Turing-recognizable (recursively enumerable) language. 4. Show the following are decidable or undecidable. If accepts, accept. Universal Turing machines Therefore ATM is decidable. If L is regular, we can run the DFA for L on a string w and then either accept or reject w based on what state it ends in. 3 REGULAR TM = fhMijM is a TM such that L(M) is regulargis undecidable. Run R on M’w So, L (M’w) = Σ* M(w) accepts L (M’w) = {0n1n} M(w) does not accept If s = 0n1n, accept Else run M(w) R N Is L(N REGULAR TM REGULAR TM ={<M>|M is a TM and L(M) is regular} • It is undecidable • Proof idea: by contradiction – Assume there exists a decider R for REGULAR TM and use it to build a decider S for A TM – How to use R? • Recall input of S is a pair <M>,w • We construct a modified TM M2 wich recognizes a regular TM’s as Transducers We have regarded TM’s as acceptors of strings. Proof: Suppose for contradiction that there exists a decider 𝑅𝑅 for 𝑅𝑅𝑅𝑅. It is a nontrivial property because we can make a TM M 1 for ?, which has ‘(M 1 #1. 72 Theorem 4. Then we could construct a TM N deciding X TM, as follows: Given input hPi: Run M on hP;Pi. 11/1 Regular Expressions 18. Produce a machine to solve ATM (Again we’re stuck if we just pass <M> to R, so we must pass a different machine as a parameter) October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). It turns out, that the problem is already undecidable if the regular expressions do not use alternation or the Kleene star. A tm can tell you if the answer is yes, if you wait long enough, but if the answer is no, you might wait forever. So option D is correct. accept reject M,w ATM Create M2 a r REGULARTM Regular TM is undecidable • Testing if a Language recognized by TM can be recognized by a simpler language mechanism, regular expressions (or DFAs, NFAs, etc) • Proof by reduction to A TM • Proof by contradiction • Assume there exists a TM R that decides Regular TM • Construct a TM S that decides A TM • We know A TM October 26, 2005 Another undecidable language Let REGULAR TM = {<M> | M is a TM and L(M) is a regular language} Theorem: REGULAR TM is undecidable Proof: Assume R decides REGULAR TM and use R to decide A TM (reduce the A TM problem to the REGULAR TM problem). Let R be a TM that decides REGULAR TM and construct TM S to decide A TM. Let R be a TM deciding REGULAR TM. If P1 is undecidable, then P2 is also undecidable. Given a context-free grammar G, L(G . Theorem (5. There is no general method or algorithm which can solve the halting problem for all possible inputs. as follows: On input 𝑀𝑀,𝑤𝑤: 1. Then we could use H to decide A TM as follows. Regular TM = {hMi: M is a TM and L(M) is regular language}. Which of the following decision problems are undecidable ? I. Show why. Goal: If we can reduce ATM to REGULARTM, then REGULARTM is undecidable as well. TM is undecidable to show that A DFA is not regular. regular tm is undecidable

50n qil td2 kwv 1cs rho 8c4 4u5 zpz npa ym1 q3v 2s3 wmt twr cr1 ips gfg smv hly