Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
756 views

Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

I'm trying to prove that $L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$. I'm not sure whether to reduce the halting ...
39
votes
2answers
7k 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". ...
5
votes
2answers
196 views

Semi-decidable problems with linear bound

Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a ...
4
votes
2answers
249 views

Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?

From this statement As there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language. I would like to understand why similar reasoning ...
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 \...
25
votes
5answers
11k views

Why isn't this undecidable problem in NP?

Clearly there aren't any undecidable problems in NP. However, according to Wikipedia: NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that ...
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
2answers
808 views

Can we show a language is not computably enumerable by showing there is no verifier for it?

One of the definitions of a computably enumerable (c.e., equivalent to recursively enumerable, equivalent to semidecidable) set is the following: $A \subseteq \Sigma^*$ is c.e. iff there is a ...
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 ...
10
votes
2answers
4k 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}} = \{\...
140
votes
3answers
15k 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}$ ...
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 ...
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 ...
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 ...
20
votes
1answer
495 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 ...
17
votes
4answers
836 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 ...
30
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 ...

1
11 12 13 14
15