Skip to main content

Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
57 views

If Halting is not recursive, then why is it that not every set of the form $\{M: \text{M is a Turing machine that does XXX}\}$ is not recursive?

Suppose I wish to find out whether $\{M: \text{M is a Turing machine that does XXX}\}$ is recursive, where $XXX$ can be anything about the Turing machine. I have a bad proof that proves that all such ...
Kindness's user avatar
1 vote
1 answer
30 views

What is the difference between $ L_e$ and $E_{TM} $?

What is the difference between $L_e = \{ \langle M \rangle | L(M) = \emptyset \}$ and $E_{TM} = \{ \langle M \rangle | \text{M is a turing machine and L(M)} = \emptyset \}$? $L_e$ is not RE and $E_{...
Cesare's user avatar
  • 11
3 votes
4 answers
428 views

Undecidable problems in finite graphs

Are there any natural questions in finite graphs (or digraphs) that are undecidable?
Lisa E.'s user avatar
  • 369
0 votes
1 answer
36 views

Using reducibility to prove a language that accepts $\lambda$ and either loops or accepts other strings is undecidable

I am new to the reduction style of proof so I am hoping to get some help on this problem. Let $L=\{〈M〉:M$ accepts the empty string and does not reject any string$\}$. Prove $L$ is undecidable. My ...
hitchens's user avatar
1 vote
2 answers
60 views

Gödel's theorem and machines' power

I was studying AI and when a question came to my mind. I know that one of the objections to the possibility of a thinking machine examined by Turing is the so called mathematical objection, ...
Amanda Wealth's user avatar
0 votes
0 answers
21 views

Issues in the proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$

I'm studying reducidability in Sipser Book and watching his videos, but I couldn't fully understand his proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$ (p. 218, 3rd ed). Consider this extract: M1 = “...
user169972's user avatar
0 votes
0 answers
20 views

PCP is undecidable, but seems also NP [duplicate]

I've seen the proof that the Post Correspondence Problem is undecidable -- let's call this the problem of taking a finite collection of tiles with top and bottom labeled by any two strings, and ...
Addem's user avatar
  • 367
1 vote
2 answers
42 views

Reduce the problem of CFGs with equal languages to the problem of CFGs generating a palindrome

Consider the problem of, given two CFGs $G_1$ and $G_2$, deciding whether they accept the same language, $L(G_1)=L(G_2)$. Call this problem $EQ_{CFG}$. Also consider the problem of deciding whether a ...
Addem's user avatar
  • 367
0 votes
1 answer
38 views

Decide if some DFA is accepted

Given Some(DFA) = {|A is a DFA and L(A) is not empty and L(A) is not equal to Σ^(*)} Show Some(DFA) is decidable. I produced the following answer and wanted to check if I am correct T="On input ...
keth's user avatar
  • 1
2 votes
1 answer
32 views

Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

If $G$ is a CFG, is it decidable whether $L(G)=\Sigma^+=\Sigma^*\setminus\{\epsilon\}$? I have no idea which in direction to go. I feel like it is undecidable, but can't seem to find any proof. I ...
PranksterSabeleye's user avatar
7 votes
1 answer
115 views

Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?

Let $L$ be a language over an alphabet $\Sigma$ and let $$ \text{MIN}(L) = \{ w \in L \mid \forall x,y \in \Sigma^* : (w = xy \land x \in L) \implies y = \varepsilon \} $$ $$ \text{MAX}(L) = \{ w \in ...
JimmyB's user avatar
  • 213
0 votes
1 answer
33 views

A decision procedure for PCP

I have read that the Post Correspondence Problem is undecidable. Let's say this is the problem of having a finite set of "dominoes" with a string in the top and another string on the bottom....
Addem's user avatar
  • 367
0 votes
1 answer
59 views

If a language L over a finite alphabet A has both a subset and superset that are Turing-recognizable, does this make L Turing-Recognizable too?

"Let A be a finite alphabet, and let L1 and L2 be two Turing-recognisable languages over A such that L1 is a proper subset of L2, i.e. L1 ⊂ L2 but L1 ≠ L2. Let a language L over the alphabet A ...
Mark's user avatar
  • 1
2 votes
1 answer
114 views

Is matching pairs sufficient?

Book PDF: https://vishub.org/officedocs/13770.pdf Pg 253 of book This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is ...
PranksterSabeleye's user avatar
5 votes
1 answer
328 views

Is every non-recursively-enumerable language RE-hard?

Is every language $L \notin RE$ is $RE$-hard? Similarly, is every language $L \notin RE \cup coRE$ is $RE$-hard and $coRE$-hard? It seems like a simple question but I can't find an answer. I tried to ...
Amit Keinan's user avatar
4 votes
1 answer
126 views

Is the Turing machine the only framework to analyse limits of computation?

In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this ...
math boy's user avatar
  • 359
1 vote
1 answer
85 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 ...
Sanyo Mn's user avatar
  • 195
0 votes
1 answer
38 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 ...
rus9384's user avatar
  • 1,684
-1 votes
1 answer
59 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 ...
David's user avatar
  • 11
0 votes
2 answers
111 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 ...
Dilara's user avatar
  • 11
1 vote
1 answer
38 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 ...
Just Curious's user avatar
1 vote
1 answer
43 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 ∈ {...
sergio ospina's user avatar
-2 votes
1 answer
71 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 ...
Just Curious's user avatar
3 votes
1 answer
114 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 ...
sergio ospina's user avatar
2 votes
1 answer
55 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 ...
Aditya 's user avatar
  • 123
4 votes
1 answer
197 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 ...
Emolga's user avatar
  • 223
1 vote
0 answers
43 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 ...
Steven's user avatar
  • 11
1 vote
1 answer
58 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 ...
Luis Ramirez's user avatar
0 votes
1 answer
53 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 $\...
Ruben Hensen's user avatar
2 votes
2 answers
342 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 ...
codeing_monkey's user avatar
2 votes
0 answers
180 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 ...
Sachihiro's user avatar
  • 121
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 ...
user164282's user avatar
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 ...
Luis Ramirez's user avatar
0 votes
1 answer
69 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. ...
Vincenzo Buselli's user avatar
-2 votes
2 answers
80 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 ...
berlin23's user avatar
-6 votes
1 answer
73 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 ...
Aland Ameer's user avatar
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 ...
Mikayla Eckel Cifrese's user avatar
0 votes
3 answers
121 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 ...
Aland Ameer's user avatar
0 votes
2 answers
76 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 ...
boinka's user avatar
  • 1
1 vote
1 answer
172 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 ...
Flowy Poosh's user avatar
3 votes
0 answers
192 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 ...
Senmorta's user avatar
0 votes
1 answer
784 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 ...
HaferFlockenPengu's user avatar
1 vote
1 answer
56 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_{...
Laurus Laurus's user avatar
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$ ...
RookieCookie's user avatar
1 vote
1 answer
141 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$...
RookieCookie's user avatar
1 vote
2 answers
106 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 ...
user1701057's user avatar
-2 votes
1 answer
112 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?
Tomer Mor's user avatar
0 votes
1 answer
246 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⟩) ...
staz6's user avatar
  • 25
1 vote
1 answer
48 views

Is there a maximal set of programs that terminate?

It seems useful to characterize terminating programs. While trying to formulate that as a well-defined question I was wondering about the following problem: Is there a maximal decidable set of ...
timgo's user avatar
  • 113
0 votes
0 answers
30 views

How can decidability/semi-decidability/undecidability have impact on REAL life applications/examples?

How decidability/semi-decidability/undecidability has impact on REAL life applications/examples? I understand that it can be used for implementation of various algorithms but what else?
Arthemoon's user avatar
  • 141

1
2 3 4 5
18