Hypercomputer

A “hypercomputer” is an imaginary artifact required to answer some crisp question that can’t be answered in the limit of arbitrarily large finite computers. For example, if you have a question that depends on a general solution to the Halting Problem, then we say that to solve this problem requires a “hypercomputer”, and in particular, a level-1 halting oracle. (If you need to determine whether programs on level-1 halting oracles halt, you need a level-2 halting oracle, which we would also call a “hypercomputer”.)

It seems exceptionally unlikely that hypercomputers will ever be discovered to be embedded into our physical universe. The term “hypercomputer” just exists as a label so we can say, “Supposing we had a hypercomputer and ran this (impossible) program, what would be the consequences?”

For some examples of conceptually illuminating code that would require a hypercomputer to actually run, see Solomonoff induction and AIXI.

Unbounded analysis of agents sometimes invokes hypercomputers because this lets us talk about multiple agents with easy-to-describe knowledge relations to each other. For example, we might talk about Agent X that uses Zermelo-Fraenkel set theory as a proof system and has a \(\Pi_n\) oracle, and another Agent Y that uses Peano Arithmetic and has a \(\Pi_{n+1}\) oracle, to encode a set of relations where Y can directly predict and model X, and X can do proofs about Y. For example, we might talk about Agent X that uses a weak hypercomputer and a strong proof system, and Agent Y that has a strong hypercomputer and a weak proof system, to describe a scenario where Y can directly predict and model X, and X can do proofs about Y. In these cases, we’re not trying to say that the relation between agents X and Y intrinsically requires them to have impossible powers of computation. We’re just reaching for an unphysical scenario that happens to crisply encode inter-agent relations we find interesting for some reason, and allows these inter-agent relations to have consequences about which we can easily do proofs.