New answers tagged computability
2
First of all, the place for this question is cs.se, not here. But since I've already written an answer, I'll leave it.
There is a formal definition of computability: a function $f$ is computable if there is a Turing machine that, given input $x$, always halts with $f(x)$ written on its tape.
You could of course define more general computability, which uses ...
0
Choose P arbitrarily (since question asks this for all P). Wouldn't constructing $H(H(P))$ already include assumption that $H(P)$ as input to $H$ has source code or other representation that can be tested for termination? If that is true, then $H(P)$ by assumption contains an implementation of solution to the halting problem for $P$, therefore executing that ...
3
The short version of this answer is:
Degree theory (e.g. the study of the first-order theory of the partial order of Turing degrees) yields examples of non-relativizing statements, although these statements are of course highly technical. One useful tool for understanding this situation is the cone theorem ... which also limits the extent to which this ...
1
Such an $H$ would let us solve the halting problem:
We begin by running $H(H(P))$ until it halts (which it does by assumption on $H$).
If the output of $H(H(P))$ is "doesn't halt," then we know $H(P)$ doesn't halt, and so by assumption on $H$ we know that $P$ doesn't halt.
If the output of $H(H(P))$ is "halts," then we subsequently run $H(P)$ until it ...
Top 50 recent answers are included
