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.WhilethisdefinitiondoesnotfitintothetraditionalChomsky2

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.

Toestablishthisresultconcerningpredictionofthefuturethispaperconsidersamodelof4

computationwhichisactuallygeneralenoughtoaddresstheperformanceofothercomputational

tasksaswellaspredictionofthefuture.Inparticular,thisresultdoesnotrelyontemporalorder-

ingsofevents,andthereforealsoestablishesthatnocomputercaninfalliblypredictthepast(i.e.,

performretrodiction).Soanymemorysystemmustbefallible;thesecondlawcannotbeusedto

ensureperfectlyfaultlessmemoryofthepast.Accordingly,thepsychologicalarrowoftimeisnot

inviolate[24].1Theresultsarealsogeneralenoughtoallowarbitrarycouplingofthecomputer

andtheexternaluniverse.Soforexampletheyalsoestablishthattherecannotbeadevicethatcan

takethespecificationofanycharacteristicoftheexternaluniverseasinputandthencorrectly

observethevalueofthatcharacteristic.Similarly,theyestablishthatherecannotbeadevicethat

cantakethespecificationofanydesiredvalueofacharacteristicoftheexternaluniverseasinput

andtheninducethatvalueinthatcharacteristic.Inotherwords,looselyspeaking,therecannotbe

eitheraninfalliblegeneralpurposecontroldevicenoraninfalliblegeneralpurposecontroldevice.

(Thissecondinterpretationcanbeviewedasanuncertaintyprinciplethatdoesnotinvolvequan-

tum mechanics.)

Thereareanumberofpreviousresultsintheliteraturerelatedtotheseresultsofthispaper.

ManyauthorshaveshownhowtoconstructTuringMachinesoutofphysicalsystems(seefor

example[10,22]andreferencestherein).Bytheusualuncomputabilityresults,thereareproper-

tiesofsuchsystemsthatcannotbecalculatedonaphysicalTuringmachinewithinafixedallot-

mentoftime(assumingeachstepinthecalculationtakesafixednon-infinitesimaltime).In

addition,therehavebeenanumberofresultsexplicitlyshowinghowtoconstructphysicalsys-

temswhosefuturestateisnon-computable,withoutgoingthroughtheintermediatestepofestab-

lishing computational universality [13, 23].

Thereareseveralimportantrespectsinwhichtheresultsofthispaperextendthisprevious

work.Allofthesepreviousresultsrelyoninfinitiesofsomesortinphysicallyunrealizablesys-

tems(e.g.,in[23]aninfinitenumberofstepsareneededtoconstructthephysicalsystemwhose

futurestateisnotcomputable).Inaddition,theyallassumeone’scomputingdeviceisnomore

powerfulthanaTuringmachine.Alsononeofthemaremotivatedbyscenarioswherethecompu-