Hypercomputer

A “hy­per­com­puter” is an imag­i­nary ar­ti­fact re­quired to an­swer some crisp ques­tion that can’t be an­swered in the limit of ar­bi­trar­ily large finite com­put­ers. For ex­am­ple, if you have a ques­tion that de­pends on a gen­eral solu­tion to the Halt­ing Prob­lem, then we say that to solve this prob­lem re­quires a “hy­per­com­puter”, and in par­tic­u­lar, a level-1 halt­ing or­a­cle. (If you need to de­ter­mine whether pro­grams on level-1 halt­ing or­a­cles halt, you need a level-2 halt­ing or­a­cle, which we would also call a “hy­per­com­puter”.)

It seems ex­cep­tion­ally un­likely that hy­per­com­put­ers will ever be dis­cov­ered to be em­bed­ded into our phys­i­cal uni­verse. The term “hy­per­com­puter” just ex­ists as a la­bel so we can say, “Sup­pos­ing we had a hy­per­com­puter and ran this (im­pos­si­ble) pro­gram, what would be the con­se­quences?”

For some ex­am­ples of con­cep­tu­ally illu­mi­nat­ing code that would re­quire a hy­per­com­puter to ac­tu­ally run, see Solomonoff in­duc­tion and AIXI.

Un­bounded anal­y­sis of agents some­times in­vokes hy­per­com­put­ers be­cause this lets us talk about mul­ti­ple agents with easy-to-de­scribe knowl­edge re­la­tions to each other. For ex­am­ple, we might talk about Agent X that uses Zer­melo-Fraenkel set the­ory as a proof sys­tem and has a \(\Pi_n\) or­a­cle, and an­other Agent Y that uses Peano Arith­metic and has a \(\Pi_{n+1}\) or­a­cle, to en­code a set of re­la­tions where Y can di­rectly pre­dict and model X, and X can do proofs about Y. For ex­am­ple, we might talk about Agent X that uses a weak hy­per­com­puter and a strong proof sys­tem, and Agent Y that has a strong hy­per­com­puter and a weak proof sys­tem, to de­scribe a sce­nario where Y can di­rectly pre­dict and model X, and X can do proofs about Y. In these cases, we’re not try­ing to say that the re­la­tion be­tween agents X and Y in­trin­si­cally re­quires them to have im­pos­si­ble pow­ers of com­pu­ta­tion. We’re just reach­ing for an un­phys­i­cal sce­nario that hap­pens to crisply en­code in­ter-agent re­la­tions we find in­ter­est­ing for some rea­son, and al­lows these in­ter-agent re­la­tions to have con­se­quences about which we can eas­ily do proofs.

See also the Wikipe­dia page on hy­per­com­pu­ta­tion.

Parents:

  • Methodology of unbounded analysis

    What we do and don’t un­der­stand how to do, us­ing un­limited com­put­ing power, is a crit­i­cal dis­tinc­tion and im­por­tant fron­tier.