Question:
Which of the following is/are undecidable?
Which of the following is/are undecidable?
Show Hint
Many problems related to Turing machines, such as language equivalence and language regularity, are undecidable.
Updated On: Jan 30, 2026
- Given two Turing machines \( M_1 \) and \( M_2 \), decide if \( L(M_1) = L(M_2) \).
- Given a Turing machine \( M \), decide if \( L(M) \) is regular.
- Given a Turing machine \( M \), decide if \( M \) accepts all strings.
- Given a Turing machine \( M \), decide if \( M \) takes more than 1073 steps on every string.
Show Solution
Verified By Collegedunia
The Correct Option is A, B, C
Solution and Explanation
(A) Undecidable. The problem of deciding whether two Turing machines accept the same language is undecidable because it is equivalent to the language equivalence problem, which is undecidable.
(B) Undecidable. Deciding if a Turing machine's language is regular is undecidable, as it is related to the regularity problem for Turing machines, which is undecidable.
(C) Undecidable. The problem of deciding whether a Turing machine accepts all strings is undecidable and is related to the halting problem, which is undecidable.
(D) Decidable. The problem of determining whether a Turing machine takes more than a fixed number of steps on every string is decidable, as it can be determined in a finite number of steps.
(B) Undecidable. Deciding if a Turing machine's language is regular is undecidable, as it is related to the regularity problem for Turing machines, which is undecidable.
(C) Undecidable. The problem of deciding whether a Turing machine accepts all strings is undecidable and is related to the halting problem, which is undecidable.
(D) Decidable. The problem of determining whether a Turing machine takes more than a fixed number of steps on every string is decidable, as it can be determined in a finite number of steps.
Was this answer helpful?
0
0
Top GATE CS Theory of Computation Questions
- Consider the following context-free grammar \(G\), where \(S\), \(A\), and \(B\) are the variables (non-terminals), \(a\) and \(b\) are the terminal symbols, \(S\) is the start variable, and the rules of \(G\) are described as:
\[ S \to aaB \mid Abb \] \[ A \to a \mid AaA \] \[ B \to b \mid bB \] Which ONE of the languages \(L(G)\) is accepted by \(G\)? - A regular language \(L\) is accepted by a non-deterministic finite automaton (NFA) with \(n\) states. Which of the following statement(s) is/are FALSE?
- Consider the following two languages over the alphabet \( \{a, b\} \): \[ L_1 = \{ \alpha \beta \alpha \mid \alpha \in \{a, b\}^+ { and } \beta \in \{a, b\}^+ \} \] \[ L_2 = \{ \alpha \beta \alpha \mid \alpha \in \{a\}^+ { and } \beta \in \{a, b\}^+ \} \] Which ONE of the following statements is CORRECT?
- Consider the following two languages over the alphabet \( \{a, b, c\} \), where \( m \) and \( n \) are natural numbers. \[ L_1 = \{ a^m b^{m+n} c^{m+n} \mid m, n \geq 1 \} \] \[ L_2 = \{ a^m b^n c^{m+n} \mid m, n \geq 1 \} \] Which ONE of the following statements is CORRECT?
Consider the following deterministic finite automaton (DFA) defined over the alphabet, \( \Sigma = \{a, b\} \). Identify which of the following language(s) is/are accepted by the given DFA.
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions