Questions tagged [undecidability]
Questions about problems which cannot be solved by any Turing machine.
120
questions
45
votes
2answers
19k views
How to show that a function is not computable?
I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
143
votes
3answers
17k views
How can it be decidable whether $\pi$ has some sequence of digits?
We were given the following exercise.
Let
$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$
...
44
votes
2answers
8k views
Perplexed by Rice's theorem
Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time!
Of course, Rice's theorem doesn't simply say "everything is impossible". ...
32
votes
7answers
6k views
Is there a more intuitive proof of the halting problem's undecidability than diagonalization?
I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization.
While the proof is convincing (I understand each step of ...
19
votes
2answers
14k views
Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?
Let $F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$. I need to decide whether F is decidable or recursively enumerable. I think it's decidable, but I don't know how to ...
12
votes
6answers
35k views
Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?
Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$
Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$?
It ...
13
votes
2answers
1k views
Are there any existing problems that wouldn't be solvable with a halting oracle?
I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible ...
6
votes
1answer
6k views
Relationship between Undecidable Problems and Recursively Enumerable languages
I have read the Wikipedia article on Recursively Enumerable languages. The article suggests that the halting problem is recursively enumerable but undecidable. My idea till today was that the halting ...
18
votes
5answers
1k views
Is it possible to solve the halting problem if you have a constrained or a predictable input?
The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case?
For ...
11
votes
1answer
993 views
Reductions among Undecidable Problems
Im sorry if this question has some trivial answer which I am missing. Whenever I study some problem which has been proven undecidable, I observe that the proof relies on a reduction to another problem ...
47
votes
1answer
6k views
What makes type inference for dependent types undecidable?
I have seen it mentioned that dependent type systems are not inferable, but are checkable. I was wondering if there is a simple explanation of why that is so, and whether or not there is there a limit ...
13
votes
3answers
2k views
Is Deciding Decidability Decidable?
I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.
6
votes
1answer
11k views
Is the language of Turing Machines that halt on every input recognizable?
I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
24
votes
4answers
1k views
Do undecidable languages exist in constructivist logic?
Constructivist logic is a system which removes the Law of the Excluded Middle, as well as
Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't ...
31
votes
1answer
2k views
Rice's theorem for non-semantic properties
Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always ...
4
votes
2answers
2k views
Is undecidable(complement of R) a subset of NP-hard?
Is there an undecidable problem which is not NP-hard?
4
votes
1answer
728 views
How to prove the emptiness of intersection of two context free languages is undecidable?
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.
Do you maybe ...
3
votes
3answers
10k views
Is every subset of a decidable set, also decidable?
Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable?
I believe it would be true because all the subsets of B should also be decidable making A decidable. I'...
5
votes
1answer
5k views
Proving ALLTM complement not recognizable
A few definitions..
$$
\begin{align*}
\mathrm{ALL}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) = \{0,1\}^{*} \Bigr\}
\\[2ex]
\...
3
votes
1answer
660 views
Construction of the complement of universal Turing machine - where is the catch?
This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct ...
1
vote
1answer
933 views
Palindromes and linear grammars
Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?
9
votes
3answers
5k views
Are all undecidable/uncomputable problems reducible to the Halting problem? [duplicate]
Theory of computation tells us that there are some languages that cannot be recognized by a Turing machine. That is, there are well-defined problems for which no Turing machines can provide an ...
15
votes
3answers
6k views
Why is the halting problem decidable for LBA?
I have read in Wikipedia and some other texts that
The halting problem is [...] decidable for linear bounded
automata (LBAs) [and] deterministic machines with finite memory.
But earlier it is ...
8
votes
2answers
3k views
How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?
How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?
I have tried to reduce this problem to another undecidable ...
5
votes
3answers
5k views
Testing two DFAs generate the same language by trying all strings upto a certain length
Given the language
$EQ_{\mathrm{dfa}} =$ $\{\langle A, B\rangle\mid A$ and $B$ are two DFAs and $L(A) = L(B)$ $\}$
Prove that $EQ_{\mathrm{dfa}}$ is decidable by testing the two DFAs on all strings ...
10
votes
4answers
5k views
Is there an undecidable finite language of finite words?
Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable?
I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \...
7
votes
1answer
2k views
Is it decidable whether a Turing machine modifies the tape, on a particular input?
Is $L=\{\langle M,w \rangle|M\text{ does not modify the tape on input w}\}$ decidable?
We could tell if a TM does not modify the tape on any input by checking if there are no transitions in $M$ that ...
14
votes
1answer
786 views
Program synthesis, decidability and the halting problem
I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that ...
8
votes
2answers
3k views
Prove REGULAR_TM is undecidable
I am studying the proof of the following theorem:
Given the language
$\mathit{REGULAR}_\mathit{TM} = \{\langle M \rangle | M $ is a turing machine and $\mathit{Accept}(M)$ is regular$\}$
$\mathit{...
8
votes
2answers
262 views
Decidability of Equality of Radical Expressions
Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt[n]{\,\cdot\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, ...
4
votes
1answer
652 views
Undecidability of REGULAR_TM (Detail within Proof)
I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book.
The example shows how $REGULAR_{TM}$, defined as the ...
3
votes
1answer
3k views
Reducing from a Turing machine that recognizes is regular to the halting problem
I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present.
This is the reduction they give:
...
3
votes
1answer
8k views
Can a semi-decidable problem be also decidable?
As far as I understand, a semi-decidable (recursively enumerable) problem could be:
decidable (recursive) or
undecidable (nonrecursively enumerable)
...
3
votes
1answer
494 views
Machines whose languages are their own encoding
Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable?
I tried diagonalization but can only ...
3
votes
1answer
63 views
Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials
Let's have expressions that are composed of elements of $\mathbb N$ and a limited set of binary operations {$+,\times,-,/$} and functions {$\exp, \ln$}. The expressions are always well-formed and form ...
11
votes
2answers
6k views
A Question relating to a Turing Machine with a useless state
OK, so here is a question from a past test in my Theory of Computation class:
A useless state in a TM is one that is never entered on any input string. Let $$\mathrm{USELESS}_{\mathrm{TM}} = \{\...
2
votes
4answers
1k views
Reduction and decidability
Consider the following language: $$ L = \{ \langle M \rangle \ |\ M \text { accepts } w \text { whenever it accepts } w^R \}$$
I am trying to understand the following proof that this language $L$ is ...
1
vote
1answer
2k views
Is it decidable if a TM takes at least 2016 steps on all inputs?
$$L_1= \{\langle M \rangle \mid \text{\(M\) takes at least 2016 steps on all inputs} \}$$
Is this language decidable?
I will write my way of understanding it. Please answer it in the way I ...
0
votes
1answer
1k views
Prove Undecidability: TM M enters each of its states on Input W?
Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$?
How to prove that the problem is undecidable?...
-2
votes
1answer
553 views
Prove that {⟨M,w⟩∣M accepts w only} is unrecognizable [closed]
$$L = \{\langle M,w\rangle \mid \text{\(M\) accepts \(w\) only}\}$$
How can I prove this language is unacceptable (unrecognisable)?
I think I should use a reduction, I'm not sure how.
3
votes
2answers
5k views
Undecidable unary languages (also known as Tally languages)
An exercise that was in a past session is the following:
Prove that there exists an undecidable subset of $\{1\}^*$
This exercise looks very strange to me, because I think that all subsets are ...
1
vote
1answer
219 views
Prove that $H$ reduces to $H\varepsilon$
I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem).
I am very confused how to PROVE it, I mean it is clear that we can ...
1
vote
2answers
107 views
Show that a language is decidable iff some enumerator enumerates the language in decreasing order
Show that a language is decidable iff some enumerator enumerates the
language in decreasing order.
I know a language is decidable iff some enumerator enumerates the language in the standard string ...
1
vote
1answer
962 views
Reducing the infinite language problem to halting problem
Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \} $.
It is easy to show with Rices theorem that $INF$ is not decidable.
($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$).
How ...
1
vote
1answer
909 views
A second question on "Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs" [duplicate]
Let B={M1,M2,...} be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent ...
1
vote
1answer
2k views
Infinite union of recursive languages
I'm trying to figure out how to prove or disprove the following statement:
Infinite union of recursive languages is recursively enumerable.
I know how to prove that infinite union of regular ...
0
votes
1answer
131 views
Turing Machine 'marking' specific portion of encoding
Given a turing machine $T$ that receives an encoding of another turing machine and a word $<M><w>$, can $T$ 'run' through the encoding and 'mark' specific transitions/states?
For example, ...
0
votes
1answer
193 views
Is there an undecidable language that is mapping reducible to its complement?
Is there an undecidable language A that is mapping reducible to its complement?
If it is possible, since A is an undecidable language, so A's complement must also be an undecidable language. But i don'...
-1
votes
1answer
1k views
Complement of halting set is not r.e
suppose we don't know that Halting problem is not recursive.
I want to prove that complement of halting set is not r.e. then we can find halting problem is not recursive.
Can you direct prove that ...
-2
votes
1answer
1k views
Is the set of TMs that accept exactly two strings (each) semi-(decidable)?
I have found this problem-
let A be the set of encoding of all those Turing machines that accept exactly two strings and let A' be the complement of A. Comment on whether A and A' are recursive , ...
