Questions tagged [undecidability]
Questions about problems which cannot be solved by any Turing machine.
115
questions
20
votes
1answer
503 views
Ratio of decidable problems
Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested ...
asked Mar 9 '12 at 12:54
Gilles 'SO- stop being evil'
39.9k7 gold badges106 silver badges171 bronze badges
14
votes
2answers
7k views
Is it decidable whether a TM reaches some position on the tape?
I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$.
For an integer $c>1$, and the following three problems:
...
10
votes
2answers
1k views
Halting problem without self-reference
In the halting problem, we are interested if there is a Turing machine $T$ that can tell whether a given Turing machine $M$ halts or not on a given input $i$. Usually, the proof starts assuming such a ...
9
votes
2answers
2k views
For any language $A$, there is $B$ such that $A \le _T B$ but $B \nleq _T A$
I am trying to come up with a proof for the following:
For any language $A$, there exists a language $B$ such that $A \le_{\mathrm{T}} B$ but B $\nleq_{\mathrm{T}} A$.
I was thinking of letting $B$...
9
votes
5answers
20k views
How to tell if a language is recognizable, co-recognizable or decidable?
If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable?
Basically any hints or tricks that can be used to tell. Or maybe the ...
4
votes
1answer
5k views
Can you recognize or decide if a Turing Machine has an infinite sized language?
That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language?
...
23
votes
2answers
1k views
Is there a “natural” undecidable language?
Is there any "natural" language which is undecidable?
by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the ...
10
votes
6answers
553 views
Undecidable problems limit physical theories
Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual ...
14
votes
3answers
2k views
undecidable problem and its negation is undecidable
A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement.
However, ...
12
votes
2answers
3k views
Are all context-sensitive languages decidable?
I was going through the Wikipedia definition of context-sensitive language and I found this:
Each category of languages is a proper subset of the category directly above it. Any automaton and any ...
10
votes
4answers
3k views
The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?
One statement of Rice's theorem is given on page 35 of "Computational Complexity: a Modern Approach" (Arora-Barak):
A partial function from $\{0,1\}^*$ to $\{0,1\}^*$ is a function that is not ...
9
votes
2answers
8k views
Is it decidable whether a given context free grammar generates an infinite number of strings?
Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
9
votes
4answers
3k views
Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?
On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets. This question is somewhat different.
It asks whether ...
8
votes
2answers
249 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
4answers
1k views
What approaches are most useful when proving uncomputability of a given function?
I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows:
Reduction,...
4
votes
2answers
687 views
Why is the language of TMs that have some quadratic time bound undecidable?
The language in question is $L = \{M : M \text{ is a Turing machine that halts in } 100n^2 + 200 \text{ time}\}$.
Attempt 1
Suppose $L$ is decidable. Let $M_1, M_2, \ldots$ be the Turing machines in ...
4
votes
1answer
261 views
Decide whether there exists a walk of weight exactly k
Consider the following problem:
Input: a directed graph $G = (V,E,\omega)$ where $\omega : E \longrightarrow \mathbb{Z}$, two vertices $v_1, v_2 \in V$, and a weight $k \in \mathbb{Z}$
Question: ...
3
votes
2answers
1k views
Is it possible to ever define $L(M)$ of a given Turing Machine, $M$?
In class, we were discussing creating a Turing Machine $M$ based on the set of input strings it should accept, i.e. define a Turing Machine that accepts only the input $\{ w\ \#\ w\ |\ w \in \{0,1\}^*\...
3
votes
2answers
4k views
Decidability of whether a language described by Turing machine is regular
I am trying to prove decidability of problem whether language described by Turing machine is regular. My idea is that I can simulate finite automaton with a subset of Turing machine instructions, ...
3
votes
1answer
961 views
Which properties of context sensitive languages are decidable?
There are two context-sensitive languages, $L_1$ and $L_2$. Which of the following statements about them are decidable respectively undecidable?
$L_1 = \emptyset$
$L_1 = \Sigma^*$
$L_1 \cap L_2 = \...
3
votes
1answer
53 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 ...
1
vote
0answers
67 views
Notable decidable operations on context-sensitive languages [closed]
It is not always so easy to determine which basic questions on languages are (un)decidable. Also due to Rice's theorem, many nontrivial questions on languages are undecidable.
What are notable or ...
1
vote
1answer
1k views
which of the following languages are Recursively Enumerable?
Which of the following languages are recursively enumerable?
A={⟨M⟩∣ TM M accepts at most 2 distinct inputs}
B={⟨M⟩∣ TM M accepts more than 2 distinct inputs}
For first language I think that we can ...
1
vote
2answers
238 views
Is the below language Non R.E?
$L_0=\{\langle M,w,0\rangle\mid M \text{ halts on } w\}$
$L_1=\{⟨M,w,1⟩\mid M \text{ does not halts on } w\}$
Here $\langle M,w,i \rangle$ is a triplet, whose first component $M$ is an encoding of a ...
1
vote
2answers
2k views
Do all decidable problems lie in the class NP?
All decision problems (i.e.language membership problems), which are verifiable in polynomial time by a deterministic Turing machine are called NP problems. Further, these problems can be solved by a ...
0
votes
2answers
1k views
Is P decidable?
It seems correct that any single given algorithm must either have polynomial runtime or not. Is there a specific algorithm that (does or does not actually lie in $P$, but) can neither be proven nor ...
15
votes
5answers
2k views
Are there undecidable properties of non-turing-complete automata?
Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability).
I would like to get ...
11
votes
3answers
589 views
Is it possible to decide if a given algorithm is asymptotically optimal?
Is there an algorithm for the following problem:
Given a Turing machine $M_1$ that decides a language $L$,
Is there a Turing machine $M_2$ deciding $L$ such that
$t_2(n) = o(t_1(n))$?
The ...
8
votes
4answers
859 views
Implications of Rice's theorem
Every time I think I get what Rice's theorem means, I find a counterexample to confuse myself. Maybe someone can tell me where I'm thinking wrong.
Lets take some non-trivial property of the set of ...
5
votes
1answer
1k views
BSS-model Computational complexity of finding the roots of a polyomial
I'm currently dealing with a problem for which I could show that an exact algorithm would imply a general algorithm for finding the real (but not complex) roots of an arbitrary univariate polynomial ...
3
votes
1answer
193 views
The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages
Can the following two statistics be bounded:
the proportion of halting programs vs non-halting programs
the proportion of decidable vs undecidable languages
For example, can we say that one class is ...
2
votes
1answer
436 views
Is converting an ambiguous grammar to an unambiguous grammar computable?
Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).
2
votes
1answer
518 views
If $L$ is recursive then so is $L^*$, and vice versa
Given a language $L$ over the alphabet $\{0,1\}$. Let $L^*= \{ w_1w_2...w_n | n \ge 0, w_1,...,w_n \in L\}$.
Prove:
If $L$ is recursive, then $L^*$ is recursive as well.
If $L^*$ is recursive, then $...
2
votes
2answers
736 views
Is the halting problem decidable by an “infinite Turing machine”?
It has been shown of course that the halting problem is undecidable. That is, we cannot formulate a Turing machine that will decide for any arbitrary turing machine whether it will halt or not.
...
0
votes
1answer
81 views
Given three languages L1 L2 L3 that do not intirsect could one be TR and the other TD and the third neither
where $L_{1} \cup L_{2} \cup L_{3} = \sum^{*}$ and
$L_{1} \cap L_{2} = \emptyset$ and $L_{2} \cap L_{3} = \emptyset$ and $L_{1} \cap L_{3} = \emptyset$
is it possible that $L_{1}$ is decidable, $L_{...
0
votes
2answers
5k views
ETM Undecidability
I'm having trouble convincing myself of the proof for the following theorem:
$E_{TM} = \{\langle M\rangle\mid M$ is a TM and $L(M) = \emptyset\}$ is undecidable.
I think I understand why we reduce $...
17
votes
4answers
893 views
Is this finite graph problem decidable? What factors make a problem decidable?
I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is ...
12
votes
4answers
3k views
Operations under which the class of undecidable languages isn't closed
Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable ...
9
votes
2answers
2k views
Decidability of prefix language
At the midterm there was a variant of the following question:
For a decidable $L$ define $$\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}$$
Show that $\text{Pref}(L)$ is not ...
6
votes
1answer
3k views
Is it possible to prove EQTM is undecidable by the Rice theorem?
Given the problem $EQ_{TM} = \{ \langle M_1, M_2\rangle \mid M_1 \text{ and } M_2 \text{ are } TM, L_{M_1} = L_{M_2}\}$, is it possible to prove that this is undecidable by using (a variant of) Rice ...
5
votes
1answer
3k views
Examples of undecidable problems whose intersection is decidable
I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the ...
4
votes
2answers
320 views
Intuition about decidability
Given a language, how do you go about deciding if it's decidable or not? For example:
Given a DFA $A_0$ and a TM $M_0$
$L_1 = \{ \langle M \rangle \, | \, M \mbox{ is a TM and }L(M) = L(A_0) \}$
$...
3
votes
1answer
432 views
Show that a language is RE or recursive
Consider these 2 languages:
$L_{\ge5} = \left \{ \left< M \right> : M \text{ accepts at least 5 strings} \right\} $
$L_{<5} = \left \{ \left< M \right> : M \text{ accepts fewer ...
2
votes
1answer
5k views
Use Rice's theorem to show that the language of optimisable Turing machines is undecidable
I have an assignment to do and I'm quite stuck with the following question :
Use Rice's theorem to show that
$ \qquad L' = \{ \langle M \rangle \mid \; (\exists \text{ TM } M') \; [ L(M') = L(M) \...
2
votes
2answers
188 views
Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable
How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable?
Intuitively speaking I think it is indeed undecidable because ...
2
votes
1answer
743 views
Is there any undecidable language that is countable?
All we know is that if a language is countable than it must be recognizable. However, a recognizable language may or may not be decidable.
2
votes
1answer
258 views
What is the meaning of undecidability in Rice Theorem?
Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable?
As an example the following language is ...
2
votes
1answer
233 views
Halting problem for fixed Turing machine and fixed input
It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.
What if we fixed both the machine and the input? I.e., is it decidable for every ...
2
votes
1answer
705 views
computability - decidability of a prefix language
For any language $L$ over $\{0,1\}^*$, a language $L'$ can be defined as $\{ a | ab \in L \text{ for some } b \in \{0,1\}^* \}$.
If $L$ is decidable, is $L'$ decidable?
I think that $L'$ should be ...
2
votes
1answer
38 views
Can an alphabet be extended in a reduction proof? (with sample problem)
So I am working on solving a problem on whether following language is decideable:
$L = \{n \in \mathbb{N} \mid M_n$ never freezes (for any input)$\}$, where $n$ is the Gödel-number of a Turing ...
