Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
4k 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....
0
votes
1answer
204 views

Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. ...
0
votes
1answer
40 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 $\}...
1
vote
1answer
739 views

Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

The detailed question is: Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps? I highly assume, that this problem is not decidable because in the worst case ...
7
votes
1answer
325 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 \...
3
votes
1answer
441 views

A variation of the halting problem

Given an infinite set $S \subseteq \mathbb{N}$, define the language: $L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$ where $T_M$ is the ...
4
votes
3answers
1k views

PCP undecidability

There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here: https://en.wikipedia.org/wiki/Post_correspondence_problem I'll assume whoever will ...
1
vote
1answer
25 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,$...
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
2answers
132 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 (...
0
votes
2answers
2k views

Prove ALL$_{\text{TM}}$ is undecidable reduction problem

Given ALL$_{\text{TM}}$ = { < M > | where M is a TM and L(M) = $Σ^*$ } show this is undecidable. I'm also told not to use Rice's theorem. I'm having difficulties with reduction type problems. How ...
0
votes
1answer
718 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: ...
1
vote
1answer
819 views

decidability about intersection of regular language and context free language

Is "Given a CFL L and a regular language R, is intersection of L and R an empty set?" decidable? What if we replace L with the complement of L? One of them is decidable and the other is not. For the ...
0
votes
1answer
18 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 ...
-2
votes
1answer
344 views

Turing machine on input w tries to move its head past the left end of the tape

Consider the language $$ L = \{ \langle M,w \rangle \mid \text{$M$ on input $w$ tries to move its head past the left end of the tape}\}. $$ Prove whether L is decidable or not. I tried to prove ...
0
votes
1answer
43 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
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
2answers
101 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 ...
1
vote
1answer
25 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 ...
1
vote
1answer
179 views

CFG that generates $1^*$ is decidable

I read somewhere that the problem which asks whether or not a CFG $G$ generates $1^*$ is decidable. The proof goes like this: $1^* \cap L(G)$ is context free since it is the intersection of a regular ...
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 ...
0
votes
2answers
49 views

Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property?

I was asking myself if it is not possible to decide the language where a TM M gets the Godel number of a TM M' as input and the checks if, let us say, the TM M' has a certain amount of transitions. My ...
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 ...
0
votes
1answer
305 views

Determine if a language is Decidable or semi decidable

Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$. We need to determine, without ...
2
votes
0answers
45 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
53 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
55 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
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
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
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
33 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
13 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 ...
0
votes
1answer
55 views

Undecidability of TMs recognizing a decidable language

The language $L = \{ \text{M} \mid \text{M is a TM and the set of words w such that M halts on w is decidable} \}$ is given. I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it ...
0
votes
0answers
17 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, ...
1
vote
2answers
75 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 ...
5
votes
1answer
626 views

How can there be undecidable languages in P/1?

I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me. as I learned in class, a turing machine M accepts language L with advice $ {a_n} $ if $\qquad\...
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 ...
0
votes
1answer
171 views

Undecidability of the language of PDAs that accept some ww

I'm trying to solve problem 5.33 from Sipser's Introduction to the Theory of Computation, "Consider the problem of determining whether a PDA accepts some string of the form $\{ww|w\in \{0,1\}^∗\}$...
-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
32 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
1answer
27 views

Many-one reductions between the set of true sentences and a particular arithmetical set

Never used this site before so not sure the best way to get help. However, I've been looking at many-one reductions in relations to sentences in logic. Let TH(N) = {ϕ : ϕ is a first order sentence ...
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$? $$ \{ \# ...
0
votes
1answer
115 views

Are all Recursively Enumerable languages which are not Recursive also Undecidable?

Knowing that all Recursive languanges are Decidable and All Not R.E. Languages are Undecidable (correct me if I am wrong), Are all languages which are R.E. but not Recursive also Undecidable? R.E. ==&...
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
38 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 ...
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 ...

1
2 3 4 5
16