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
33 views

Show that the following language is undecidable

$\{ M \mid M \text{ is a machine that runs in }100n^3 + 300\text{ time }\}$ I am currently stuck with this one. I thought of reducing HALT to M as the reduction seems legitimate to me: if the first ...
1
vote
1answer
41 views

Is $L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not accept}\ 010 \} $ Turing recognizeable?

I'm working on the following problem: Is the following language Turing recognizable (recursively enumerable) ? $$L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not > ...
5
votes
1answer
222 views

How to prove the emptiness of intersection of two context free languages is undecidable?

Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful. Do you maybe ...
0
votes
1answer
31 views

The problem of equivalence of a CFG and a RG? [duplicate]

Given a context-free grammar and a regular grammar, check whether they are equivalent. It's a fact that it's undecidable, but how could I prove it? I want to clarify that my question is not about ...
1
vote
1answer
30 views

Undecidability of checking whether all words can be generated from a context-free grammar?

I know it's undecidable, but how to prove it? Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate ...
1
vote
1answer
25 views

A question about decidable and undecidable problems

Maybe this question is not very smart but I really wanna learn this thing. also, I need someone who is familiar with printing 42 problem and zero program problem. This is the context: Consider the ...
-1
votes
0answers
39 views

If two complementary languages are recognizable and their intersection is decidable, there are decidable

Let $L_1$ and $L_2$ denote two languages over $\{0,1\}$ such that $L_1 \cup L_2 = \{0,1\}^*$. Suppose $L_1$ and $L_2$ are recognizable and $L_1 \cap L_2$ is decidable. Prove that $L_1$ and $L_2$ are ...
-1
votes
0answers
67 views

Classify Turing Machine as Decidable, Co-recognizable, Recognizable

$L = \{ \langle M \rangle \mid $ $M$ is a TM and $M$ visits its start state at least twice when executed on ε$\}$. Prove whether $L$ is decidable, recognizable or co-recognizable. I think the ...
1
vote
1answer
49 views

How post correspondence problem is undecidable?

An undecidable problem is a problem that cannot have any algorithm to solve it. Post correspondence problem can be solved using a brute force approach. Then how can it be an undecidable problem?
0
votes
0answers
20 views

Is reduction from A_TM to EQ_TM possible to prove EQ_TM is undecidable?

\begin{align} EQ_{\mathrm{TM}} &= {\{ \langle M,N\rangle : L(M)=L(N) \}}\\ A_{\mathrm{TM}} &= {\{ \langle M,w\rangle : \textrm{TM $M$ accepts $w$}\}} \end{align} I can do it using $E_{\mathrm{...
0
votes
0answers
25 views

Is the proof for the undecidability of $A_{TM}$ still valid if we change certain parts?

i have a question based on a question i saw exists on the site, but with wrong information in it and no answer there, so i am reposting it with valid information(cited wrong from the book). on page ...
0
votes
1answer
100 views

How to prove the set of Turing machines that accept a string and its mirror is undecidable?

I'm trying to prove the undecidability of the following language. $$L=\{\langle M \rangle\mid M\text{ is a Turing machine and there is a string }w\\\text{ s.t. }M\text{ accepts }w\text{ and }M\text{ ...
0
votes
0answers
64 views

Proving language K is undecidable using the diagonalization method

I have a problem proving the following properties of given language K: $K = \{< M > | M\ accepts < M >\}$ I am trying to prove that language K is Turing-recognizable but undecidable ...
3
votes
2answers
74 views

One counter automaton as a function

We can associate a one counter finite automaton with a function $f:\Sigma^* \to \mathbb{N} \times \{0,1\}$, where $f(x)=(n,b)$ describes the state where the automaton terminates when fed an input word ...
0
votes
0answers
31 views

Effects of changes in the proof that $A_{\text{TM}}$ is undecidable

In the proof that $A_{\text{TM}}$ undecidable we use the following machine: $D =$ On input $\langle M, w \rangle$: Simulate $M$ on input $w$. If $M$ ever enters its accept state, accept. ...
1
vote
1answer
159 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
255 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
74 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
105 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
61 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
40 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
85 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
68 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
89 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
62 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
42 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
44 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
43 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
79 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
97 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
100 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
120 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
97 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
81 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
42 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
118 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
26 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
16 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
30 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
74 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
238 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
50 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
53 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
38 views

Context sensitive language is context free

Problem of determining whether a context sensitive language is context free is undecidable. How to prove it
4
votes
1answer
63 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
33 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
47 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
37 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 ...