Questions tagged [undecidability]
Questions about problems which cannot be solved by any Turing machine.
871
questions
1
vote
0
answers
35
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 ...
- 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 ...
- 61
0
votes
0
answers
22
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 ...
0
votes
1
answer
48
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. ...
-1
votes
2
answers
49
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 ...
- 1
-6
votes
1
answer
55
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 ...
- 11
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 ...
0
votes
3
answers
91
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 ...
- 11
0
votes
2
answers
61
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
1
vote
1
answer
163
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 ...
- 11
3
votes
0
answers
185
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 ...
- 31
0
votes
1
answer
411
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 ...
0
votes
0
answers
26
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
39
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$ ...
- 165
0
votes
0
answers
46
views
Is the $Even - Halt$ problem decidable?
Is the language:
$$L = \{\ \langle M \rangle \ |\text{ There is an input $w$ such that M performs even number of steps before M halts on $w$} \}$$
They way I approached the problem the was the ...
1
vote
1
answer
84
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$...
- 165
0
votes
0
answers
23
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
39
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 ...
- 27
0
votes
0
answers
19
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 ...
- 1
0
votes
0
answers
47
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
60
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
225
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⟩) ...
- 25
0
votes
1
answer
43
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 ...
- 103
0
votes
0
answers
28
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?
- 141
0
votes
1
answer
168
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 ...
- 305
0
votes
1
answer
46
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
- 305
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 ...
- 305
1
vote
0
answers
24
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\...
- 141
2
votes
2
answers
120
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 ...
- 23
0
votes
2
answers
82
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 ...
- 163
0
votes
1
answer
63
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 ...
- 3
1
vote
2
answers
68
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 ...
- 108
1
vote
1
answer
111
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(\...
- 15
0
votes
0
answers
63
views
How to prove by reduction this (acceptance?) problem
At school I was assigned this example:
Prove by the reduction method that it is undecidable whether for a given Turing machine M with the alphabet {a, b, _} holds aabb ∈ L(M).
I think it's acceptance ...
- 1
0
votes
1
answer
53
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 ...
- 21
0
votes
0
answers
29
views
Recursive language sandwiched between two non-RE languages
I need to find three languages $L_1,L_2,L_3$ that satisfy:
$L_1 \subseteq L_2 \subseteq L_3$.
$L_1,L_3 \notin RE$.
$L_2 \in R$.
I can't think of any other language that is not RE, except for $$L_d = ...
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 ...
0
votes
1
answer
233
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 ...
- 103
0
votes
1
answer
54
views
Show that Lu is m-reducible to the language L = {⟨M, x⟩ | M(x) terminates with an empty tape}
Question: Given a language L, L = {⟨M, x⟩ | M(x) terminates with an empty tape}, show that Lu is m-reducible to L by finding a computable function f: Σ* -> Σ*, where for every w, w ∈ Lu if and only ...
- 1
0
votes
0
answers
39
views
Prove that a language does not many one reduce to its complement
I am trying to prove that an undecidable language $L$ is not many one reducible to its complement.
The problem goes as follows:
Formally prove that $L \not\leq_m \overline{L}$ for any undecidable $L$....
- 1
10
votes
4
answers
2k
views
Probabilistic methods for undecidable problem
An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic ...
- 219
0
votes
1
answer
53
views
Infinite loops and the computability of mapping reductions
Consider the reduction $A_{TM} \le_m \overline{E}_{TM}$, where
$$A_{TM} = \{\langle M, w \rangle \mid \text{TM $M$ accepts $w$}\}\text{, and}$$
$$\overline{E}_{TM} = \{\langle M \rangle \mid \text{TM $...
- 117
0
votes
0
answers
113
views
proof that halting problem is undecidable
In the book Formal languages and automata by Peter Linz, 4th edition (Jones & Bartlett Learning), on pages 300-301,
there is a proof for the fact that the halting problem is undecidable.
The proof ...
- 89
1
vote
1
answer
81
views
Is it computable to find the cardinality of intersection of two recursively enumerable sets?
I am well aware that recursively enumerable sets (which are subsets of $\mathbb N$) are closed under intersection. What is more interesting is whether or not the cardinality of the intersection is ...
- 121
1
vote
1
answer
47
views
Comparing source code and compiled code for ("topological") equivalence
Assume that I have a program Login.c that I have compiled with cc and generated the executable ...
- 1,006
2
votes
1
answer
133
views
proof of non Turing-computable function g
In one of my lessons about turing machines I have been taught that the function g is not computable:
\begin{cases}g(n)=f_{n}(n)+1 & \text { if } f_{n}(n) \text { is defined } \\ g(n)=1 & \text ...
- 89
1
vote
1
answer
169
views
prove that there does not exist a Turing machine with a particular property
Prove that there does not exist a Turing machine M such that for every Turing machine K that halts on all inputs, $M$ accepts $\langle K\rangle$ if and only if $L(K)$ is infinite.
The above question ...
- 289
0
votes
1
answer
637
views
Prove that the language of all Turing machines that accept finitely many words is decidable or not
Question: we have the following language:
$$A = \{\langle M \rangle :| L( M)| < \infty \text{ and } M\text{ is a Turing machine}\}$$
where $\langle M\rangle$ is the encoding of $M$ and $L(M)$ is ...
- 5
1
vote
1
answer
125
views
a halting turing machine
Prove that there does not exist a universal Turing machine that takes a pair $\langle M, w\rangle$ as input, where M is a Turing machine and w is a string, and that always halts, accepts if $M$ ...
- 289
2
votes
1
answer
261
views
Showing that a property is semantic - Rice's theorem
I want to show that the language
$$L= \left\{ \left\langle M\right\rangle \mid\substack{\text{M is a TM and there exists a poly TM $M'$ such that}\\
\text{if M halts on input $w$, $M'$ halts on $w$ ...
- 161