New answers tagged

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