Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
-4 votes
0 answers
64 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 } ...
kauray's user avatar
  • 511
1 vote
1 answer
67 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
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 ...
rus9384's user avatar
  • 1,600
-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 ...
David's user avatar
  • 11
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 ...
Dilara's user avatar
  • 11
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 ...
Just Curious's user avatar
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 ∈ {...
sergio ospina's user avatar
-2 votes
1 answer
63 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
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 ...
sergio ospina's user avatar
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 ...
Aditya 's user avatar
  • 123
4 votes
1 answer
130 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
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 ...
Steven's user avatar
  • 11
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 ...
Luis Ramirez's user avatar
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 $\...
Ruben Hensen's user avatar
2 votes
2 answers
119 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
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 ...
Sachihiro's user avatar
  • 111
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
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. ...
Vincenzo Buselli's user avatar
-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 ...
berlin23's user avatar
-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 ...
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
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 ...
Aland Ameer's user avatar
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 ...
boinka's user avatar
  • 1
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 ...
Flowy Poosh's user avatar
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 ...
Senmorta's user avatar
0 votes
1 answer
592 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
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_{...
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
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$...
RookieCookie's user avatar
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 ...
elay dadnon's user avatar
1 vote
2 answers
102 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
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 ...
yoav's user avatar
  • 1
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 ...
Alan Whitteaker's user avatar
-2 votes
1 answer
82 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
241 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
44 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
0 votes
1 answer
237 views

If a language is undecidable, then its complementary language must also be undecidable?

Reference from here If a Language is Non-Recognizable then what about its complement? There exist complementary languages of unrecognizable languages that are recognizable, and there exist ...
lz9866's user avatar
  • 315
0 votes
1 answer
52 views

Unrecognizable languages must be undecidable?

A decidable language must be recognizable. Unrecognizable languages must be undecidable? I want to know more about the relation of undecidability and unrecognizability
lz9866's user avatar
  • 315
0 votes
1 answer
34 views

If the complementary language of an recognizable language is a non-recognizable language, is the recognizable language a non-decidable language?

The complementary language of a recognizable undecidable language is not recognizable. If the complementary language of an recognizable language is a non-recognizable language, is the recognizable ...
lz9866's user avatar
  • 315
2 votes
0 answers
28 views

Reduction from $\mathsf{ALL}_{\mathsf{TM}}$ to it's complement

I'd like to know if there's a reduction $\mathsf{ALL}_{\mathsf{TM}}\leq_{m}\overline{\mathsf{ALL}_{\mathsf{TM}}}$ where of course $\mathsf{ALL}_{\mathsf{TM}}=\left\{ \left\langle M\right\rangle \mid\...
Ariel Yael's user avatar
2 votes
2 answers
126 views

Proving that there is no solution to the PCP problem using induction

I'm studying for the Algorithms and Computability course. I have encountered a problem that I cannot solve and cannot find any materials to help me solve it. It's the following PCP problem: We have ...
Miszka's user avatar
  • 23
1 vote
2 answers
99 views

Decidability of the minimum number of states a Turing Machine needs to accept a language

I'm reading some old notes from a course on Turing Machines and I've bumped into the following question: Is the following language decidable? The language formed by the set of all Turing Machines ...
user2891462's user avatar
0 votes
1 answer
80 views

Decidable or Not: Set of all Turing Machines M that on input w uses all states of M

Show that the following language or problem is not recursive: $$ L=\{\langle M,w\rangle\mid \text{computation of TM } M \text{ on input } w \text{ uses all states of } M\} $$ I was trying to prove it ...
enouema's user avatar
1 vote
2 answers
74 views

What machines are required to solve the emptiness of regular and context-free langauges?

Consider the language definition: $L = \{<M>| M$ is a DFA and $M$ accepts some string of the form $ww^{r}$ for some $w\in \Sigma^{*}\}$ The language $L$ is : A) Regular B) Context-free but not ...
Arun Madhav's user avatar
1 vote
1 answer
124 views

Is the equivalence problem of a CFG and a FSM decidable?

I have the following problem: Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\{0, 1\}$. Is it decidable whether $L(\...
sockaddr's user avatar
0 votes
1 answer
62 views

What characteristics would a PDA $A$ where $L(A)=\Sigma^*$ have?

I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's ...
Gabe Kelly's user avatar
0 votes
5 answers
2k views

Does contradiction definitively prove nonexistence

It is common to have proofs that use contradiction to show that some language is undecidable in computability theory. An example proof can be seen in 4.2 Undecidability “Introduction to the Theory of ...
Dereference's user avatar
0 votes
1 answer
399 views

Is the infinite union of decidable languages decidable?

I am currently struggling with figuring out the following problem: Given decidable languages L1, L2, L3, L4, ... Is the infinite union of Languages L1, ...... decidable? I have an intution that it is ...
Druckermann's user avatar

1
2 3 4 5
18