Stack Exchange Network

Stack Exchange network consists of 175 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
55 views

Is it decidable whether a Turing machine M will reach state q on input s?

Given a turing machine $M$, one of its states $q$ and an input word $w$, will $M$ ever reach $q$ on $w$? As we are not given anything about the word length, I assume that we have a finite length word....
3
votes
2answers
184 views

Is the set of language decidable by some Turing machine computing in some given computable time bound decidable

Let $T : \mathbb N \to \mathbb N$ be some computable function. Then by $\mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an ...
2
votes
2answers
61 views

Why cannot we enumerate all Turing machines that have no fixed point?

The language $$ L_1 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) = x\} $$ ($w$ is an encoding of a DTM, $M_w$ is the respective DTM.) is not decidable, according to Rice's ...
0
votes
2answers
66 views

Proving a language as undecidable without using reductions

Let's say our Σ is 0 and 1. I want to disprove the following: There can be Turing Machines that accept only 1's, i.e. 1, 11, 111, etc. Therefore, all languages that have strings of 1's are ...
1
vote
2answers
57 views

Would any continuous model of the universe have/be based on hypercomputational laws?

I've read that when Turing-Church thesis is applied to the universe and physics, one of the three interpretations that we can use and is defended by some important physicists is that: "The universe ...
1
vote
1answer
39 views

Proof of undecideability that one state is reached before another

I'm trying to show that, for a deterministic Turing machine $M=(Q,\Gamma,\Sigma,\delta,q_0)$, the language $K$, which includes all of the words $w \in \Sigma^\ast$ where the calculation of $M$ on $w$ ...
2
votes
2answers
67 views

Is determining if a Turing machine runs in constant time decidable if one assumes it halts?

As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts? The decision problem, more formally: Given a Turing machine $M$ where it is assumed ...
5
votes
4answers
2k views

Is the infinite language unrecognizable in a Turing machine?

This question is building up on an older one, here. But now let's say we keep $Σ=\{0,1\}$. Is the TM that accept anys ($1^x \mid x \gt 0$) recognizable? That means 1, 11, 11111, 1111111, and so on ...
2
votes
2answers
43 views

Is the reverse of a closed under operation maintainable?

I'm looking at the following question from this handout: The class of decidable languages is closed under union My question is, does this hold in reverse? Is there a phrase for this? Basically, if ...
0
votes
2answers
88 views

Can we enumerate finite sequences which have no halting continuation?

Note: this question has been cross-posted to Math.SE, after about a week here. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
1
vote
1answer
45 views

A language which is neither r.e. nor co-r.e

First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$ is RE. I tried to construct a Turing machine: ...
2
votes
1answer
39 views

Decidability of language of TMs which accept only their Gödel number [duplicate]

I am trying to prove that $L = \{\langle M \rangle \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM $M$, and $L(M)$ the language recognized by $M$....
1
vote
1answer
35 views

Rice's theorem applicable to the following language?

Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \} $ be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable. I've heard that I can't use Rice's ...
1
vote
1answer
39 views

REC and RE under intersection

Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither? Assume $L_{3}$ is the intersection of some language $L_{1}$ $\...
1
vote
1answer
68 views

Language of TM is Undecidable

why is this Problem$$L = \{ \langle M\rangle \mid L(M) \text{ is undecidable}\}$$ undecidable? I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case ...
-3
votes
3answers
90 views

Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”? [closed]

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"? That is, if one has a language that's Turing complete, but expresses infinite computation (i.e. may not ...
1
vote
2answers
79 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 ...
2
votes
1answer
67 views

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

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
64 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
42 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
33 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
99 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
12 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
23 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
38 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
138 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
42 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
49 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
36 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
41 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
23 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
1answer
37 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
26 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
40 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
41 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
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
43 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
143 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
173 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
31 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
102 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 ...
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
78 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
62 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
97 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
56 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
32 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
99 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 ...