Decidability Prof. (Dr.) K.R. Chowdhary Email: kr.chowdhary@gmail.com Formerly at department of Computer Science and Engineering MBM Engineering College, Jodhpur Thursday 13th November, 2025 kr chowdhary TOC 1/ 10 K.R. Chowdhary Theory of Computation Automata, Formal Languages, Computation and Complexity Focuses on pedagogy in its writing, that represents a refreshing approach Ensures comprehensive and enjoyable learning Undergone a rigorous classroom testing ©2025 Get 20% off with this code: SPRAUT Available on Springer Nature Link Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books & eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks, encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply. Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers, book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us. Promotions do not work in combination with other discounts or gift cards. link.springer.com/book/ 9789819762347 Decision Problems We may be interested in following questions: “Is a number number perfect square?” “Is number prime?” “Does a graph has cycle?” “Does the computation of TM halt before 25th transition?” Each of these general question describe a decision problem. A decision problem PP is a set of related questions pi , each of which has es/no answer. For example: kr chowdhary p0 : Is 0 a perfect square? p1 Is 1 a perfect square? p2 is 2 a perfect square? ... Each of the pi is an instance of the problem P. The solution of a decision problem P is an algorithm that determines the answer of every question p ∈ P. A decision problem is decidable, if it has a solution. TOC 2/ 10 Decision Problems An algorithm that solves decision problem should be: Complete: correct answer is given for every problem instance Mechanistic: finite sequence of instructions, each can be carried out without requirement of insight, ingenuity, or guesswork. kr chowdhary Deterministic: With identical input, the same computation is carried. A procedure having the properties of complete, Mechanistic, and deterministic, is called effective procedure. A standard TM is an effective algorithm if it is, Mechanistic, deterministic, and complete. However, it is complete only if, it halts on every input. TOC 3/ 10 Decidable languages Decidable language-3 AEQDFA = {⟨A, B⟩| A and B are DFAs and L(A) = L(B) } Equivalence problem: Test whether two DFAs recognize the same language. Theorem: AEQDFA is decidable languages F = “On input ⟨A, B⟩, where A and B are DFAs: 1 2 3 construct DFA L(C ) = (L(A) ∩ L(B)) ∪ (L(B) ∩ L(A)) (A = B ⇒ C = φ ) Run TM T for deciding AEQDFA on input ⟨C ⟩ if T accepts, Accept; otherwise reject. ” Acceptance problem:ATM Input: A TM’s description ⟨M⟩ and a string w for input to M. Output: Yes/No indicating if M eventually enters qaccept on input w. Acceptance of language consisting of tuples: ⟨M, w ⟩, ATM = {⟨M, w ⟩|M is a Turing description and M accepts input w }. Is ATM Turing recognizable? Defn. Turing Recognizable: A language ATM is “Turing recognizable”if there exists a TM M such that for all w: - If ⟨M, w ⟩ ∈ ATM then M eventually enter qaccept - If ⟨M, w ⟩ ∈ / ATM then M eventually enter qregect or M loops for ever. kr chowdhary TOC 4/ 10 Halting Problem Theorem: ATM is Turing recognizable. U = “On input ⟨M, w ⟩, where M is a TM and w is a string: Simulate M on input w If M ever enters accepts state, then U accepts; if M enters its reject state, U rejects” - U is universal TM - U keeps looping if M neither accepts or rejects - However, if U ≡ M, ATM is unsolvable (i.e.,undecidable) 1 2 A problem is decidable if some TM decides (solves) it. Halting problem: Given a TM M and input string ⟨W , ⟨m⟩⟩, decide whether M halt on ⟨⟨M⟩, w ⟩? The instance of the problem is : en (M)en (w ). Halting = {en (M)e(w )|M halts on w } is not recursive. kr chowdhary TOC 5/ 10 Undecidability of ATM Proof by contradiction: Assume that ∃ some TM H that decides ATM . That is, H accepts if M accepts w, and H rejects if M rejects w. Now we construct a TM D with H as subroutine. This calls H and determine what M does when the input to M is its own description < M >. However, after determining this, it outputs the opposite. That is, it rejects if M accepts, and vice-versa. Call this as H ′ . Define D(< M >) = 1 Construct a TM D (having input < M >) that outputs the opposite of the result of simulating H on input ⟨⟨M⟩, M⟩. 2 Output the opposite of what H outputs, i.e., if H accepts, then reject, and if H rejects, then accept. The above can be rewritten as: If M accepts its own description < M >, then H(< M >) accepts and ∴ D(< M >) rejects If M rejects its own description < M >, then H(< M >) rejects and ∴ D(< M >) accepts What happens if we run D on its own description < D >? From above: (substitute D for M), we have (see next slide) kr chowdhary TOC 6/ 10 Proving Undecidability of ATM If D accepts < D >: H(D, < D >) accepts and D < D > rejects If D rejects < D >: H(D, < D >) rejects and D < D > accepts Which can be further simplified: If D accepts < D >: D < D > rejects If D rejects < D >: D < D > accepts Hence, whatever is done, it must do the opposite. So there is a contradiction. So, D cannot exist. But, if H exists, we know how to make D. H cannot exist; so there is no TM that decides ATM . kr chowdhary TOC 7/ 10 Proving Undecidability of ATM kr chowdhary TOC 8/ 10 A different approach for ATM as undecidable Preceding proof uses self-reference and diagonalization. To obtain table for diagonalization argument, consider that every v ∈ {0, 1}∗ represent a TM. If v does not have form R(M), a one-state TM with no transition is assigned to v. Thus, TMs can be listed as M0 , M1 , M2 , M3 , M4 , M5 , M6 , M7 , . . . corresponding to ε, 0, 1, 00, 01, 10, 11, 000. Consider a table that lists TMs along the horizontal and vertical axes. The i, jth entry in table is:  1 0 if Mi halts when run with input R(Mj ) if Mi does not halt when run with input R(Mj ) Diagonal elements are answers to the self-referential questions: Does Mi halt when run with itself? Undecidable, decidable, recognizable, Unrecognizable: ACFG is decidable ATM is undecidable L ∈ P(Γ∗ ) is unrecognizable, where P(Γ∗ ) is uncountable ¯ = {w | M is a TM and M does not accept w} ATM kr chowdhary TOC 9/ 10 Bibliography Chowdhary, K.R. (2025). Decidability, Undecidability, and Unsolvability. In: Theory of Computation. Springer, Singapore. https://doi.org/10.1007/978-981-97-6234-7_12 kr chowdhary TOC 10/ 10