Hypercomputer

[summary: 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, we say that to solve this problem requires a "hypercomputer". (In particular, it requires a level-1 halting oracle.)

It seems exceptionally unlikely that hypercomputers will ever be discovered to be embedded into our physical universe. We just use this as a label so we can say, for certain impossible programs, "Supposing we had a hypercomputer and could run this impossible program, what would be the consequences?"

For an example of interesting code that requires a hypercomputer, see Solomonoff induction. The relations between different levels of hypercomputer are also useful for crisply describing agents that have better or worse abilities to predict one another.]

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. [has-requisite(arithmetical_hierarchy): 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.] [!has-requisite(arithmetical_hierarchy): 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.