Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).
Questions tagged [computability]
2395 questions
0
votes
1 answer
Intuition for "identification" and "generalization" (computability theory)
I am trying to decipher page 68 of Hermes' book on computability theory. One paragraph I am having trouble with is
Let $Q$ be an n-ary predicate ($n \geq 2$). Let $1 \leq i < k \leq n$. Then $P$ [a predicate] is called the $(i, k)$…
badatmath
- 4,065
0
votes
0 answers
Question Regarding Subsets of $\mathbb{N}$ with Certain Properties
I have three related questions. The first two are extremely similar. The third one asks a question based on the first two. Let $K$ denote the diagonal halt set. Similarly let $bb:\mathbb{N} \rightarrow \mathbb{N}$ denote the busy beaver function and…
SSequence
- 1,022
0
votes
1 answer
Why isn't the idea of "an oracle for the halting problem" considered self-contradictory?
Doesn't the halting problem's uncomputability mean that if you had an oracle that "computed" it you could derive a contradiction?
Tom Lehman
- 187
0
votes
1 answer
Enumerating all halting programs
In class I was given this problem with solution. I was hoping someone could shed some light on them.
$\underline{Question}$
Is the set K RE (recursively enumerable)?
K = { $i$ | $P_{i}$ halts on input $i$ }
$\underline{Solution}$
For j = 1 to…
0
votes
0 answers
Computability of Inverse Fourier Transform on L^2
Is the inverse Fourier transform on $L^2$ computable? That is,
\begin{align}F^{-1}: &L^2 \rightarrow L^2\\
& f \mapsto \check{f} \end{align} $(\delta_{L^2}, \delta_{L^2})$ computable? Here, we know that $\check{f}(x) = \hat{f}(-x)$ almost…
Poonam
- 11
0
votes
0 answers
What exactly is a delta class?
We've been learning the arithmetical hierarchy, but unfortunately the parts of the textbook used actually did not include the formal definitions of a $\Delta$ class (we are being provided with parts of a pdf). I was wondering if anyone could provide…
layabout
- 748
0
votes
1 answer
Why must language $L$ be decideable?
I am trying to teach myself computability theory with a textbook.
According to my book, a function $f$ over an alphabet $A=\{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\}$ is only computable iff the language
$$
L =…
Minden Petrofsky
- 323
0
votes
1 answer
Counterexample to the uniformization principle for $\Pi^0_1$ relations
Problem: Is it true that for every $\Pi^0_1$ relation $P(e, t) \subseteq \omega\times\omega$ there is a partial recursive function $g \colon \omega \to \omega$ satisfying $(\exists t)P(e, t) \Rightarrow \left(g(e)\!\downarrow\ \&\ P(e,…
Random Jack
- 2,906
0
votes
1 answer
How to show the following problem is undecidable without Rice's theorem?
The problem is '$W_x=\varnothing$'.
If I could reduce '$x\in W_x$' to '$W_x=\varnothing$' by s-m-n theorem and universal function, maybe there would be a solution. I have no idea how to reduce? Can you give me some details?
Marvin
- 151
0
votes
1 answer
Why is not language $L=\{w_i \mid w_{2i} \notin M_i\}$ recursively enumerable?
Why is not language
$$L=\{w_i \mid w_{2i} \notin M_i\}$$
recursively enumerable? I need to show that by diagonalization, but dont know how? Its quite obvious for $L=\{w_i \mid w_i \notin M_i\}$, but for this I dont know how to show that. Thanks a…
Ondra
- 115
0
votes
1 answer
Show that function is primitive recursive.
Having trouble with showing that function is primitive recursive. Have the following problem.
Let $ f: \mathbb{N} \rightarrow \mathbb{N}$ be decreasing function. Show
that $f$ is primitive recursive.
I see that $f$ will eventually decrease to a…
E.K.
- 99
0
votes
1 answer
Decidability or computability in the class P
It is well known that problems in the class P are characterized as those problems that are decidable in polynomial time by means of a deterministic Turing machine. My question is the following: If a decision problem can be decided by a deterministic…
UnclePetros
- 53
0
votes
1 answer
What can we say a language is recursively enumerable if it can be simulated?
For example, consider the language $L$ given by
$$L = \{ M : M \; \textsf{halts on} \; \epsilon \}$$
I understand why this language is not recursive, but how do we prove it is recursively enumerable? I spoke with a friend, and he simply said…
Ralff
- 1,487
0
votes
1 answer
Prove that the set $\{x|\varphi_x \text{is total}\}$ is productive
It's easy to show that the complement $\bar{T}=\{x|\varphi_x \text{is not total}\}$ is productive, since $\bar{K}$ is many-one reducible to it, but what about $T$?
delta-terminator
- 193
0
votes
1 answer
Define the Complement of Factoring?
I just need some clarification as to what this terminology means in this situation.
A decision problem for $FACTORING$ is as follows.
INPUT: an integer $n$ and a integer $d$
QUESTION: does $n$ have a prime factor less than $d$?
How would…
Takkun
- 433