Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
-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
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
124 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
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
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....
-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 ...
0
votes
1answer
188 views

Is there an undecidable language that is mapping reducible to its complement?

Is there an undecidable language A that is mapping reducible to its complement? If it is possible, since A is an undecidable language, so A's complement must also be an undecidable language. But i don'...
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 ...
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 ...
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
242 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
vote
1answer
42 views

Is there a connection between the Undecidability Theorem and "software complexity"?

I was reading Complexity: The Emerging Science at the Edge of Order and Chaos and a certain passage got me really intrigued. When discussing Chris Langton's explorations of artificial life algorithms,...
0
votes
1answer
392 views

Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?

I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?
0
votes
1answer
73 views

How this language belong to R?

Consider the following language $$L= \{ \langle M\rangle | \text{ $M$ is a TM, and $L(M)\in coRE$} \}$$ I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. ...
0
votes
1answer
79 views

Understanding the union of an undecidable language with a finite or decidable language

I'm trying to prove that the language $L \cup A$ is undecidable, when the language $L$ is undecidable and the language $A$ is finite or decidable. This is confusing me because if $L$ were to be a semi-...
2
votes
2answers
260 views

Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable

How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable? Intuitively speaking I think it is indeed undecidable because ...
0
votes
2answers
90 views

Decidability of Turing machines and misconceptions on the halting problem

In an online discussion on Turing machines and decidability recently, I blatantly theorized that any problem about a specific single Turing machine must be decidable, the question of undecidability ...
13
votes
2answers
1k views

Are there any existing problems that wouldn't be solvable with a halting oracle?

I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible ...
2
votes
1answer
82 views

What is the actual scope of the Halting Problem impossibility result?

Consider the Halting problem : No TM H exists which given any TM and input, decides whether that TM will halt on that input. The usual proof (informally) is that if such an H existed, then a function ...
0
votes
1answer
52 views

Is the decision problem, for a Turing Machine are there any input strings rejected decidable?

Given a Turing Machine T, are there any input strings rejected by T. I need to decide whether this is decidable or recursively enumerable. I think it's undecidable, but I'm not sure how to prove it. ...
-1
votes
2answers
85 views

Are there undecidable languages which are well defined?

It would be a mess if the answer had to be NO after all these speculations and theorems about these languages but.. I am not conviced liar paradox is well defined. And Godël himself said his theorem ...
0
votes
0answers
48 views

Let $f$ be a computable and injective function. Is $f^{-1}$ computable and injective?

So I just started learning about computability, undecidability and Turing machines. And I wonder if: Given a computable and injective function $f$, is $f^{-1}$ also computable and injective? I don't ...
0
votes
1answer
47 views

Cryptosystems whose hardness depends on solving the halting problem?

There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes. This post Gives a list of some famous cryptosystems whose underlying ...
-1
votes
2answers
198 views

Decidable questions of undecidable problems

Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a ...
0
votes
0answers
43 views

Show that this language is undecidable

Given the language $K$ $=\{<M> $ where $M$ is a turing machine ( that is on the alphabet {0,1}) and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$ I would like to know if ...
1
vote
1answer
27 views

Does there exist a undecidable infinite language with only a finite undecidable subset?

I know that there's no such thing as a finitely sized undecidable language. However, does there exist an undecidable language where a finitely sized set of undecidable elements are 'hiding among' an ...
2
votes
2answers
171 views

how does Kleene-Post show two languages that are not Turing reducible to each other?

I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument. I've seen ...
0
votes
0answers
252 views

reduction from ALLTM to ETM

I am trying to understand why this "proof" of ETM undecidability is wrong. ALLTM={ < M >|M is a TM, L(M)=∑*} ETM={< M >|M is a TM, L(M)=∅} We know that ALLTM is undecidable, lets ...
5
votes
1answer
262 views

Deciding whether complement of context-free language is context-free

I need to find out if the following problem is decidable: Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language. I am having trouble in defining ...
2
votes
0answers
46 views

Does Rice's theorem apply to sequential logic circuits?

I am wondering if Rice's theorem (or something similar to that) applies also to sequential circuits. I.e. given any finite sequential circuit, can there be an algorithm that can formally verify any ...
0
votes
2answers
88 views

Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ ...
1
vote
0answers
21 views

Is undecidability contained in $PSPACE / o(exp(n))$?

It is not hard to show that $DSPACE(n+1)/2^n$ contains undecidability. But is it possible to make the advice string subexponentially long (while the machine is allowed to have any $poly(n)$ space) ...
2
votes
0answers
96 views

Decide whether a polynomial has a root

Let $A$ be a ring such that all elements of $A$ are complex computable numbers. I'm interested in knowing whether the decision problem that asks, given $P\in A[X]$, if $P$ has a root in $A$ is ...
0
votes
1answer
97 views

Proving the language of non-primes is in NP

I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question. Show the following language is in ...
1
vote
1answer
159 views

Why is universality of CFG undecidable?

Let $\text{ALL-CFG} = \{\left<G\right> \mid G\text{ is a CFG and } L(G) = \Sigma^*\}$. I have understood the proof of ALL-CFG is undecidable, but I wonder why the following proof is not ...
5
votes
4answers
3k views

EQtm is not mapping reducible to its complement

This is a problem from Sipser's book (marked with an asterisk). $EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$ We know that neither $...
0
votes
1answer
41 views

Recognizability and complements

I'm learning about Turing Machines, decidability, and recognizability, and read that if a language is recognizable, its complement is sometimes recognizable. I don't really understand how this could ...
1
vote
0answers
93 views

How does a PDA compare two configurations of accepting histories?

In Michael Sipser's book, they prove that ALL_CFG = { G | G is a CFG and L(G) = Σ∗ } is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of ...

1
2
3 4 5
16