Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
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 ...
1
vote
3answers
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 ...
2
votes
1answer
51 views

Decide if a language has a word of a given size

Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable: $$L' = \{w \in \Sigma^* | \text{ there exists a word } w'\in L \text{ ...
1
vote
1answer
731 views

Decidability of Turing machines that never move their heads past any input string

$L_1 = \{ \langle M, w\rangle : M \text{ is a TM that never moves its head past the input string } w \}$ $L_2 = \{ \langle M\rangle : M\text{ is a TM that never moves its head past any input string} ...
3
votes
1answer
62 views

Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials

Let's have expressions that are composed of elements of $\mathbb N$ and a limited set of binary operations {$+,\times,-,/$} and functions {$\exp, \ln$}. The expressions are always well-formed and form ...
0
votes
0answers
67 views

Is the undecidability of a given problem undecidable?

Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
2
votes
1answer
281 views

Turing machine with an oracle for a proper subset of a known undecidable language

Consider a Turing machine $T$ with access to an oracle for a proper, nonempty subset of $A_{TM}$, say $L$. That is, $T$ can query this oracle to check whether some string belongs or doesn't belong to $...
0
votes
1answer
43 views

About computable sets

Let TOT be the set of all Turing Machines that halt on all inputs. Find a computable set B of ordered triples such that: TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B] This definition means ...
0
votes
2answers
87 views

How could you "solve" the halting problem if, hypothetically, the busy beaver numbers were "small"?

I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem. I'm trying to figure out how you could ...
1
vote
1answer
189 views

Turing machines moving left at least once

Is the following language decidable? $$ L = \{ \langle M,w \rangle \mid \text{$M$ moves its head left at least once when run on $w$}\}. $$ I feel like this is a decidable language. But I don't know ...
-2
votes
3answers
399 views

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"/convergence? [closed]

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"? The halting problem: The halting problem is a decision problem about properties of computer programs ...
1
vote
2answers
202 views

Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$

I would like to ask for intuition to understand the difference between a CFG generating $\Sigma^*$ and a regular grammar generating $\Sigma^*$.. I got the examples here from Sipser. Let $ALL_{CFG}$ ...
0
votes
2answers
146 views

Is it decidable for a NPDA to halt?

I know that it is decidable for an NPDA to accept a string $w$, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string. But are there ...
1
vote
0answers
49 views

Is it semidecidable to test whether a Turing decidable language is empty?

I'm not sure how to go about solving this. I tried this: Suppose L is a Turing decidable language. Turing Machine M1 is a decider of L and M2 is a decider of the complement L We construct a TM U ...
0
votes
0answers
34 views

Is it decidable to know the number of positions used by a Turing machine for a fixed input?

I'm having trouble proving if the following language is recursive, recursively enumerable, or not r.e. at all: the set of all encodings of Turing machines $M$ such that the number of positions in the ...
0
votes
0answers
53 views

A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $...
2
votes
1answer
375 views

Halting problem for fixed Turing machine and fixed input

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$. What if we fixed both the machine and the input? I.e., is it decidable for every ...
0
votes
0answers
31 views

Find decidable sets such that $A$ reduces to $B$ but not vice versa

I am stuck in this problem, so any help is appreciated. The problem asks to show that there exists decidable sets $A$ and $B$ such that $A \leq_{m}^{p} B$ but $B \not \leq_{m}^{p} A$, and that $A$, $B$...
0
votes
1answer
57 views

EVEN-CFL Decidable / Undecidable - Rice-Theorem

Let EVEN-CFL $=\left\{w | M_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\}$ Question : Is EVEN-CFL ...
3
votes
2answers
384 views

show that in every infinite computably enumerable set, there exists an infinite decidable set

I came across this problem: Show that in every infinite computably enumerable set, there exists an infinite decidable set. As an attempt to solve the problem, I could only think of a proof by ...
0
votes
1answer
75 views

show that this decidable set $C$ exists

I came across this problem which says that given disjoint sets $A$ and $B$ s.t $\bar{A}$ and $\bar{B}$ are both computably enumerable (c.e.), there exists a decidable set $C$ s.t. $A \subseteq C$ and $...
-1
votes
1answer
158 views

Design a DFA recognising the following language

Design a DFA over alphabet (a,b) such that for all it's string no prefix contain two more a's than b's and two more b's than a's and the number of a's is equal to b's. Is it possible to design a DFA ...
2
votes
2answers
438 views

Why doesn't the recursion theorem prove there is an undecidable finite set?

I created something similar to Sipser's proof for the undecidability of $A_{TM}$ (theorem 6.5), "proving" the undecidability of a set that must be finite. Presumably, it's wrong, but I can't ...
0
votes
1answer
41 views

Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e

An example from Sipser's book, Introduction to the Theory of Computation, shows that it is not decidable for a $TM$ to recognize whether a $CFG$ (or a type 2 grammar) generates $\Sigma^*$, where $\...
2
votes
1answer
180 views

Prove {<M> | TM M on input 3 at some point writes symbol "3" on the third cell of its tape} is recursively enumerable but not recursive

Question: Let $$S = \{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape} \}.$$ Show that $S$ is r.e. (Turing acceptable) but not recursive ...
0
votes
2answers
89 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? (...
3
votes
1answer
897 views

Is chess game movement TM decidable?

If we have a finite chess board and two figures x and y. Is it possible to get y from x by following chess rules and when white is y and white starts from y placement. Is this decidable? My ...
2
votes
2answers
1k views

Recursive language subtracted from recursively enumerable language

This is a homework problem but I am awfully confused. The problem reads as follows: If $L_1$ is recursively enumerable but not recursive, and $L_2$ is recursive, then which of the following is the ...
1
vote
2answers
274 views

Determining the classification of languages

$L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$ halts on $w$}\}$ $L_1 = \{ \langle M, w, 1 \rangle \mid \text{$M$ does not halt on $w$}\}$ $L = L_0 \cup L_1$ I need to determine where in ...
0
votes
3answers
913 views

Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable

I tried to prove by contradiction. $L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable. $$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, ...
2
votes
2answers
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 & ...
4
votes
4answers
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,...
0
votes
1answer
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 ...
1
vote
1answer
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. ...
1
vote
1answer
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, ...
0
votes
1answer
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!
3
votes
0answers
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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$ ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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\}$ ...
0
votes
2answers
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 (...
0
votes
1answer
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)...
6
votes
1answer
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. ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
27 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 ...
1
vote
1answer
50 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 ...

1 2 3
4
5
16