Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
46 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
38 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
31 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
35 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
54 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
25 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'): ...
-3
votes
1answer
29 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
119 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
36 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
157 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?
2
votes
2answers
188 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
1answer
34 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-...
0
votes
2answers
66 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 ...
0
votes
1answer
69 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. ...
2
votes
1answer
58 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
36 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. ...
0
votes
0answers
36 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
2answers
40 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
163 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 ...
0
votes
0answers
38 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
22 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 ...
0
votes
0answers
129 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 ...
3
votes
1answer
89 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
43 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 ...
-2
votes
2answers
71 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 ...
1
vote
0answers
17 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) ...
0
votes
1answer
90 views

Undecidability of closure under reverse of language accepted by TM

Prove that the following problem is undecidable using a reduction: Given a Turing machine $S$, does $S$ accept a word $w$ iff it accepts its reverse $w^R$? There is a solution here, which I don't ...
0
votes
1answer
43 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 ...
0
votes
1answer
39 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 ...
0
votes
0answers
63 views

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

This is about the halting problem. My questions are: where do you think are logical flaws in what I am going to write? How do you think this does not invalidate the proof for the undecidability of the ...
2
votes
2answers
147 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 ...
1
vote
1answer
70 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 ...
1
vote
1answer
24 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 ...
0
votes
0answers
61 views

How would I prove that nondeterministic Turing machines are undecidable?

How would I go about proving that the language: $$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$ is undecidable? I looked at the proof for $A_{TM}$ ...
2
votes
0answers
89 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 ...
3
votes
0answers
92 views

is it decidable whether a grammar in Chomsky normal form has useless rules?

Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
4
votes
1answer
308 views

Undecidability of “is this CFG prefix-free?”

I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition). Another thread has the very different question "...
8
votes
1answer
181 views

What is a list of “reasonable but undecidable” theorems?

There are some theorems that go along the lines of "all reasonable properties of <math subject> are computationally undecidable." Here are two examples: Rice's Theorem: "all ...
1
vote
1answer
25 views

Not understanding this way of proving undecidability of the termination problem

I am reading some slides on Algorithm to understand why termination is an undecidable problem. The slides say the following: – Assume termination(P) always terminates and returns true iff P always ...
1
vote
1answer
61 views

Cannot understand reductions from the halting problem and its complement

When I was going through the reductions from $HP$ and $\overline{HP}$ in this handout, I do not understand how everywhere the following claim is made: $$⟨M,x⟩ \in \overline{HP} ⇒ \text{M does not halt ...
-1
votes
1answer
71 views

Is this Language decidable?

As the title says; is this language decidable and how do you prove it? $$L =\{\langle M\rangle \mid M \text{ is a Turing Machine and there is an input that } M \text{ halts on} \} $$
0
votes
1answer
95 views

Algorithmic problem of regular, context-free, and recursively enumerable languages

Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free. Are the following problems algorithmically decidable? Is $L_1 \cap L_2 = L_3$? Is $L_1 \...
1
vote
1answer
54 views

Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

I want to ask if $\{w|\forall x\in T(M_v):|w|>|x|\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M_v)|<\infty$. My idea: It is co-semi-decidable since as soon as i ...
2
votes
1answer
47 views

Union of every language within group of decidable languages is also decidable?

So I was trying to solve following exercise: Let $(L_{i})_{i \in \mathbb{N}}$ be a family of decidable languages - this means that every $L_{i}$ is decidable. Then $\cup_{i \in \mathbb{N}}L_{i} $ is ...
1
vote
1answer
34 views

Why is the following language undecidable?

I'm currently learning for my exams this semester and tried to solve some old exams from the last years. The question is to show, that L ist undecidable. $L=\{w|T(M_w)\neq\emptyset \land \forall x \in ...
0
votes
1answer
57 views

Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. ...
0
votes
1answer
40 views

Undecidability of the language of all Turing Machines with repeat strings as their language

Show that the language consisting of all Turing machines whose language consists of strings that can be broken up into two consecutive and equal strings is undecidable. I would prefer if reduction was ...
0
votes
1answer
121 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\}^∗\}$...
1
vote
1answer
96 views

How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

I want to prove that $L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$ is undecidable I am not sure about this. This is my try : Suppose L is decidable. Let $E$ be the decider from $L$. Let $A$ be ...
1
vote
1answer
24 views

Is the Post Correspondence Problem with more than two rows harder than the standard two-row variant?

The standard Post Correspondence Problem concerns tiles with two rows of symbols, and whether a tile arrangement can be made so that the sequence of the top symbols of the tiles is equal to the bottom ...

1
2 3 4 5
15