Questions tagged [undecidability]

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

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

If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

I was learning about decidability when I thought of this question: If P is partially decidable, is ¬P decidable, partially decidable or undecidable? I think it is Undecidable since if ¬P holds then P ...
user avatar
0 votes
0 answers
27 views

How to show a language is not recursive, without using reductions?

I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
user avatar
-2 votes
0 answers
23 views

Prove ${ \{ p|\mathcal{L}_p \ is \ infinite \} }$ is an undecidable set using Rice's theorem [closed]

I'm struggling trying to applicate the Rice theorem in this set. I suspect I have to prove that there is a non-trivial property which is the infinity, but I'm stuck finding out what is a set index, ...
user avatar
1 vote
1 answer
50 views

Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?

An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide ...
user avatar
1 vote
1 answer
168 views

Undecidability in optimal data compression

There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course: I think it is saying finding the optimal size of given data is undecidable. However, I thought there ...
user avatar
  • 143
0 votes
1 answer
45 views

Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
user avatar
  • 1
1 vote
1 answer
85 views

Proving Undecidability of this Language

Consider the language $$L = \{\langle M \rangle \mid \text{$\exists$ an input $x$, where $|x|<i$, such that $M$ halts on $x$, but it takes at least $j$ steps} \}$$ where $i$ and $j$ are fixed non-...
user avatar
0 votes
1 answer
40 views

If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable

I should prove or give a counterexample to the above statement. In my opinion, this statement is false but I don't manage to find the right counterexample. My idea was to define $C = Σ^*$ because $Σ^*$...
user avatar
  • 117
-2 votes
1 answer
120 views

Halting problem. Decider “recognising itself” in the input? Part 2

This is a "revision" of this question, it contained an error I now see. In a nutshell, I was wondering if in the halting problem proof the decider $D$, after recognising its source code in ...
user avatar
1 vote
1 answer
46 views

For any two languages A and B there exists J such that both A and B are Turing reducible to J

Here is the my attempt: Proof : Suppose $J = \{aa' \mid a \in A\} \cup \{bb' \mid b \in B\}$ such that $a'$ and $b'$ are the symbols that do not belong to any $w \in A \cup B$ and $a,b$ are strings. ...
user avatar
1 vote
1 answer
63 views

Prove that Turing Machine ever writes a blank symbol over a non blank symbol is undecidable

I have been given the following problem from the book Introduction to the Theory of Computation by Martin Sipser and was wondering if my solution is correct: Determine if a Turing Machine ever writes ...
user avatar
  • 181
4 votes
2 answers
445 views

How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?

I have been given the following problem and was wondering if my solution is correct: Say that a variable $A$ in CFG $G$ is necessary if it appears in every derivation of some string $w$ where $w$ is ...
user avatar
  • 181
2 votes
1 answer
51 views

Prove it is undecidable that a Turing machine accepts at least one input w in space $|w|^2$

This question is part of the undecidable lecture by Jeff Erickson. $$\{\langle M\rangle\mid M \text{ accepts at least one string }w\text{ in space }|w|^2\}$$ We should prove that this language is ...
user avatar
  • 21
1 vote
1 answer
58 views

Prove $H2 = \{\langle M\rangle : M$ accepts all inputs in $\{0, 1\}^∗$ whose length is at most $2\}$ is undecidable but recognizable

Yet another question from an exe. in the Computability class taught by Z. Luria - I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable? I mean we ...
user avatar
  • 117
0 votes
2 answers
33 views

Post Correspondence Problem is undecidable

I am reading Introduction to the Theory of Computation by Michael Sipser and I am in chapter 5. It says here that the Post Correspondence Problem is undecidable, but thinking about it, given a ...
user avatar
0 votes
1 answer
32 views

Turing recognizability and Reduction Mapping on pairs of related Turing machines

I am interested in computation and I am lost on undecidability and reductions. I have the following two problems I am stuck on. Let us call 2 Turing machines related if there is an input $w$ on which ...
user avatar
1 vote
1 answer
46 views

Prove Language Is Undeciable Using Diagonalization

I was given the following problem and told it has to be solved using diagonalization. However, I am confused as to why diagonalization would be the solution. Would the answer not be since L is ...
user avatar
-2 votes
1 answer
33 views

Decision problem

Prove the following theorem Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P. Could anyone be able to prove it?
user avatar
1 vote
1 answer
38 views

Why is the language containing the Turing machines which only accept their own encoding not applicable to the diagonalization proof?

I saw this question and asked myself why the original problem is not solvable through diagonalization. Let $$L = \bigl\{\langle M \rangle \mid L(M) = \{\langle M\rangle\}\bigr\}$$ Take the complement $...
user avatar
  • 13
0 votes
1 answer
41 views

Decidability of a given grammar if it is regular

According to my course the question "Is $L(G)$ regular?" undecidable. But I was more interested in knowing the exact algorithm or proof that makes this question undecidable. To further ...
user avatar
2 votes
1 answer
31 views

Why is $E_{LBA}$ undecidable if $A_{LBA}$ is decidable

A linear bounded automaton (LBA) is a restricted TM with finite tape. Let $A_{LBA} = \{\langle M, w \rangle | M$ is an LBA that accepts string $w \}$. It can be shown that $A_{LBA}$ is decidable: ...
user avatar
0 votes
1 answer
33 views

Does proving undecidability implies that H is RE-Complete

If I want to show that H is RE-Complete is it enough to show it's undecidable? or should I prove something else alongeside? $H$ is the halting problem: $H = \{<p,x>|p \textit{ halts on } x\}$\
user avatar
  • 199
2 votes
2 answers
327 views

Why is a Language L(M) {has at least 10 strings} turing recognizable and L(N) {has at most 10 strings} is not?

Why is a Language L(M) {has at least 10 strings} recognizable and L(N) {has at most 10 strings} is not? ...
user avatar
  • 131
1 vote
1 answer
48 views

Is proving NP-(in)completeness generally NP-complete?

Is even distinguishing between NP complete and incomplete problems an NP-hard problem?
user avatar
  • 161
0 votes
0 answers
44 views

Finite Number of Turing Machines that stop after k steps?

For this question suppose Alphabet for input is {0,1}. Given: L={<M> | M stops on every input after maximum 1000 steps} My professor claimed that there is a ...
user avatar
  • 51
2 votes
1 answer
55 views

Is the language of PSPACE Turing Machines decidable?

Let $$L_{\text{PSPACE}}=\{\langle M\rangle : M \text{ is a TM using a polyspace amount of memory}\}$$ Is $L_{\text{PSPACE}}$ decidable? I don't think we can use Rice's Theorem because this doesn't ...
user avatar
  • 283
1 vote
1 answer
46 views

Decidability for intersection of context free and regular languages

I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the ...
user avatar
0 votes
0 answers
29 views

Undecidability of a set of Turing Machines

Considering the following set, I have to say if it is undecidable, decidable or semidecidable: $$S_1 = \{y | \forall n \text{ the Turing Machine } M_y \text{ does not accept any string of length } n\}$...
user avatar
0 votes
1 answer
22 views

What is the meaning of Sub_tm in this context?

Im working on a problem for a homework assignment in finite automata, but I'm having trouble conceptually grasping the problem in the first place. Prove that the following is undecidable: $SUB_{TM} = \...
user avatar
1 vote
0 answers
17 views

Proving set of register machines that halt before k steps for some input is non-recursive

Given an enumeration of register machines $R_n$ that take a single natural number as input, and a constant $k$, the function $f$ is defined as: $$ f(n) = \begin{cases} 1 & \exists m \text{ such ...
user avatar
  • 11
3 votes
1 answer
63 views

Automated Query Equivalence Solver (MongoDB)

The query-equivalence problem is undecidable. However there are theorem provers that attempt to solve instances of undecidable problems. I am curious how I could go about using an automatic theorem ...
user avatar
-2 votes
1 answer
182 views

Halting problem is undecidable proof-:

Confused with this proof. I will point my confusions here. what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine? How do we decide w is ...
user avatar
  • 47
1 vote
1 answer
28 views

The recognizability of $\overline{A}_{TM}$

In undergrad theory classes, the idea of decidability and recognizability is introduced. It's well known that $A_{TM}$, the set of words accepted by a TM $M$, is recognizable but not decidable. We ...
user avatar
-1 votes
1 answer
45 views

Does Turing machine move left on particular input?

We know that RE language is the collection of unrestricted grammar which is known as type-0 grammar that's why emptiness, finiteness of every RE languages is undecidable. My question is how I check ...
user avatar
  • 1
0 votes
1 answer
189 views

Why REC languages is undecidable under emptiness and finiteness?

Membership problem of Recursive languages are decidable. My approach: Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it. For string $w,$ if $w ∈ L,$ then $M$ halts in ...
user avatar
  • 1
0 votes
1 answer
112 views

Rice theorem could apply except RE language?

You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages. $Q_1:$ So ...
user avatar
  • 1
0 votes
2 answers
197 views

Regularity of CFG and DCFL

I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...
user avatar
  • 1
0 votes
1 answer
71 views

Why finiteness problem of CFL is decidable?

We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?
user avatar
  • 1
0 votes
1 answer
65 views

Reasoning given with explanation of Halting Problem

I have read (and re-read) the informal proof of The Halting Problem. Can we not make the same argument using only the Program, without the Input {e.g. H(P) rather than H(P, I)}? I am confused by the ...
user avatar
  • 319
0 votes
1 answer
79 views

Reduction from undecidability, decidability to decididabilty

If given any two language both $L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample ...
user avatar
  • 1
7 votes
1 answer
342 views

Prove that "If $L$ is a context-free language, is $\overline{L}$ also context-free?" is undecidable

Lately I need to find the decidability of the following decision problem: If $L$ is a context-free language, is $\overline{L}$ also context-free? I know that context-free language is not closed ...
user avatar
1 vote
0 answers
27 views

How to reduce $\overline{K} \leq L$, or how to show semi-decidability of a given language?

I'm currently preparing for an exam and I'm having trouble to solve the following Questions. Let $w \in \{0,1\}^*$ and let $L$ be a language defined as follows $$L = \{w \mid \mathsf{time}_{M_w}(x) \...
user avatar
  • 279
1 vote
1 answer
47 views

Intuitive reason why the language of halting machines is Turing reducible but not many-one reducible to its complement

I have seen this statement in my studies and I cannot figure out why it is true. We know that $P_{HALT} \leq_T \overline{P_{HALT}}$, but $P_{HALT} \leq_m \overline{P_{HALT}}$ does not hold. I know, ...
user avatar
  • 11
0 votes
1 answer
90 views

Halts for all rejects, but might accept/loop otherwise?

If a Turing machine halts for all rejects of L but might accept/loop otherwise, how is L's recognizability classified? Recognizability Decidability ${\langle L\rangle}$ ${\langle \overline{L}\rangle}$...
user avatar
1 vote
1 answer
34 views

M does not accept [M] | 'Correction' of proof possible?

The language $D=\{[M]|M([M])=0\}$ is not decidable because of the following argument: Suppose there was a $TM \space M_D$ that decides $D$. Then if we gave $M_D \space [M] $, there would be two ...
user avatar
  • 25
0 votes
1 answer
21 views

Reduction from 2 finite languages when one doesn't include epsilon and the other does

Just did a test about the subject that had the following question: I know it seems trivial and my first reaction was "well of course its true" but the epslilon kinda threw me off. $L_2$={ab,$...
user avatar
7 votes
1 answer
336 views

Reduction to a parameterized problem

I'm trying the following question from my homework: We're given a graph $G$ and parameters $k,\hat{P}, \hat{W}\in \mathbb{N}$. Additionally, each $v \in V(G)$ has a profit and weight: $p_v, w_v\in \...
user avatar
0 votes
1 answer
59 views

Issues in the proof of $E_{TM}$ is Turing reducible to $A_{TM}$

First definition: $A_{TM}$ = $\{ <M,w> | $M is a TM and M on w accepts$ \}$ Second definition: $E_{TM} = \{ <M> |$ M is a TM and L(M) = $\phi \}$ Let $T^{A_{TM}}$ be an oracle Turing ...
user avatar
  • 697
0 votes
1 answer
38 views

Prove undecidable and recognizable

Is there a way that I can use If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$? to prove that $L=\big\{...
user avatar
0 votes
1 answer
67 views

Can a TM decide the binary PCP-Problem?

I am having a little bit of a hard time distinguish between a TM which accepts a language, and a $TM$ that decides a language. To be more precise: $L_1 = \{\langle M\rangle\; | \; M$ accepts the 10-...
user avatar
  • 1

1
2 3 4 5
17