Questions tagged [undecidability]
Questions about problems which cannot be solved by any Turing machine.
849
questions
0
votes
0
answers
20
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?
- 133
0
votes
1
answer
29
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 ...
- 195
0
votes
1
answer
22
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
- 195
0
votes
1
answer
32
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 ...
- 195
1
vote
0
answers
21
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
90
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 ...
- 21
0
votes
2
answers
44
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
40
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
52
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 ...
- 110
1
vote
1
answer
76
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
24
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 ...
- 3
0
votes
1
answer
33
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 ...
- 11
0
votes
0
answers
27
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
89
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
30
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
25
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
42
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 $...
- 105
0
votes
0
answers
95
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
67
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
42
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 ...
2
votes
1
answer
111
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
59
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 ...
- 279
0
votes
1
answer
213
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
87
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$ ...
- 279
2
votes
1
answer
134
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
0
votes
0
answers
20
views
Is it a well-posed question to decide whether a process is deterministic, given that the machine is equipped with a TRNG?
Consider a machine equipped with two input devices: A true random number generator for a fair coin toss, and stdin. I wondered whether it's possible to decide that ...
- 241
2
votes
1
answer
139
views
Turing Machine writes "a" for every input w is undecidable
I have a doubt on my solution of the following:
Formalize the language of a Turing machine that takes a Turing machine "M" and a character "a" as input, the language recognizes all ...
- 121
1
vote
2
answers
116
views
Why is $A_{TM}$ not mapping reducible to $E_{TM}$?
$A_{TM}= \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$
$E_{TM}= \{ \langle M\rangle \mid L(M) = \emptyset \}$
The standard proof for the undecidability of $E_{TM}$ is given in this ...
- 275
2
votes
1
answer
306
views
Disprove: if L is decidable then Prefix(L) is decidable
The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for ...
- 453
1
vote
1
answer
28
views
If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?
I was learning about decidability when I thought of this question: If P is partially decidable, is ¬P decidable, partially decidable or undecidable?
I think it is Undecidable since if ¬P holds then P ...
- 23
1
vote
0
answers
33
views
How to show a language is not recursive, without using reductions?
I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
- 113
1
vote
1
answer
77
views
Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?
An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide ...
- 241
1
vote
1
answer
208
views
Undecidability in optimal data compression
There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course:
I think it is saying finding the optimal size of given data is undecidable. However, I thought there ...
- 163
0
votes
1
answer
137
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
1
vote
1
answer
106
views
Proving Undecidability of this Language
Consider the language
$$L = \{\langle M \rangle \mid \text{$\exists$ an input $x$, where $|x|<i$, such that $M$ halts on $x$, but it takes at least $j$ steps} \}$$ where $i$ and $j$ are fixed non-...
0
votes
1
answer
45
views
If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable
I should prove or give a counterexample to the above statement.
In my opinion, this statement is false but I don't manage to find the right counterexample.
My idea was to define $C = Σ^*$ because $Σ^*$...
- 217
-2
votes
1
answer
159
views
Halting problem. Decider “recognising itself” in the input? Part 2
This is a "revision" of this question, it contained an error I now see. In a nutshell, I was wondering if in the halting problem proof the decider $D$, after recognising its source code in ...
1
vote
1
answer
300
views
For any two languages A and B there exists J such that both A and B are Turing reducible to J
Here is the my attempt:
Proof : Suppose $J = \{aa' \mid a \in A\} \cup \{bb' \mid b \in B\}$ such that $a'$ and $b'$ are the symbols that do not belong to any $w \in A \cup B$ and $a,b$ are strings.
...
- 173
1
vote
1
answer
747
views
Prove that Turing Machine ever writes a blank symbol over a non blank symbol is undecidable
I have been given the following problem from the book Introduction to the Theory of Computation by Martin Sipser and was wondering if my solution is correct: Determine if a Turing Machine ever writes ...
- 181
4
votes
2
answers
691
views
How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?
I have been given the following problem and was wondering if my solution is correct: Say that a variable $A$ in CFG $G$ is necessary if it appears in every derivation of some string $w$ where $w$ is ...
- 181
2
votes
1
answer
538
views
Prove it is undecidable that a Turing machine accepts at least one input w in space $|w|^2$
This question is part of the undecidable lecture by Jeff Erickson.
$$\{\langle M\rangle\mid M \text{ accepts at least one string }w\text{ in space }|w|^2\}$$
We should prove that this language is ...
- 21
1
vote
1
answer
174
views
Prove $H2 = \{\langle M\rangle : M$ accepts all inputs in $\{0, 1\}^∗$ whose length is at most $2\}$ is undecidable but recognizable
Yet another question from an exe. in the Computability class taught by Z. Luria -
I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable?
I mean we ...
- 217
0
votes
2
answers
59
views
Post Correspondence Problem is undecidable
I am reading Introduction to the Theory of Computation by Michael Sipser and I am in chapter 5. It says here that the Post Correspondence Problem is undecidable, but thinking about it, given a ...
- 13
0
votes
1
answer
45
views
Turing recognizability and Reduction Mapping on pairs of related Turing machines
I am interested in computation and I am lost on undecidability and reductions. I have the following two problems I am stuck on.
Let us call 2 Turing machines related if there
is an input $w$ on which ...
1
vote
1
answer
160
views
Prove Language Is Undeciable Using Diagonalization
I was given the following problem and told it has to be solved using diagonalization. However, I am confused as to why diagonalization would be the solution. Would the answer not be since L is ...
- 11
-2
votes
1
answer
39
views
Decision problem
Prove the following theorem
Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P.
Could anyone be able to prove it?
- 11
1
vote
1
answer
64
views
Why is the language containing the Turing machines which only accept their own encoding not applicable to the diagonalization proof?
I saw this question and asked myself why the original problem is not solvable through diagonalization. Let
$$L = \bigl\{\langle M \rangle \mid L(M) = \{\langle M\rangle\}\bigr\}$$
Take the complement $...
- 13
0
votes
1
answer
65
views
Decidability of a given grammar if it is regular
According to my course the question "Is $L(G)$ regular?" undecidable. But I was more interested in knowing the exact algorithm or proof that makes this question undecidable. To further ...
