Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
16 views

CFG that generates $1^*$ is decidable

I read somewhere that the problem which asks whether or not a $CFG$ $G$ generates $1^*$ is decidable. The proof goes like this: $1^* \cap G$ is context free since it is the intersection of a regular ...
1
vote
0answers
34 views

How to show that these two disjoint sets $A$ and $B$ exist

I came across this problem which asks to show the existence of two disjoint Turing-recognizable sets $A$ and $B$ such that no decidable set $C$ can separate them... In this case, a set $C$ is said to ...
0
votes
0answers
25 views

Is the emptiness of intersection of two CFLs decidable? [duplicate]

Consider $L = \{\langle L_1, L_2\rangle\mid L_1, L_2 \in \text{CFL} \text{ and } L_1 \cap L_2 = \emptyset \}$. How to prove that $L \notin R $? $L_1, L_2$ encoded in chomsky-normal-form.
-1
votes
1answer
11 views

Is the Languague which contains all TMs which write the blank symbol at firs by the given input w decidable?

Consider the problem of determining whether a Turing machine M on an input w writes the blank symbol at first. Is this decidable ?
0
votes
1answer
19 views

Help me understand this Turing-machine Problem concerning $A_{TM}$

I'm a Physics/C.S. student and have been struggling with this particular problem for a few days now. So the task is as following: Consider the following languages: $\hspace{20pt} L_1 = \{\langle M \...
0
votes
1answer
26 views

Show that for every language there exists a harder language

I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that: $$ A \leq_T B $$ but: $$ B \not \leq_T A $$ If it is $A \leq_TB$ and ...
0
votes
1answer
25 views

Is $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} (un-)decidable?

I have to prove that the language $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} is (un-)decidable. In a previous assignment we proved that $L_1:=${$<M>$|$L(M)=A_TM$} is undecidable. I would say ...
3
votes
1answer
227 views

A variation of the halting problem

Given an infinite set $S \subseteq \mathbb{N}$, define the language: $L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$ where $T_M$ is the ...
1
vote
0answers
37 views

difference between two uncomputable functions

for $L1$ regular language, $L2$ some language, $L1$ \ $L2$ is regular, decidable. yet, the next transition function might not even be computable: $F′=${$\,q:δ(q,w)∈F \, for\, some\, w∈ L2\,$}$.$ $F$ ...
0
votes
1answer
29 views

Proving undecidability for a language which contains string with certain syntax

Lets say we have the following problem: $$\mathcal{L}_1 = \{\langle \mathcal{M} \rangle | \mathcal{M}\ \text{is a Turing machine and $\mathcal{L}(\mathcal{M})$ contains a string with exactly three ...
-2
votes
2answers
78 views

Is a 'discrete language' well-defined?

Are the following well-defined formal languages (in these cases: subsets of {0,1}*) ? An argument w is a member of L under the following rules... Example1: If more than half of w's digits are 1's --...
0
votes
0answers
19 views

TM for Language With a Specific Cardinality

I'm curious about how to build TM that decide and recognize languages defined by cardinality. For example, with the language $L_1$ = $\{w \in \{0,1\}^* | |w| = 1\}$ this is the language with a single ...
1
vote
1answer
105 views

How to decide whether a language is decidable when not involving turing machines?

For instance, consider L = {k : the binary expansion of sqrt(2) contains k consecutive 1s}. Obviously Rice Theorem would not work. I also tried the method of how it is to PCP undecidable but still no ...
0
votes
1answer
48 views

Is $nHALT$ undecidable even if $M$ halts on input $w$ in finite steps

If we have the language $nHALT=\{<M,w,n>;$ $M$ halts on input $w$ in less than $n$ steps$\}$ Is this language also undecidable in the same way that $HALT$ is undecidable? And if so, $nHALT\...
2
votes
1answer
19 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
1answer
96 views

Check if language is decidable

I would like to determine if the following language is decidable or not. L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}. I know that every finite ...
2
votes
1answer
26 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
0answers
19 views

Many-one reductions between the set of true sentences and a particular arithmetical set

Never used this site before so not sure the best way to get help. However, I've been looking at many-one reductions in relations to sentences in logic. Let TH(N) = {ϕ : ϕ is a first order sentence ...
1
vote
1answer
213 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
45 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
30 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 ...
20
votes
5answers
2k views

Halting problem theory vs. practice

It is often asserted that the halting problem is undecidable. And proving it is indeed trivial. But that only applies to an arbitrary program. Has there been any study regarding classes of programs ...
0
votes
1answer
36 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
43 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
3answers
49 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 ...
0
votes
1answer
17 views

Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. ...
-1
votes
1answer
77 views

Turing machine on input w tries to move its head past the left end of the tape

Consider the language $$ L = \{ \langle M,w \rangle \mid \text{$M$ on input $w$ tries to move its head past the left end of the tape}\}. $$ Prove whether L is decidable or not. I tried to prove ...
1
vote
1answer
61 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 ...
1
vote
1answer
61 views

Is there a language that cannot be polynomially reduced to?

Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?
1
vote
2answers
74 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}$ ...
1
vote
0answers
19 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
2answers
43 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 ...
0
votes
0answers
31 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 ...
1
vote
0answers
29 views

How does a PDA compare two configurations of accepting histories?

In Michael Sipser's book, they prove that ALL_CFG is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of implementation) a PDA goes on to compare ...
0
votes
0answers
36 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
125 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
27 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
31 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 ...
-1
votes
1answer
38 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 ...
0
votes
1answer
71 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 $...
3
votes
2answers
255 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 ...
2
votes
2answers
350 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
35 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
142 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
1answer
40 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 ...
0
votes
0answers
27 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:=\{v\mid ...
1
vote
1answer
44 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
27 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
103 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
61 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 ...

1
2 3 4 5
14