Questions tagged [undecidability]

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

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

Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable?

I have having trouble with the following question: Given an NFA $A$ and a regular expression $B$, consider the problem of determining if $L(A) = L(B)$. Is this decidable? Prove your answer.
0
votes
1answer
529 views

Decidability of a Turing machine which always halts in at most ten steps [closed]

I have an exam coming up soon and I need help with this. Consider the problem: Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input. Is this decidable? Prove ...
5
votes
2answers
13k views

Why isn't the class of Turing-Recognizable languages closed under Complement?

I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations ...
12
votes
1answer
673 views

Program synthesis, decidability and the halting problem

I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that ...
0
votes
1answer
150 views

Proving undecidability of the language composed of LBAs where their language is empty

As it is explained in Sipser's book, the following language is undecidable and he proves this using the computation history method. $\qquad E = \{\langle M \rangle \mid M\ \mathrm{LBA}, L(M)=\...
11
votes
6answers
26k views

Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?

Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$ Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$? It ...
4
votes
0answers
142 views

Decidability over finite graphs of small degree [closed]

Suppose $\sigma$ is a vocabulary of First Order logic consisting of one binary relation $E$ and let $\phi$ be a $\sigma$ sentence (FO formula with no free variables). Is it decidable whether there is ...
0
votes
1answer
98 views

Can I use infinite numbers in a reduction?

I have to reduce $L_\text{empty}$ to $L_\text{inf}$ where $\qquad L_\text{empty} = \{e \mid |L(P_e)| = 0 \}$ and $\qquad L_\text{inf}= \{e \mid |L(P_e)| = \infty \}$. where $P_e$ is the program ...
2
votes
1answer
454 views

computability - decidability of a prefix language

For any language $L$ over $\{0,1\}^*$, a language $L'$ can be defined as $\{ a | ab \in L \text{ for some } b \in \{0,1\}^* \}$. If $L$ is decidable, is $L'$ decidable? I think that $L'$ should be ...
1
vote
2answers
243 views

Is this a correct decider?

We are given the following language B = {$<M,i>$ : M is a turing machine and $i \in \mathcal{N}$ and M accepts some string in atmost $i$ steps } Is language B decidable ? As per a hint from ...
4
votes
2answers
277 views

Intuition about decidability

Given a language, how do you go about deciding if it's decidable or not? For example: Given a DFA $A_0$ and a TM $M_0$ $L_1 = \{ \langle M \rangle \, | \, M \mbox{ is a TM and }L(M) = L(A_0) \}$ $...
11
votes
3answers
533 views

Is it possible to decide if a given algorithm is asymptotically optimal?

Is there an algorithm for the following problem: Given a Turing machine $M_1$ that decides a language $L$, Is there a Turing machine $M_2$ deciding $L$ such that $t_2(n) = o(t_1(n))$? The ...
5
votes
2answers
208 views

Language comprising of Turing machine encodings

Let $A$ be the language $\{\langle M\rangle\mid M\text{ is a Turing machine that accepts only one string}\}$ According to my understanding, if a Turing machine is able to decide if another Turing ...
3
votes
1answer
1k views

Deciding Recursive/Recursively Enumerable when given Turning machine encoding as a language

Let $L_{1}$ and $L_{2}$ be two languages defined as follows : $L_1 = \{ \langle M\rangle \mid L(M) \neq \emptyset \}$ $L_2 = \{ \langle M\rangle \mid L(M) = \emptyset \}$ where $\langle M\...
5
votes
1answer
1k views

Decision problem and algorithm

I was reading about decision problem. I understand that decision problem tell yes/no answer for an input. The decision is based on a decision procedure also called an algorithm. The wikipedia says ...
5
votes
2answers
418 views

Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?

I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem. Halting ...
4
votes
2answers
1k views

Is undecidable(complement of R) a subset of NP-hard?

Is there an undecidable problem which is not NP-hard?
1
vote
1answer
389 views

Is the intersection of two regular languages regular?

Trivially decidable problem is one in which the problem is a known property of the language/grammar. So intersection of two regular languages is regular should be trivially decidable? But it is given ...
2
votes
3answers
2k views

Undecidability of the following language

So we can prove that the language say $A = \{ \langle M,w \rangle \mid \text{M is TM that accepts } w^R \text{ whenever it accepts } w \}$ is undecidable by assuming it is decidable and use that to ...
2
votes
1answer
696 views

Solvability of Turing Machines

I'm preparing for an exam, and on a sample one provided (without solutions), we have this question: Is the following solvable or non-solvable: Given a turing machine $T$, does it accept a word of even ...
8
votes
1answer
134 views

Question related to Hilbert's 10th problem

Given $n \in \mathbb{N}$ and $p,q \in \mathbb{N}[x_1,\ldots,x_n]$ one can define the following formula in the language of formal arithmetics $$\varphi(n,p,q) = \forall x_1 \cdots \forall x_n : \neg ...
6
votes
1answer
211 views

Showing the function=? is impossible

Here's a lab from a first-year computer science course, taught in Scheme: https://www.student.cs.uwaterloo.ca/~cs135/assns/a07/a07.pdf At the end of the lab, it basically presents the halting problem,...
8
votes
2answers
2k views

How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable? I have tried to reduce this problem to another undecidable ...
3
votes
1answer
179 views

Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?

I have a book that proves the halting problem with this simple statement: $$ A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon $$ It states that halting problem reduces to the ...
2
votes
1answer
224 views

Reduction of A_LBA to E_LBA

I have a rather interesting one to ponder and would love if I could get an answer for it. We were discussing the topic of mapping reduction today in my Computing theory course and I was wondering why ...
4
votes
2answers
273 views

First-order logic arity defines decidability?

I've read first-order logic is in general undecidable, and that could be decidable only when working with unary operators. (I think that's propositional logic, correct me if I am wrong) The question ...
5
votes
1answer
220 views

Hardness of ambiguity/non-ambiguity for context-free grammars

A grammar is ambiguous if at least one of the words in the language it defines can be parsed in more than one way. A simple example of an ambiguous grammar $$ E \rightarrow E+E \ |\ E*E \ |\ 0 \ |\ ...
8
votes
1answer
149 views

Can $f$ be not computable even if $L$ is decidable?

I am trying to teach myself computability theory with a textbook. According to my book, a function $f$ over an alphabet $A=\{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, ...
5
votes
1answer
813 views

When are 2 decision/optimization problems equivalent?

Does anybody know a good definition of 2 decision / optimization problems being equivalent? I am asking since for example allowing polynomial time computations any 2 problems in NP could be ...
1
vote
2answers
230 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 ...
4
votes
2answers
1k views

Visualizing a Non Deterministic Decider

I know that we can visualize a Non deterministic TM as a TM which splits into multiple copies of itself whenever it sees a non deterministic path (Yes, I also know that this is just a visualization ...
12
votes
2answers
2k views

Are all context-sensitive languages decidable?

I was going through the Wikipedia definition of context-sensitive language and I found this: Each category of languages is a proper subset of the category directly above it. Any automaton and any ...
11
votes
2answers
255 views

Decidability of a problem concerning polynomials

I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite ...
2
votes
1answer
899 views

Which properties of context sensitive languages are decidable?

There are two context-sensitive languages, $L_1$ and $L_2$. Which of the following statements about them are decidable respectively undecidable? $L_1 = \emptyset$ $L_1 = \Sigma^*$ $L_1 \cap L_2 = \...
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,...
10
votes
1answer
15k views

What is the difference between halting, accepting, and deciding in the context of Turing machines?

Does accepting mean that the TM will read and recognize a char from the cell it's currently reading from? And is it the case that a TM halts iff the input is decidable?
14
votes
2answers
6k views

Is it decidable whether a TM reaches some position on the tape?

I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$. For an integer $c>1$, and the following three problems: ...
8
votes
1answer
226 views

How to show that the set of machines which accept languages in $\mathrm{NP}\smallsetminus\mathrm P$, is decidable only if $\mathrm P=\mathrm{NP}$?

I'd like your help with proving that the language $$L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}$$ is decidable iff $\mathrm{P}=\mathrm{NP}$. If $\mathrm{P}=\...
19
votes
2answers
11k views

Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?

Let $F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$. I need to decide whether F is decidable or recursively enumerable. I think it's decidable, but I don't know how to ...
14
votes
1answer
338 views

For a Turing Machine $M_1$, how is the set of machines $M_2$ which are “shorter” than $M_1$ and which accept the same language decidable?

I wonder how come that the following language is in $\mathrm R$. $L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a TM, and } L(M_1)=L(M_2), \text{ and } |\langle M_1\rangle| > | \...
5
votes
1answer
2k views

Examples of undecidable problems whose intersection is decidable

I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the ...
2
votes
1answer
717 views

Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

I'm trying to prove that $L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$. I'm not sure whether to reduce the halting ...
38
votes
2answers
7k views

Perplexed by Rice's theorem

Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time! Of course, Rice's theorem doesn't simply say "everything is impossible". ...
5
votes
2answers
194 views

Semi-decidable problems with linear bound

Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a ...
4
votes
2answers
245 views

Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?

From this statement As there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language. I would like to understand why similar reasoning ...
10
votes
4answers
5k views

Is there an undecidable finite language of finite words?

Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable? I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \...
25
votes
5answers
10k views

Why isn't this undecidable problem in NP?

Clearly there aren't any undecidable problems in NP. However, according to Wikipedia: NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that ...
15
votes
5answers
2k views

Are there undecidable properties of non-turing-complete automata?

Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability). I would like to get ...
11
votes
2answers
776 views

Can we show a language is not computably enumerable by showing there is no verifier for it?

One of the definitions of a computably enumerable (c.e., equivalent to recursively enumerable, equivalent to semidecidable) set is the following: $A \subseteq \Sigma^*$ is c.e. iff there is a ...
12
votes
4answers
3k views

Operations under which the class of undecidable languages isn't closed

Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable ...