Could someone prove they had a halting oracle?

computational-complexity

Solution 1:

It's clear that you cannot possibly hope for more than a probabilistic result -- any testing procedure that can pass a true halting oracle after asking it $n$ questions will also pass a random oracle with probability at least $2^{-n}$.

But I much doubt that you can get even a probabilistic guarantee. Suppose that the purported oracle was in reality a proof-search oracle that answers correctly when the program can be proved (in some fixed but unknown formal system) to either terminate or diverge, and otherwise answers "Halts". In order to conclude that this is not a true halting oracle, we would need to ask it about something that diverges, but unprovably so. We could ask it to search for a proof of an undecidable Gödel sentence, but since the formal system the fake oracle uses is unknown, it could just have added a finite number of Gödel sentences to its static knowledge.

Related

A question about the tensor product of $\mathbb{Q}$
The Math behind rotation puzzles?
Any compact embedded $2$-dimensional hypersurface in $\mathbb R^3$ has a point of positive Gaussian curvature
Solving systems of linear equations when matrix of coefficients is singular
Practical Use of Series Expansion at $x=\infty$
Deriving the Area of a Sector of an Ellipse
Understanding the Zariski topology on $\mathbb{R}$
$\epsilon{\rm -}\delta$ proof of the discontinuity of Dirichlet's function
Riemann's thinking on symmetrizing the zeta functional equation
Distribution of the maximum of a multivariate normal random variable
Can we extend the definition of a homomorphism to binary relations?
Computing the integrals of the form $\exp(P(x))$, $P(x)$ a polynomial