New answers tagged halting-problem
1
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 ...
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
