Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
-1
votes
1answer
30 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 ...
-1
votes
0answers
24 views

TM decidable or undecidable problem?

Question: Explain why the following problems are decidable or undecidable (Using rice's theorem where possible). Does the language accepted by a Turing machine contain an even-length word? Holds a ...
0
votes
1answer
137 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 ...
0
votes
1answer
78 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 ...
0
votes
2answers
116 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 ...
0
votes
1answer
31 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?
0
votes
1answer
34 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 ...
0
votes
1answer
75 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 ...
4
votes
0answers
67 views

How to prove that the problem $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
1
vote
0answers
24 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) \...
1
vote
1answer
29 views

Question about Turing and Many-One Reductions

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, ...
0
votes
1answer
70 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}$...
1
vote
1answer
28 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 ...
0
votes
1answer
13 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,$...
7
votes
1answer
329 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 \...
0
votes
1answer
48 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 ...
0
votes
1answer
32 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\{...
0
votes
1answer
41 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 = \{<M> \; | \; M$ accepts the 10-PCP $\}...
0
votes
1answer
29 views

Why is $EQ_{cfg}$ not recognizable but is co-turing-recognizable

I've seen the proof that $EQ_{CFG}$ is not recognizable but its complement is, my problem is that in the proof that it's complement is recognizable, it says that we test every string in $\sum^*$ and ...
0
votes
2answers
31 views

prove language is decidable

The question is: The language L contains $DFAs$ which can accept languages equal to $\Sigma$* prove this language is decidable. I'm new to the Decidability topic and I don't know where should I start ...
0
votes
1answer
34 views

What are some problems that have higher degree of unsolvalbilty than $\Pi^0_2$-complete problems?

I'm looking for some problems that have higher degree of unsolvalbilty in term of arithmetical hierarchy that requires more than 2 quantifiers like $\Pi^0_3$ ,$\Pi^0_4$ etc.
1
vote
1answer
34 views

Is this string substitution problem decidable?

We have the following task: Take as input a finite set of string pairs. Each pair represents a substitution. Replace exactly one instance of the left with the right. A substitution can only be ...
2
votes
0answers
47 views

An approximation variant of the halting problem

It always has been bugging me that we (humans) know pretty easily when most programs we write halt or not, but the halting problem is still undecidable. I have just thought of a variant approximation-...
0
votes
1answer
51 views

Reduction of Turing-machine language

How to show that the following language is undecidable using reduction on the halting problem? $L: = \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle M \rangle$ does not accept any input $\}$ When TM ...
0
votes
1answer
60 views

Reduction of the diagonalization language to the universal language

I'm going through Jeffrey D. Ullman's Introduction to Automata Theory, Languages, and Computations. The author reduces an instance of the membership problem in $L_d$ (diagonalization language) to a ...
1
vote
1answer
58 views

Are run time bounds in P decidable when the problem is promised that an input program must halt?

I'm solving Problem 11-10(b) in "what can be computed". 11.10 Consider the decision problem HALTSINSOMEPOLY (HISP), defined as follows. The input is a program P, and the solution is “yes” ...
0
votes
0answers
51 views

Is the language of Turing Machine encodings decidable is this instance?

I have an exercise question as follows: L is a set of all Turing Machine encodings for which the Turing Machine halts after a number of steps less than or equal to the minimum value among |w| and 1000,...
0
votes
1answer
90 views

A question on decidability

I have a homework question that is as follows: L(P) is a language of ASCII input strings for which a given program, P, returns "yes". Is the set of all input strings P decidable, such that P ...
0
votes
0answers
28 views

Would a "TM starting with a blank tape will ever write a nonblank symbol anywhere before halting" be decidable?

Would a "TM starting with a blank tape will ever write a nonblank symbol anywhere before halting" be undecidable?
0
votes
1answer
35 views

Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"

Do two halting Turing machines accept the same language? Proof that it is undecidable(credit to another user on this website: "Tom van der Zanden"): Let M be an arbitrary Turing machine. Let ...
0
votes
0answers
14 views

Is the halting problem decidable for TMs that do not write to the tape? [duplicate]

Is the halting problem decidable for TMs that do not write to the tape? Once a read only tape TM repeats a configuration, it will loop forever. Therefore, all we have to do to decide the above is ...
1
vote
1answer
38 views

Complement of equality problem of Turing machine is recognisable or not

Complement of equality problem of Turing machines is unrecognisable or not-recognizable but How?. As per my knowledge it is recognisable if you can decide its accept condition but not Reject and ...
0
votes
0answers
26 views

Purpose of Acceptance Problem

I am confused about the purpose/statement of the Acceptance problem: $A_{TM} =\{\langle M\rangle\,s |$ Turing machine $M$ accepts $s\}$ It can be shown that $A_{TM}$ is uncomputable, so we know that, ...
0
votes
1answer
29 views

Proving undecidability of a language with mapping reductions

I'm referring to questions like this one: Mapping reduction to show NeverHalt is undecidable I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
1
vote
1answer
29 views

Proving Undecidability with reductions - Why do some proofs not use an Oracle?

I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf So as I've learnt it, say we want to prove a new Language L is ...
1
vote
2answers
104 views

Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model

For any computable-function, there may be multiple different algorithms (possibly countably infinite). For example, sort has many different implementations/algorithms, that we know of or that we have ...
-2
votes
1answer
19 views

$\{<M>: M \text{ is a finite automata and L(M) contains a word of form } a^ib^j\}$ is decidable?

How can we show that the language $K = \{<M>: M \text{ is a finite automata and L(M) contains a word of form } a^ib^j\}$ is decidable?
-1
votes
1answer
15 views

If $ \text{NV}_{\text{TM}}$ is decidable, then $A_{TM}$ is decidable?

It seems that $ \text{NV}_{\text{TM}} = \{〈N〉: N \text{ a Turing-Machine and } L(N) ≠ ∅\}$ is not decidable. Here is a proof: Suppose that $\text{NV}_{\text{TM}}$ is decidable with the Turing-Machine ...
0
votes
2answers
38 views

Unrecognizability of $L(M_1) \cap L(M_2) = \emptyset$

Let's define a language $$C = \{ \{M_1, M_2\} \mid M_1, M_2 \text{ are TMs s.t. } L(M_1) \cap L(M_2) = \emptyset \}$$ We have to show that $C$ is unrecognizable. I am having trouble going on about ...
1
vote
0answers
45 views

Undecidability of an Intersection

1)"Given a CFL L and a regular language R, is the intersection of L and R an empty set?" decidable? 2)What if we replace L with the complement of L? Either 1 or 2 is decidable and the other ...
0
votes
1answer
33 views

Decidability of languages with dfa/turing-machines

For any alphabet and any natural number k, a language of strings at least k is decidable. So my question is having some alphabet (let's say (0,1)) and some number let's say k=5 then my language has ...
0
votes
1answer
76 views

How to prove (un)decidability

Let's say we have a string s , a code size limit of b bytes and a time limit t, the question is then whether or not it is possible to construct an algorithm that prints the string within the time ...
1
vote
1answer
26 views

Join of recursively enumerable set and its complement

The union of a recursively enumerable set and its complement is $\Sigma^*$, which is definitely recursively enumerable. What if instead we consider the following operation, on an RE set $S$? $$ \{ \# ...
-1
votes
1answer
28 views

Show that a language is not decidable by reducing from ATM

Let (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$) show that the language L={<M1,M2,w> | M1 and M2 both accept or reject w} is undecidable by reducing ATM ...
2
votes
1answer
21 views

Are there decidable non-trivial properties of a LBA's accepted language?

The halting problem and therefore the acceptance problem are decidable for LBAs, but are the infinite extensions of these problems decidable? Given a LBA, can you decide whether there exists an input ...
3
votes
1answer
109 views

Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?

Say I'm given an oracle that tells me whether or not $L(M)$, the set of words accepted by a Turing Machine $M$, is finite. By leveraging this oracle, can I solve the halting problem? That is, on an ...
0
votes
0answers
37 views

A language is decidable iff some enumerator enumerates it in decreasing order [duplicate]

Show that a language is decidable iff some enumerator enumerates the language in decreasing order. What does it mean by enumerator enumerating in decreasing order? I am so confused about this concept....
1
vote
2answers
110 views

Show that a language is decidable iff some enumerator enumerates the language in decreasing order

Show that a language is decidable iff some enumerator enumerates the language in decreasing order. I know a language is decidable iff some enumerator enumerates the language in the standard string ...
0
votes
1answer
47 views

Undecidability and Unrecognizability of Language with two Turing Machines

I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the ...
-2
votes
2answers
66 views

Prove that the language Cats-Vs-Dogs is undecidable

Define Σ = {a, b, c, . . . , z} be the set of letters in the English alphabet. Prove that the following language is undecidable: Cats-VS-Dogs = {(M) | Either “cats” ∈ L(M) or “dogs” ∈ L(M), but not ...

1
2 3 4 5
16