Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
27 views

Deciability of equivalence of two countably infinite sets where elements are pairs

Consider a set $A = \{\langle X, Y\rangle$ where $X, Y \in S\}$ and $S$ and $A$ are countably infinite sets. Consider another set $B = \{\langle P, Q\rangle, \text{where } P, Q \in R \} \text{ and } ...
0 votes
1 answer
45 views

What is the role of diagonalization in the proof of undecidability of the halting problem?

I'm trying to understand the proof of undecidability of the halting problem. Some resources give a short proof based on a proof by contradiction. There is no mention of diagonalization. But some ...
1 vote
1 answer
34 views

Decidability terms clarification

I just need some clarification regarding the different terms we use in theoretical computer science, especially regarding decidability. Decidable: A language $L$ (a set of strings) is decidable if ...
0 votes
1 answer
30 views

Undecidability of the exactly-1-in-k halting problem

The problem: Given $k>1$ Turing machines decide if for every possible input exactly one of them halts. Is this variant of halting problem undecidable? Intuitively, it seems that it must be not ...
0 votes
1 answer
302 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 ...
-1 votes
1 answer
51 views

Turing Machine language, Undecidable, reductions

I have exam next week about automata theory, languages and computation. I struggle with reductions (Undecidability). For example for this two problems, and need to check first if the language is ...
3 votes
1 answer
98 views

Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction

Let's say a Language L is NON-semi decidable and undecidable. Let's also take the Halting problem H, which is a semi decidable and undecidable language. Is it possible to reduce L to H in a many-one ...
1 vote
2 answers
100 views

How to prove $\{\langle M\rangle: L(M)=\emptyset\}$ is undecidable?

Consider the language $$E_{T M}=\{\langle M\rangle: L(M)=\emptyset\}.$$ Prove that $E_{T M} \in \text{coRE} \backslash\text{R}.$ I proved that $$E_{T M} \in\text{coRE}$$ using Turing machine I built ...
0 votes
2 answers
92 views

$L =$ { $\langle M \rangle$ | $M$ moves left on at least one input }

Is $L =$ { $\langle M \rangle$ | $M$ moves left on at least one input } decidable? What would the proof look like? Intuitively, I would say it's undecidable: We cannot predict if a given TM ever ...
4 votes
1 answer
8k views

Is it possible that the union of two undecidable languages is decidable?

I'm trying to find two languages, $L_1, L_2 \in RE \setminus R$, such that $L_1 \cup L_2 \in R$. I have already proved that if $L_1\cap L_2 \in R$ and $L_1 \cup L_2 \in R$, such $L_1, L_2$ don't ...
3 votes
1 answer
153 views

A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $...
0 votes
1 answer
194 views

Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
1 vote
1 answer
38 views

Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?

I need to prove if the following Language is or is not semi-decidable. A := {w ∈ {0,1}^* | there exists an input x on which M_w produces the output 0} Where A is the language of all the encoding w ∈ {...
1 vote
1 answer
985 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
2 answers
118 views

Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable

I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows: "By contradiction, assume that $L$ is ...
-2 votes
1 answer
62 views

Is the "intersection" of the special Halting Problem with a language always undecidable?

I'm exploring the decidability characteristics of a particular language formed by the intersection of two languages, specifically in the context of the Halting Problem. The languages are defined as ...
2 votes
1 answer
53 views

Is explicitly explaining the case where the Turing Machine loops forever essential to proving reducibility?

I am asking this in the context of the following question: Let N be a non-deterministic Turing Machine. We say that N faces a dilemma if at some point in its working, it encounters a situation where ...
4 votes
1 answer
129 views

Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps

Let $L$ be a language for which there exists some turing machine deciding it in at most $n^2$ steps. Is it decidable whether a given turing machine $M$ decides $L$ and runs in at most $n^2$ steps? I ...
0 votes
1 answer
45 views

"Term Rewriting and All That" - Exercise 2.3

I am working through the exercises in the book "Term Rewriting and All That" and got stuck on question 2.3. The question reads: find a reduction $\rightarrow$ on $\mathbb{N}$ such that $\...
1 vote
1 answer
45 views

If A U B and A ∩ B are recognizable, then is one of A, A', B, B' also recognizable?

I know that if decidability of $A \cap B$ and $A \cup B$ doesn’t guarantee the decidability of any of $A$ or $B$. We can prove that: ATM is not decidable. Since decidable languages are closed under ...
1 vote
0 answers
40 views

Proof of the halting problem being undecidable

To prove the that the halting problem is undecidable I was provided with 5 lemmas. I understood each Lemma individually and also the proof itself. What I'm confused about is that one of the Lemmas ...
2 votes
2 answers
2k views

Why is a Language L(M) {has at least 10 strings} turing recognizable and L(N) {has at most 10 strings} is not?

Why is a Language L(M) {has at least 10 strings} recognizable and L(N) {has at most 10 strings} is not? ...
0 votes
1 answer
55 views

A program that solves the Halting Problem for programs with N states

My question relates to the conclusions drawn from the Halting Problem. I understand that the Halting Problem proves that no program H(P,i) exists that determines if P(i) halts or not for P in general. ...
0 votes
1 answer
1k 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 ...
1 vote
0 answers
79 views

Help me verify my proof that FINITE is undecidable

Is my proof that FINIT is undecidable correct? FINITE= { ⟨M⟩ | M is a Turing machine that accepts only finitely many strings } is undecidable. Answer: To prove this we can use reduce to Halting ...
6 votes
2 answers
2k views

What does it mean to prove the halting problem is undecidable "using arithmetization"?

In version gamma of the ACM/IEEE/AAAI Computer Science Curricula 2023, on page 50, one of the illustrative learning outcomes for the "Computational Models and Formal Languages" section of ...
0 votes
0 answers
23 views

If we have two TMs D1 and D2 and the languages of the TMs L(D1) != L(D2), then is this problem decidable/recognizable? [duplicate]

We know that in the case where, L(D1) = L(D2), the problem is undecidable. But what happens when the languages are not equal? I would assume it's still undecidable, but is it recognizable? And how ...
-2 votes
2 answers
70 views

Show that the language is undecidable

Consider the language L = {< M >| M accepts iff input length is divisible by 3}. I'm supposed to use reduction to show that the language is undecidable. I tried proving it but didn't know what ...
8 votes
2 answers
523 views

Solving systems of linear equations over semirings

So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm ...
5 votes
7 answers
3k views

What are the conditions necessary for a programming language to have no undefined behavior?

For context, yesterday I posted Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?. Part of what prompted me to ask that question ...
-6 votes
1 answer
65 views

Is ChatGPT wrong about the definition of unrecognizable and undecidable languages?

I asked ChatGPT to give me the difference between unrecognizable and undecidable languages, and this what it gave me: Unrecognizable languages can be accepted by a Turing machine, but the machine may ...
0 votes
3 answers
98 views

Why can't we use computation history to detect looping of a Turing machine on a given input?

First of all, obviously there is a flaw in my logic and I just want to know what it is. So here is my idea: Given a TM M and an input string ω, simulate M on ω on another TM S. For every change of ...
3 votes
1 answer
93 views

Automated Query Equivalence Solver (MongoDB)

The query-equivalence problem is undecidable. However there are theorem provers that attempt to solve instances of undecidable problems. I am curious how I could go about using an automatic theorem ...
0 votes
2 answers
70 views

Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof

all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct? TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
1 vote
1 answer
165 views

What could $P = NP$ imply about arbitrary Turing machines?

My question: What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists ...
3 votes
0 answers
190 views

Does this paper by Patrick Cousot describe an undecidable method for model checking?

All of the discussion is in the context of this paper. I think that the whole procedure that the paper describes is not decidable, because if we can have an algorithm for it, then we can solve halting ...
3 votes
1 answer
686 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 ...
0 votes
1 answer
588 views

TMs can decide whether or not a string is a Palindrome, yet, the language called PALINDROMES is undecidable - why?

I came across this language, where M denotes a Turing Machine: PALINDROMES $:= \{M \mid M \text{ accepts strings which are palindromes}\}.$ It is proven to undecidable. And, I know one can construct a ...
-1 votes
1 answer
81 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 ...
0 votes
1 answer
218 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
0 answers
30 views

$FINITE_{TM}$ is not Turing-reducible to $A_{MT}$

$FINITE_{TM} = \{\langle M \rangle\mid M\text{ is a TM and }L(M)\text{ is finite}\}$ $A_{MT} = \{\langle M,w \rangle \mid M\text{ is a TM and }M\text{ accepts }w\}$ I'm trying to prove that $FINITE_{...
1 vote
1 answer
40 views

Reformulating the Given Conditions in Decidability Problems

I came across the following question: Given two context-free languages $L_1$ and $L_2$ is it decidable whether $L_1 - L_2 = \emptyset$ ? The problem $ALL_{\text{CFG}}$ that states: Given a CFG $G$ ...
1 vote
1 answer
114 views

Is the problem of Proper Subset of decidable languages decidable?

Given 2 recursive - decidable languages $L_1$ and $L_2$ is the problem $L_1 \subset L_2$ solvable - decidable? Since both $L_1$ and $L_2$ are recursive - decidable there exist Turing Machines say $M_1$...
0 votes
0 answers
26 views

Question regarding rice theorem

this is a question I got from a test that we had before Let there be X, a subgroup of languages above $\Sigma $ such that X isn't empty nor all of the langauges in $\Sigma $ we need to say if the ...
0 votes
0 answers
20 views

proving or disproving a reduction from $R \leq P(Σ^*) \backslash RE$

I need to prove or disprove that for all languages in $R$ there is a reduction to all languages in $P(Σ^*)\backslash RE$. And I'm having trouble to figuring out the solution, especially with dealing ...
-9 votes
1 answer
620 views

Are the halting problem proofs refuted by software engineering?

Can D simulated by H terminate normally? The x86utm operating system based on an open source x86 emulator. This system enables one C function to execute another C function in debug step mode. When H ...
-2 votes
2 answers
206 views

Proof: is the language $L_1=\{\langle M\rangle\mid\emptyset \subseteq L(M)\}$ (un)-decidable?

I want to show that $L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\}$ is decidable/undecidable - without rice theorem (just for the case that I can apply it). Every language contain the $\...
0 votes
0 answers
61 views

Undecidability of syntactic properties

Rice's theorem comments on the undesirability of non-trivial semantic properties, however there are syntactic properties that are undecidable as well, such as the "useless" states problem ...
-2 votes
1 answer
81 views

EPSILON(CFG) = {<G,H> | G and H are CFGs where the concatenation is epsilon. is this language Turing-recognizable?

It is given that the language is not decidable. Is this language Turing-recognizable?
0 votes
1 answer
240 views

Modify Turing’s proof of the undecidability of the halting problem

Modify Turing’s proof of the undecidability of the halting problem to show there is no Turing machine P with the following two properties: For all Turing machines M, if M() accepts then P(⟨M⟩) ...

1
2 3 4 5
18