Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [undecidability]

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

1
vote
1answer
30 views

Are $A$ and $B$ necessarily be decidable if $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable and $A$ & $B$ being exhaustive?

I found the following question Suppose A and B are recursively enumerable languages such that $A∪B=Σ∗$. Further, suppose $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable. Which of the following is ...
2
votes
1answer
45 views

Confusion about proof of undecidability of REGULAR TM in Sipser's book

in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR_TM which is described as follows : ...
1
vote
2answers
45 views

Recognizer for decidable language and words it doesn't halt on

Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only ...
1
vote
1answer
31 views

How to prove that a problem is undecidable by using the Halting problem?

I cannot understand how to reduce the halting problem to a property to show that is undecidable. For example, I have this property of a Turing Machine and I have to prove if it's recursive or not: "...
1
vote
0answers
26 views

Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages?

One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the ...
1
vote
2answers
86 views

Why are not all recursive languages undecidable?

I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know. If ...
0
votes
0answers
25 views

A set that is not recursively enumerable and not (K'≤ A)

Is there a set A such that it's not recursively enumerable and not(K'≤ A) ? where K' is complement of K= {n| φ n (n) halts} Thanks!
0
votes
0answers
11 views

How to know if a lanugae is undecidable or semi-decidable

I recently learnt about undecidable languages and semi-decidable languages. But I am still quite confused on how I can determine if a language is semi-decidable. Is there any standard theorem or axiom ...
2
votes
1answer
20 views

PCP with commutative alphabet

Post's Correspondence Problem is known to be undecidable. A variant of PCP, namely PCP with partially commutative alphabets is also known to be undecidable. Is the following variant also known to be ...
1
vote
1answer
34 views

Reduce ATM to REGULAR_TM

Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$. Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
1
vote
2answers
108 views

Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
0
votes
2answers
40 views

Halting problem of TM which recognize recursive languages is undecidable?

I am preparing for an exam and I came across this question in one of the tests. Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False) The solution ...
6
votes
2answers
1k views

Relation between Undecidable problems and NP-Hard

I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly. And then, I realized that it is not certain where undecidable problems should be placed. ...
0
votes
1answer
37 views

Is this language recognizable?

Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable. I don't think it's even recognizable, but I'm not sure. Regardless, I ...
0
votes
1answer
32 views

Context sensitive language is context free

Problem of determining whether a context sensitive language is context free is undecidable. How to prove it
2
votes
1answer
37 views

Decidability of factoring algebraic equations

Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution: $$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$ And some arbitrary factorization constraints, say:...
1
vote
0answers
21 views

3-SAT wher each literal appears at most once [duplicate]

I'm currently following a course and we have to prove that a restricted version of the 3-SAT decision problem where each literal appears at most once is solveable in polynomial time. I think such a ...
0
votes
0answers
17 views

Whether language of all turing machines is decidable or undecidable or semi-decidable?

I recently came across this language: $L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$ It was asked in the question to find out whether language L is decidable or undecidable. ...
1
vote
0answers
22 views

Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable

I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that ...
1
vote
1answer
31 views

Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww

Today I did a test in my class, the trace was: Prove that the language $L =\{\langle M\rangle\mid \forall w \in \{0,1\}^\ast: M \text{ accepts }w\implies M \text { accepts }ww \}$, is undecidable ...
2
votes
1answer
38 views

Example for an undecidable language L such that L is reducible to its complement and vice versa

I am searching for an undecidable language $L$, such that $L \leq \Sigma^* \setminus L$ and $\Sigma^* \setminus L \leq L$, but I am not able to find a concrete language and reduction. Is there ...
0
votes
0answers
24 views

Why do we need an opposite machine to prove that Acceptance problem is undecideable?

It is not clear why almost every book uses an opposite Turing machine to get a contradiction. Here in slides they also use the Machine Dwhich simply outputs ...
0
votes
1answer
30 views

Prove that $L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$ not recursively enumerable [duplicate]

Past year paper question: Let $M_i$ denote the Turing machine with code $i$ using the alphabet $\Sigma=\{a,b\}$. Show that the following language is not recursively enumerable: $L = \{a^i \;:\; (\...
2
votes
1answer
41 views

Decidability of Turing Machine accepting exactly 14 words

Would you say that the following problem is undecidable? $$L_1 = \{\langle T \rangle \mid T \text { accepts 14 words}\}$$ My intuition says that this must be undecidable, and I want to try to reduce ...
0
votes
1answer
59 views

Is the language of all TMs accepting all strings starting with 010 decidable?

I am trying to figure out if this language is decidable: $$ \{ \langle M \rangle \mid \text{$M$ accepts all strings starting with 010}\}. $$ My intuition is that it is. Whatever string $w$ starts ...
0
votes
1answer
26 views

A,B decidable: proof that A\B is decidable too

For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too. My idea is as follows: If B is empty or doesnt have elements in common with A, then A\B is ...
0
votes
2answers
29 views

Error in proof of decidability

$L=\{\left<M\right> \ | \ M $ is a TM s.t. $M$ does not accept any string starting with a '1' $\}$. Assume the alphabet to be $\Sigma = \{0,1\}$. By Rice's theorem $L$ is undecidable. I ...
3
votes
2answers
76 views

Does Halts reduce to all other undecidable languages?

In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of ...
0
votes
0answers
31 views

Which subsets of the set of all recursively enumerable languages is recursively enumerable?

I know that, Rice's say's any non trivial subset of the set of all recursively enumerable languages is not recursive. I also remember reading some characterisation of the recursively enumerable ...
1
vote
1answer
16 views

How hard can identifying non-membership in a semi-decidable language be?

A language is called semi-decidable if there is an algorithm for identifying members. There are well-known examples of semi-decidable languages where identifying non-members is equivalent to $\...
2
votes
2answers
77 views

Why did Alan Turing have to define computation before demonstrating undecidability?

It seems to me that Turing could've just presented the following argument: Theorem: Given a computational model $\mathcal{M}$ capable of conditional branching and indeterminate repetition the halting ...
1
vote
1answer
51 views

Decidability of $E_{TM}$ and $A_{TM}$ for “erasing” Turing machines

Why is the $A_{ETM}$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization ...
2
votes
1answer
60 views

Decidability of equivalence of two context free grammars

I got a question regarding the decidability of equivalence of two context free grammars: Construct a Turing machine that decides whether $L(G) = L(H)$, where $G$ and $H$ are two context free ...
2
votes
1answer
52 views

How to reduce a problem?

I am a bit confused on how to reduce a problem. I'll give an example: Let's say there is a problem called HALTEMPTY and we know it is undecidable. $HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
1
vote
1answer
27 views

Problems with decidability open (for a long time) proven decidable

It seems to me that problems whose dedicability remains open for a long time, if resolved, tend to end up being undecidable. A prominent example would be (e.g.) Hilbert's tenth problem, whose ...
3
votes
1answer
96 views

Is {<M,w>|M prints more than 300 non-blanks on input w} decidable?

Let $$ L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$ Is $L_{300}$ decidable? My intuition is it is decidable because given $M$ and $w$, we need ...
1
vote
1answer
93 views

Prove that it is undecidable whether a given LBA accepts a regular set

I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than ...
-1
votes
1answer
61 views

Solving problems that DTM can't solve

Let L be a problem that DTM can't solve. Can we prove that there is an abstract machine that can solve this problem? Here, L is not Halting problem or Hilbert's tenth problem (because we proved that ...
3
votes
2answers
220 views

PCP undecidability

There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here: https://en.wikipedia.org/wiki/Post_correspondence_problem I'll assume whoever will ...
1
vote
1answer
34 views

How to start solving this type of exercise: Determine if $L$ is in $RE\setminus coRE$ or $coRE\setminus RE$ or $R$ or not in $RE\cup coRE$?

I'm asking this, because in every exercise I check if I can relate it to one of the things I know, like:$A_{TM}$, $\overline{A_{TM}}$, ${HALT_{TM}}$,$\overline{HALT_{TM}}$, $E_{TM}$, $\overline{E_{...
2
votes
1answer
340 views

Determining if given languages are regular or recursively enumerable

I came across following problem: Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine $L_1 =\{M|M$ accepts at most 2016 strings$\}$ $L_2=\{M|M$ accepts at least 2016 strings$\}$ ...
0
votes
2answers
112 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, ...
1
vote
1answer
56 views

Artificial intelligence and undecidibility

Can artificial intelligence solve problems like Post correspondence problem?
0
votes
1answer
46 views

Obtaining a computational history of a Turing Machine

I am currently reading the proof presented in Sipser's "Theory of Computation" for the undecidability of the problem of checking whether the language accepted by a linear bounded automata is empty. In ...
1
vote
1answer
81 views

Rice's theorem application on a language that resembles ETM

I'm working on an exercise that involves checking if the Rice's theorem can be applied on a two languages. The first language is $E_{TM} = \{ \langle M \rangle \text{ | M is a Turing Machine and } L(...
1
vote
2answers
45 views

Does the undecidability of the halting problem require Turing Machines to be enumerable?

I (think I) understand the enumeration and then diagonalization proof of the undecidability of the halting problem, but I came cross this proof in SICP below, which does not seem to require the ...
2
votes
0answers
24 views

Do undecidable problems have no HO query? If so, could I have an example?

In descriptive complexity, HO corresponds to ELEMENTARY. ELEMENTARY is a subset of R, so therefore all HO queries are decidable. Then undecidable problems have no corresponding HO query. Is my ...
1
vote
1answer
70 views

undecidability of virus detection

I have been reading the following document about the undecidability of virus detection, available at: https://enterprise.comodo.com/whitepaper/Impossibility_of_Virus_Detection_WP.pdf the problem ...
1
vote
1answer
64 views

Prove that $H$ reduces to $H\varepsilon$

I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem). I am very confused how to PROVE it, I mean it is clear that we can ...
1
vote
1answer
65 views

Turing machine that does not halt on any input

I'm struggling to find a way to show that $$T = \{ \langle M \rangle\mid M \text{does not halt on any input}\}$$ is undecidable. Should I use reduction? If so, reduce this to what &ndashp ...