# Questions tagged [undecidability]

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

788 questions
Filter by
Sorted by
Tagged with
22 views

### Decidability of a language and inclusion between two other languages

I have this assignement that asks to say if the following statement is true or false, and possibly justifying the answer: "Let L₁, L₂ be decidable languages. For every language L s.t. L₁ ⊆ L ⊆ L₂, L ...
2k views

### What does "Every CFL is decidable" exactly mean?

I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means. I know that generation of a particular string by a given CFG is a ...
51 views

2k views

### Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?

I was reading the Sipser's book on the Theory of Computation, 3rd edition and came up with a question. "Does showing a problem and its complement are not Turing-decidable means that the language & ...
1k views

### What approaches are most useful when proving uncomputability of a given function?

I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows: Reduction,...
81 views

### Is L decidable or not

Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$. Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable? But isn't $L$ decidable since it is possible to ...
61 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. ...
127 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 a triplet, ...
28 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!
107 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 ...
135 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 ...
384 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$ ...
256 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 ...
192 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 ...
231 views

### Halting problem vs Universal Language

Wikipedia defines halting set as follows: $H = \{(i, x) |$ program $i$ halts when run on input $x\}$ Ullman defines universal language as follows $U = \{(M, w) |$ Turing machine $M$ accepts $w\}$ ...
626 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 (...
143 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)...
1k 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. ...
3k 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 ...
266 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 ...
406 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 ...