1 ON THE COMPUTATIONAL CAPABILITIES OF PHYSICAL SYSTEMS PART I THE IMPOSSIBILITY OF INFALLI

1
ON THE COMPUTATIONAL CAPABILITIES OF PHYSICAL SYSTEMS
PART I: THE IMPOSSIBILITY OF INFALLIBLE COMPUTATION

by David H. Wolpert
NASA Ames Research Center, N269-1, Moffett Field, CA 94035, dhw@ptolemy.arc.nasa.gov

PACS numbers: 02.10.By, 02.60.Cb, 03.65.Bz
Abstract:Inthisfirstoftwopapers,stronglimitsontheaccuracyofphysicalcomputationare
established.FirstitisproventhattherecannotbeaphysicalcomputerCtowhichonecanpose
anyandallcomputationaltasksconcerningthephysicaluniverse.Nextitisproventhatnophysi-
calcomputerCcancorrectlycarryoutanycomputationaltaskinthesubsetofsuchtasksthatcan
beposedtoC.Thisresultholdswhetherthecomputationaltasksconcernasystemthatisphysi-
callyisolatedfromC,orinsteadconcernasystemthatiscoupledtoC.Asaparticularexample,
thisresultmeansthattherecannotbeaphysicalcomputerthatcan,foranyphysicalsystemexter-
naltothatcomputer,takethespecificationofthatexternalsystem’sstateasinputandthencor-
rectlypredictitsfuturestatebeforethatfuturestateactuallyoccurs;onecannotbuildaphysical
computerthatcanbeassuredofcorrectly“processinginformationfasterthantheuniversedoes”.
Theresultsalsomeanthattherecannotexistaninfallible,general-purposeobservationapparatus,
andthattherecannotbeaninfallible,general-purposecontrolapparatus.Theseresultsdonotrely
onsystemsthatareinfinite,and/ornon-classical,and/orobeychaoticdynamics.Theyalsohold
evenifoneusesaninfinitelyfast,infinitelydensecomputer,withcomputationalpowersgreater
thanthatofaTuringMachine.Thisgeneralityisadirectconsequenceofthefactthatanoveldef-
initionofcomputation—adefinitionof“physicalcomputation”—isneededtoaddressthe
issuesconsideredinthesepapers.WhilethisdefinitiondoesnotfitintothetraditionalChomsky
2
hierarchy,themathematicalstructureandimpossibilityresultsassociatedwithithaveparallelsin
themathematicsoftheChomskyhierarchy.Thesecondinthispairofpaperspresentsaprelimi-
naryexplorationofsomeofthismathematicalstructure,includinginparticularthatofprediction
complexity,whichisa“physicalcomputationanalogue”ofalgorithmicinformationcomplexity.It
isproveninthatsecondpaperthateithertheHamiltonianofouruniverseproscribesacertaintype
ofcomputation,orpredictioncomplexityisunique(unlikealgorithmicinformationcomplexity),
in that there is one and only version of it that can be applicable throughout our universe.
3
INTRODUCTION

Recentlytherehasbeenheightenedinterestintherelationshipbetweenphysicsandcomputa-
tion([1-33]).Thisinterestextendsfarbeyondthetopicofquantumcomputation.Ontheone
hand,physicshasbeenusedtoinvestigatethelimitsoncomputationimposedbyoperatingcom-
putersintherealphysicaluniverse.Conversely,therehasbeenspeculationconcerningthelimits
imposedonthephysicaluniverse(oratleastimposedonourmodelsofthephysicaluniverse)by
the need for the universe to process information, as computers do.
Toinvestigatethissecondissueonewouldliketoknowwhatfundamentaldistinctions,ifany,
therearebetweenthephysicaluniverseandaphysicalcomputer.Toaddressthisissuethisfirstof
apairofpapersbeginsbyestablishingthattheuniversecannotcontainacomputertowhichone
canposeanyarbitrarycomputationaltask.Accordingly,thispapergoesontoconsidercomputer-
indexedsubsetsofcomputationaltasks,whereallthemembersofanysuchsubsetcanbeposedto
theassociatedcomputer.Itthenprovesthatonecannotbuildacomputerthatcan“processinfor-
mationfasterthantheuniverse”.Moreprecisely,itisshownthatonecannotbuildacomputerthat
can,foranyphysicalsystem,correctlypredictanyaspectofthatsystem’sfuturestatebeforethat
futurestateactuallyoccurs.Thisistrueevenifthepredictionproblemisrestrictedtobefromthe
set of computational tasks that can be posed to the computer.
Thisasymmetryincomputationalspeedsconstitutesafundamentaldistinctionbetweenthe
universeandthesetofallphysicalcomputers.Itsexistencecastsaninterestinglightontheideas
ofFredkin,Landauerandothersconcerningwhethertheuniverse“is”acomputer,whetherthere
are“information-processingrestrictions”onthelawsofphysics,etc.[10,19].Inacertainsense,
theuniverseismorepowerfulthananyinformation-processingsystemconstructedwithinitcould
be.Thisresultcanalternativelybeviewedasarestrictionontheuniverseasawhole—theuni-
versecannotsupporttheexistencewithinitofacomputerthatcanprocessinformationasfastasit
can.
Toestablishthisresultconcerningpredictionofthefuturethispaperconsidersamodelof