THE MATHEMATICS OF COMPUTING BETWEEN LOGIC AND PHYSICS
30 pages
English

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

THE MATHEMATICS OF COMPUTING BETWEEN LOGIC AND PHYSICS

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
30 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Supérieur, Doctorat, Bac+8
THE MATHEMATICS OF COMPUTING BETWEEN LOGIC AND PHYSICS GIUSEPPE LONGO AND THIERRY PAUL Abstract. Do physical processes compute? And what is a computation? These questions have gained a revival of interest in recent years, due to new technologies in physics, new ideas in computer sciences (for example quantum computing, networks, non-deterministic algorithms) and new concepts in logic. In this paper we examine a few directions, as well as the problems they bring to the surface. Contents 1. Introduction 2 2. Computability and continuity 3 3. Mathematical computability and the reality of physics 7 4. From the principle of least action to the quantum theory of fields 9 5. Chaotic determinism and predictability 10 6. Return to computability in mathematics 15 7. Non-determinism? 17 8. The case of quantum mechanics 21 9. Randomness, between unpredictability and chaos 23 10. General conclusions 25 References 28 Departement d'Informatique UMR 8548 et CNRS, Departement de Mathematiques et Applications.UMR 8553 et CNRS, paul@ dma.ens.fr Ecole Normale Superieure, 45, rue d'Ulm - F 75730 Paris Cedex 05 . In “Computability in Context: Computation and Logic in the Real World”, (Cooper, Sorbi eds) Imperial College Press/World Scientific, 2010. This is a largely expanded version of a previous paper in French in the proceedings of the LIGC colloquium, Cerisy, (Joinet et al.

  • natural

  • real numbers

  • church's thesis

  • computing between

  • quantum situation

  • topology over

  • numbers equivalent


Sujets

Informations

Publié par
Nombre de lectures 13
Langue English

Extrait

THEMATHEMATICSOFCOMPUTINGBETWEENLOGICANDPHYSICSGIUSEPPELONGOANDTHIERRYPAULAbstract.Dophysicalprocessescompute?Andwhatisacomputation?Thesequestionshavegainedarevivalofinterestinrecentyears,duetonewtechnologiesinphysics,newideasincomputersciences(forexamplequantumcomputing,networks,non-deterministicalgorithms)andnewconceptsinlogic.Inthispaperweexamineafewdirections,aswellastheproblemstheybringtothesurface.Contents1.Introduction22.Computabilityandcontinuity33.Mathematicalcomputabilityandtherealityofphysics74.Fromtheprincipleofleastactiontothequantumtheoryofelds95.Chaoticdeterminismandpredictability106.Returntocomputabilityinmathematics157.Non-determinism?178.Thecaseofquantummechanics219.Randomness,betweenunpredictabilityandchaos2310.Generalconclusions25References28De´partementd’InformatiqueUMR8548etCNRS,http://www.di.ens.fr/users/longo/;De´partementdeMathe´matiquesetApplications.UMR8553etCNRS,paul@dma.ens.frE´coleNormaleSupe´rieure,45,ruedUlm-F75730ParisCedex05.In“ComputabilityinContext:ComputationandLogicintheRealWorld”,(Cooper,Sorbieds)ImperialCollegePress/WorldScientific,2010.ThisisalargelyexpandedversionofapreviouspaperinFrenchintheproceedingsoftheLIGCcolloquium,Cerisy,(Joinetetal.,eds),Hermann,2009(seehttp://www-philo.univ-paris1.fr/Joinet/ligc.html).1
2G.LONGOANDT.PAUL1.IntroductionDigitalmachines,bytheirextraordinarylogicalandcomputationalcapa-bility,arechangingtheworld.Theyarechangingitwiththeirpowerandtheiroriginality,butalsowiththeimageoftheworldtheyreflect:theyhelpperformthousandsoftasksandenableradicallynewones,theyareanindispensabletoolforscientificresearch,buttheyalsoprojecttheirownmathematicalstructureupontheprocessestheyareinvolvedin.Theaimofthispaperistopresentseveralsituations(inanon-exhaustiveandratherkaleidoscopicway)whereapreciseconfrontationofdigitalcapac-itieswithrealsettingsinnaturalsciencesispossible,and,inparticular,toshowhow,inthesesituations,thecomputerscience’sconceptofcomputabil-ityhastobecarefullyhandledandsometimesnotpertinent.Digitalmachinesarenotneutral,astheyhaveacomplexhistory,basedonseveralturningpointsintermsofthethinkingwhichenabledtoinventthem.Theysynthesizeavisionandasciencewhichisveryprofound.Theyare“alphabetic”inthespecificsenseoftheencodingofhumanlanguage,producedbyabagpipeoverstrings,bymeansofdiscreteandmeaninglessletter-units,anincredibleinventionwhichdatesback5,000years.TheyareCartesianintheirsoftware/hardwaredualityandintheirreductionofthoughttotheelementaryandsimplestepsofarithmeticcalculus.Theyarelogicalbystemmingfromalogico-arithmeticalframework,inthetraditionofFregeandHilbert,duringthe30s(“proofsareprograms”).Andthisbythefinalremarkableinvention,byGo¨del:thenumber-theoreticencodingofanyalphabeticwriting.Forallofthesereasons,theycontributetoareadingofnaturebasedonthecomputablediscrete,fromthealphabettoarithmetic,onaspace-timeframedwithindiscretetopology,ofwhichtheaccessandthemeasurementareexact,justlikeindigitaldatabases.Wewillseewhyconfoundingphysics,despiteitsgreat“mathematicity”,withcomputationsandcalculus,inanyformwhatsoever,seemsasamistaketous.First,theideathatphysics“reducestosolving”equationsisaner-roneousidea.Tobeassuredofthis,oneneedsonlytoconsiderthatagreatpartofphysicsconcernsvariationalproblemsinwhichthesearchofageo-desicdiffersgreatlyfromthesearchforthesolutiontoanequation.Andthis,withoutmentioningthesingularquantumsituation,tobediscussedbelow,northelifesciences,whicharenotverymathematizedandforwhichthenotionsofinvariantandofthetransformationwhichpreservesit,centraltomathematics,arefarfrombeing“stabilized”.Thenewimportanceofdigitalmachines,inparticularinthenaturalsci-ences,requiresathoroughanalysisoftherelationshipbetweencomputations
COMPUTINGBETWEENLOGICANDPHYSICS3andnaturalprocesses.Wewillfocushereontherelationshipsbetweencom-putationsand,amongthephysicalprocesses,thosewhichweconsideras“natural”,thatis,thosethatoccursomehow“independently”ofhumanin-tervention(becauseamachinealsoproduces,orevenis,aphysicalprocess,butitisaresultofahumanconstructionwhichisextremelyoriginalandtheoreticallyrich).Wewillthenaskthequestion:Dophysicalprocessescompute?Thepaperisorganizedasfollows:Section2isdevotedtoatopologicaldis-cussionofthelinkbetweencomputabilityandcontinuity.ItleadstoSection3wheremathematics,especiallycomputationalmathematics,isconfrontedtophysicsendowedwithitspeculiar“reality”property.Weshowinpartic-ularhowphysicsdealswithalotofconceptswhichescapefromanysenseof“calculus”.Section4givesanepistemologicalexampleofamathematicalob-jectwhich,withtheevolutionofphysics,lostitscomputationalflavourafterenteringthegameofmodernphysics.Sections5,6,7and8aresomewhatthecoreofthepaper.Wefirstdiscusstheconceptofpredictabilityinthemirrorofchaoticityindynamicalsystems.Thenwecomebacktotopologicalremarksandconsidertheproblemofdeterminism,afashionablesubjectincomputersciencesnowadays.Wethenlookatthecaseofquantummechan-ics,alsoasubjectwhichenteredstronglycomputerscienceslately.Section9discussesthepositionofrandomnessinsidedynamicalsystems,andweendupwithsomefinalremarks.Letusmentiononceagainthatthescopeofthispaperisbynomeantopresentageneraltheoryofnon-adequacyofcomputersciencesinnaturalphilosophy,butrathertopresentwarningsconcerningageneraltemptationofoverusingcomputationalideasinphysicsandmathematics,giventhemajorroleofcomputingintoday’sscience.2.ComputabilityandcontinuityThenaive,andunfortunatelyhighlywidespreadresponsetothequestionaboveisthatyes,everythingcanbeseenintermsofalphanumericinforma-tionanditscomputationalelaboration.Thisthesis,underdifferentforms,isoftencalledthe“PhysicalChurchThesis”.Solet’sreturnbrieflytoChurch’sthesisinitsoriginalform,whichispurelylogico-mathematicalandinnowayphysical.Church’sthesis,introducedinthe30safterthefunctionalequivalenceproofsofvariousformalsystemsforcomputability(andconcerningonlycom-putabilityoverintegers),isanextremelyrobustthesis:itensuresthatany
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents