# Questions tagged [undecidability]

Questions about problems which cannot be solved by any Turing machine.

646 questions
Filter by
Sorted by
Tagged with
11 views

### is L not decidable? [closed]

Let $L = \{\lt M\gt | M \subseteq TM, L(M) = \{1^n0^n | n\ge0\}\}$. Is $L$ not decidable even with a reduction $A_{TM} \le_M L$?
17 views

### Can you apply Rice's Theorem on the following languages? Are they decidable?

Can you apply Rice's Theorem on the following languages? Are they decidable? $$L_1:=\{v\mid v \text{ is the Code of a TM } M_v \text{ and } M_v \text{ has an even number of states.}\}$$ L_2:=\...
33 views

### Union of halting-like problem and non-halting-like problem

I came across the following problem: Define languages $L_0$ and $L_1$ as follows : $L_0=\{⟨M,w,0⟩∣M\text{ halts on }w\}$ $L_1=\{⟨M,w,1⟩∣M\text{ does not halt on }w\}$ Here $⟨M,w,i⟩$ is ...
23 views

### how is the set of undecidable programs related to the set of non-halting programs?

Is there a non-halting program for every undecidable program? is undecidable the "same thing" as non-halting? Thanks!
95 views

### Undecidability of language involving two TMs

I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve. Given $M_1$, $M_2$ Turing machines, is it true that for ...
36 views

### How can I apply Rice's theorem?

I am learning for my computability and complexity exam in which there is always an exercise to decide whether some problem is decidable or not. In one of the past exams, there was the following ...
23 views

### Is it decidable whether Turing Machine never scans any tape cell more than once when started with given string

The problem: Is it decidable that the set of pairs $(M,w)$ such that TM $M$, started with input $w$, never scans any tape cell more than once. How can I easily prove above to be decidable. I found ...
45 views

### Is it decidable if there exists some input such that the TM makes at least five moves?

I am reading this excerpt from Ullman's book: I have following doubts: (related to red underline) TM can make 5 left moves or 5 right moves. So it will need at max 11 cells. Then how it says 9? (...
153 views

### Undecidability of two Turing machines acting the same way on an input

So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this: $M_1$ ...
22 views

### Proving sets of regular expressions and context free grammars are decidable [duplicate]

Consider below languages: $L_1=\{<M>|M$ is a regular expression which generates at least one string containing an odd number of 1's$\}$ $L_2=\{<G>|G$ is context free grammar which ...
25 views

### In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?

Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction ...
20 views

### reduction: L1’s decidability is unknown and L2 is undecidable

About this question: Reductions can be tricky to get the hang of, and you want to avoid “going the wrong way” with them. In which of these scenarios does L1 ≤m L2 provide useful information (and ...
20 views

### Proving Problems are Undecidable/ Semi decidable? E.g. Halting Problem, Membership Problem? [duplicate]

I am having issues finding similarities in different cases where a problem such as the Halting Problem or the Accept-Λ problem is reduced to the Membership problem to prove that it is semi-decidable ...
40 views

### TM1 accepts w1 vs TM1 halts on w1

What is difference between following two problems, their decidability and recognizability status: Given Turing Machine TM "accepts" given string w. Given Turing Machine TM "halts on" given string w. ...
29 views

### is the empty language L = ∅ a subset of every languages?

I need to show false the following claim Every language L which is a subset of $A_{TM}$ ($L \subseteq A_{TM}$) is undecidable. For this, I wish to use the empty language L = ∅ (I know is decidable)...
38 views

### if A is decidable then B is decidable too

Assume that a language A is reducible to language B. The claim is true? if A is decidable then B is decidable too. The correct answer is: This claim is wrong. If A is e.g. the empty language (...
310 views

### Prove that the class of CFG languages that are closed under reversal is undecidable

Note The wording of the title may be a bit vague, but I'm not asking if CFLs are closed under reversal. Please see below. Problem Description Given a word $w$, define $w^{r}$ to be its reversal. ...
55 views

### A special case of subset sum

I came across the following problem in my complexity-theory course: Given a set of numbers $A := \{a_1, \dots, a_n\} \subset_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such ...
7 views

### Is it possible to write down every Prolog program+query as the sequent in the sequent calculus?

Prolog program P is set of Horn (definite) clauses, effectively it is the conjunction of implicational formulas. I guess that every Prolog program P with some query Q can be written as ...
59 views

### Is it decidable whether a given Turing machine moves its head more than 481 cells away from the left-end marker, on input ε?

So, while reading some problems on decidability, I came across the following resource: https://www.isical.ac.in/~ansuman/flat2018/tm-more-undecidable.pdf Here, on page no 12, it is written that the ...
14 views

### Is checking if the length of a C program that can generate a string is less than a given number decidable?

I was given this question: Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable? With respect to ...
29 views

### Reducing universal language to language of palindromes

I am trying to understand proof for proving language of all palindromes is undecidable from these slides. It tried to reduce universal language to language of all palindromes on alphabet. The two ...
18 views

### Correct Turing machine representation for Rice Theorem proof

Consider the language L1. From Rice Theorem I know L1 is not decidable (i.e. undecidable). L1 = { R(M) | R(M) is a TM and 1011 ∈ L(M)} For example if I want to represent by diagram a TM $M_1$ ...
37 views

### Is the problem of deciding whether two programs have the same semantics decidable?

If I have program and I want to check whether other programs have the exact same semantics or not, could I always build a machine that could make that decision? This is a question relevant to ...
28 views

### A TM that doesn't decide Σ*, and a TM that doesn't decide the empty set?

I was wondering if it was possible to create a TM that semi-decides (but doesn't decide) either of the following two languages: $\emptyset$ $\Sigma^{*}$ I assume for 2, a one-state TM that just ...
17 views

### TM decidable or undecidable problem

Problem: Given a TM $M$ on the alphabet $\{0,1\}$, determine if there is some input on which $M$ executes for at least 5 steps. Is this problem decidable or not? To check if the problem is ...
42 views

### Why can't we prove decidability of $L= \{ \langle M \rangle : M$ accepts $\epsilon \}$ with a configurations graph?

Since every deterministic Turing Machine can be translated to a graph of configurations such that $M$ accepts a word $w$ iff there is a path from the initial configuration that matches $w$ to an ...
195 views

### Is it decidable “Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.”

I came across below problem in this pdf: Given a TM M, whether M ever writes a non blank symbol when started on the empty tape. Solution given is as follows: Let the machine only writes blank ...
81 views

87 views

### Why is it not possible to prove that two Turing Machines calculate the same function?

I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input?
58 views

### How can $A \cup B$ be decidable if $B$ is undecidable?

My assignment says: "Determine if the following statement is correct: If $A$ and $A \cup B$ are decidable, then $B$ is decidable." The solution says: "Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ ...
44 views

### What are some decidable problems which cannot be solved in real life(due to time and memory constraints)?

The first line of Sipser book for the Chapter- 'Time complexity', says that: Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the ...
Suppose $L$ is the language of the unambiguous grammars. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar. Considering that deciding whether a ...