Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
4
votes
0answers
52 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
23 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
28 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
68 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
26 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
47 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
27 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
20 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
29 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
32 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
46 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
45 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
55 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
56 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
89 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
27 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
34 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
26 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
19 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
28 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
77 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
33 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
32 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
75 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
27 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
20 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
104 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
104 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
45 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
vote
2answers
82 views

Are there 3-colorable maps that can never be colored?

I just watched this explanation of zero-knowledge proofs with Avi Wigderson: https://www.youtube.com/watch?v=5ovdoxnfFV Key claims from the video: Every formal statement can be translated into a map ...
1
vote
2answers
47 views

Turing machine that checks whether a given string is an output of a given machine and input

Is there a Turing machine such that, given a description $\langle M \rangle$ of a Turing machine $M$, an input $x$ and a string $y$, computes whether or not $y$ is the output of $M$ input $x$? My ...
0
votes
1answer
36 views

Deteremine if Language is in $R$ or $RE$

$$L =\left \{ \langle M \rangle \mid \exists x\in \Sigma^* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \}$$ Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$. My ...
0
votes
0answers
42 views

halting problem vs watchdog

I have a theory that all finite state machines can be monitored by a second turing machine with infinite tape to determine if the state of the first machine was repeated thus reaching the conclusion ...
3
votes
1answer
66 views

Characterization of computationally universal functions

Is it correct to state that $u$ is a universal function if and only if $$ \forall f : \text{RE} \quad \exists g : \text{R} \quad \exists h : \text{R} \quad f = h \circ u \circ g $$ where RE is the set ...
1
vote
1answer
76 views

A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?)

I am trying to understand the proof for this theorem (theorem 4.22 of the book 'An introduction to the theory of computation'): ...
-2
votes
1answer
30 views

Decidability of whether $w \in L(M_1) \setminus L(M_2)$

I'm studying for my finals and I came across this question from past exams: Is the following language decidable? $$ L = \{ \langle M_1,M_2,w \rangle \mid w \in L(M_1) \setminus L(M_2) \}. $$ How can ...
2
votes
2answers
241 views

Proving decidability

Regarding the following languages $L_1$ and $L_2$, I want to prove that $L_1$ is decidable and $L_2$ is undecidable. I want to construct a turing machine which can decide $L_1$ and reduce the halting ...

1
2 3 4 5
16