Emergence, Complexity and Computation ECC Andrew Adamatzky Editor Automata, Universality, Computation Tribute to Maurice Margenstern Emergence, Complexity and Computation Volume 12 Serieseditors IvanZelinka,TechnicalUniversityofOstrava,Ostrava,CzechRepublic e-mail:[email protected] AndrewAdamatzky,UniversityoftheWestofEngland,Bristol,UnitedKingdom e-mail:[email protected] GuanrongChen,CityUniversityofHongKong,HongKong e-mail:[email protected] EditorialBoard AjithAbraham,MirLabs,USA AnaLuciaC.Bazzan,UniversidadeFederaldoRioGrandedoSul,PortoAlegre RSBrasil JuanC.Burguillo,UniversityofVigo,Spain SergejCˇelikovský,AcademyofSciencesoftheCzechRepublic,CzechRepublic MohammedChadli,UniversityofJulesVerne,France EmilioCorchado,UniversityofSalamanca,Spain DonaldDavendra,TechnicalUniversityofOstrava,CzechRepublic AndrewIlachinski,CenterforNavalAnalyses,USA JouniLampinen,UniversityofVaasa,Finland MartinMiddendorf,UniversityofLeipzig,Germany EdwardOtt,UniversityofMaryland,USA LinqiangPan,HuazhongUniversityofScienceandTechnology,Wuhan,China GheorghePa˘un,RomanianAcademy,Bucharest,Romania HendrikRichter,HTWKLeipzigUniversityofAppliedSciences,Germany JuanA.Rodriguez-Aguilar,IIIA-CSIC,Spain OttoRössler,InstituteofPhysicalandTheoreticalChemistry,Tübingen,Germany VaclavSnasel,TechnicalUniversityofOstrava,CzechRepublic IvoVondrák,TechnicalUniversityofOstrava,CzechRepublic HectorZenil,KarolinskaInstitute,Sweden AboutthisSeries The Emergence,Complexityand Computation(ECC) series publishesnew devel- opments,advancementsandselectedtopicsinthefieldsofcomplexity,computation andemergence.Theseriesfocusesonallaspectsofreality-basedcomputationap- proachesfromaninterdisciplinarypointofviewespeciallyfromappliedsciences, biology, physics, or Chemistry. It presents new ideas and interdisciplinary insight onthe mutualintersectionofsubareasofcomputation,complexityandemergence anditsimpactandlimitstoanycomputingbasedonphysicallimits(thermodynamic and quantumlimits, Bremermann’slimit, Seth Lloyd limits...) as well as algorith- mic limits (Gödel’s proof and its impact on calculation, algorithmic complexity, theChaitin’sOmeganumberandKolmogorovcomplexity,non-traditionalcalcula- tionslike Turingmachineprocessand its consequences,...)and limitationsarising inartificialintelligencefield.Thetopicsare(butnotlimitedto)membranecomput- ing,DNAcomputing,immunecomputing,quantumcomputing,swarmcomputing, analogic computing,chaos computingand computingon the edge of chaos, com- putationalaspectsofdynamicsofcomplexsystems(systemswithself-organization, multiagentsystems,cellularautomata,artificiallife,...),emergenceofcomplexsys- temsanditscomputationalaspects,andagentbasedcomputation.Themainaimof thisseries itto discussthe abovementionedtopicsfroman interdisciplinarypoint ofviewandpresentnewideascomingfrommutualintersectionofclassicalaswell asmodernmethodsofcomputation.Withinthescopeoftheseriesaremonographs, lecture notes, selected contributionsfrom specialized conferencesand workshops, specialcontributionfrominternationalexperts. Moreinformationaboutthisseriesathttp://www.springer.com/series/10624 Andrew Adamatzky Editor Automata, Universality, Computation Tribute to Maurice Margenstern ABC Editor AndrewAdamatzky UnconventionalComputingCentre UniversityoftheWestofEngland Bristol UnitedKingdom ISSN2194-7287 ISSN2194-7295 (electronic) Emergence,ComplexityandComputation ISBN978-3-319-09038-2 ISBN978-3-319-09039-9 (eBook) DOI10.1007/978-3-319-09039-9 LibraryofCongressControlNumber:2014945747 SpringerChamHeidelbergNewYorkDordrechtLondon (cid:2)c SpringerInternationalPublishingSwitzerland2015 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade. Printedonacid-freepaper [SpringerInternationalPublishingAGSwitzerland]ispartofSpringerScience+BusinessMedia (www.springer.com) Preface A Tribute to MauriceMargenstern A few figures witness Maurice Margenstern’s scientific accomplishments. He au- thored or co-authored 210 papers (some more being on the way...). His 54 co-authors are from all over the world: France, Belgium, Switzerland, Germany, Austria,Italy,Spain,Ireland,UnitedKingdom,Finland,Hungary,Moldavia,Roma- nia,Russia,Israel,China,Malaysia,Japan,Chili,USA.Besideshisresearchpapers, he wrote 6 books, organizedand edited the proceedingsof 8 internationalconfer- ences,supervised5students. And,mostimportantly,hepioneerednewareasofresearchattheintersectionof mathematicsandcomputerscience. HowdidMauricebecomethescientistwesomuchappreciate? Maurice was bornin Parison June 6, 1947.After highschoolhe was accepted in prestigious French “grandes e´coles”. Resigning from the E´cole Polytechnique he entered the E´cole Normale Supe´rieure de Cachan. After he passed the French “agre´gation de mathe´matiques”, he got an academic position at the mathematics departmentoftheUniversityofParis-Sud(Orsay)in1970. Attractedbyconstructivemathematics,thenaverymarginalsubjectinFrance,he wentintheearly70’stoLeningradtostudywithNicola¨ıA.Shanin,thentheheadof the famousRussian schoolin constructivemathematicsfoundedby A.A. Markov. This is where he worked on his thesis on Constructive topological properties of spacesofalmostperiodicfunctions. Thenhisscientificinclinationsgraduallymovedfromconstructivemathematics tocomputability,asubjectthenmuchrevivedafterMatijasevich’sfamousresulton Hilbert’s 10thproblem.In the late 80’s he joined the computerscience laboratory LITP (now LIAFA) in Paris and started his amazing investigation of the simplest (resp.mostcomplex)machineswithanundecidable(resp.decidable)haltingprob- lem.DespitethepreviousworksbyYuriRogogineinMoldaviaandLudmilaPavlot- skaia in Russia, this topic was then rather confidential. Maurice is to be credited forputtingitupasoneoftheimportantthemesincomputability.Hedidsoviahis VI Preface owncontributionsandviaatriennialinternationalconferenceMachines,Computa- tionsandUniversality hesetupin 1995andwhichstill goeson.Irememberhow Josef Gruska (speaking as the last chairman of the first conference,held in Paris) stressedhowmuchenergyMauricehadtoshowinordertocreatefromscratchsuch asuccessfulinternationalevent. MauricepassedhisHabilitationin1994“Studyofthefrontierbetweendecidabil- ity and undecidability of the halting problem of small or constrained Turing ma- chines.”Hewasthenappointedasaprofessorincomputersciencebytheuniversity ofLorraineatMetz.TherehecreatedtheLITAlaboratoryandspentmuchenergy tomakeitasolidresearchcenter.Someyearsago,hewaspromoted“professeurde classeexceptionnelle”,thehighestrankinFrenchAcademia. In the early 2000’s Maurice developed the subject of computation with cellu- lar automata in the hyperbolic world (dimension 2, 3 or 4) and broughtsolutions tolongopendifficulttilingproblems.Besidesthese technicalachievements,Mau- rice provedthathyperboliccomputabilityallowsto overcomeknownunfeasibility resultsoftheEuclideanworld. The classical tool in hyperbolic geometry is the theory of groups but Maurice invented completely new tools: combinatorial ones. As is usual with new ideas, expertsin hyperbolicgeometryshowed reluctancetowardssuch an innovativeap- proach and it was a real relief for Maurice when Donald Knuth wrote to him to expressthathefoundthese newtools“quitefascinating”andwillrefertothemin theArtofComputerProgramming. Ofcourse,thetwothemespresentedabovedonotexhaustthesubjectsMaurice investigatedbuttheywitnesshiscreativetalentandimpressiveenergy. MauricerecentlyretiredandisnowemeritusprofessorattheuniversityofLor- raine.Havingnomoretoteachandmanagearesearchteam,Mauricesimplyspends moretimetocontinueproducingprominentworks. Having had the privilege to know him since the mid 70’s, it is my pleasure to say,inthenameofallcontributorsofthisvolume:Maurice,thankyouforwhatyou haveaccomplishedandlet’scontinueourfriendshipandscientificcollaboration. SergeGrigorieff Paris Contents 1 TheCommonStructureoftheCurvesHaving aSameGaussWord ........................................... 1 BrunoCourcelle 1.1 Introduction............................................. 1 1.2 Definitions.............................................. 4 1.3 AtomsofGraphsandMaps................................ 10 1.4 Planart-Graphsandt-Maps................................ 17 1.5 CurvesinthePlane....................................... 20 1.6 SomeOpenQuestions .................................... 35 References.................................................... 36 Appendix..................................................... 37 2 LogicalTheoryoftheAdditiveMonoidofSubsetsofNatural Integers...................................................... 39 ChristianChoffrut,SergeGrigorieff 2.1 Introduction............................................. 39 2.2 Preliminaries............................................ 41 2.3 UsingSubmonoidstoApproximateandEmulate .............. 48 2.4 ComplexityoftheTheory ................................. 58 2.5 NonDefinablePredicates.................................. 60 2.6 LogicalDefinabilityin(cid:2)P(N);+,=(cid:3) ........................ 68 2.7 RemarkableDefinableSetsandClasses...................... 69 2.8 Conclusion.............................................. 73 References.................................................... 73 3 SomeReflectionsonMathematicsandItsRelationtoComputer Science....................................................... 75 LiesbethDeMol 3.1 MathematicalLogic,theComputerandMathematics .......... 76 3.2 ANumber-Theorist’sPointofView......................... 80 VIII Contents 3.3 The Impact of the Computer on Mathematics: Some QuantitativeResults ...................................... 83 3.4 Computer-AssistedExplorativeMathematics:Characteristics andProblems............................................ 86 3.5 Some(NewandOpen)Problems ........................... 90 3.6 SomeAfterthoughts ...................................... 98 References.................................................... 99 4 SamplingaTwo-WayFiniteAutomaton ......................... 103 ZheDang,OscarH.Ibarra,QinLi 4.1 IntroductionandMotivation ............................... 103 4.2 InformationDependencyandInformationFlowin2NFAs ...... 105 4.3 LanguagePropertiesofSampledRunsofSomeTwo-Way Infinite-StateAutomata ................................... 112 4.4 Conclusions............................................. 114 References.................................................... 114 5 Maurice Margenstern’sContributionsto the Field ofSmall UniversalTuringMachines..................................... 117 TurloughNeary,DamienWoods 5.1 Introduction............................................. 117 5.2 SimulatingtheCollatzFunctionwithSmallTuringMachines ... 118 5.3 FrontiersbetweenUniversalityandNon-universality........... 120 5.4 RestrictedTuringMachines................................ 121 References.................................................... 124 6 ConstructingReversibleTuringMachinesbyReversibleLogic ElementwithMemory......................................... 127 KenichiMorita 6.1 Introduction............................................. 127 6.2 ReversibleLogicElementwithMemory(RLEM) ............. 128 6.3 RelationtoPhysicalReversibility........................... 130 6.4 ConstructingReversibleTuringMachinesbyRotaryElement ... 132 6.5 ConcludingRemarks ..................................... 137 References.................................................... 137 7 TheGrossoneMethodologyPerspectiveonTuringMachines....... 139 YaroslavD.Sergeyev,AlfredoGarro 7.1 Introduction............................................. 139 7.2 TuringMachines......................................... 141 7.3 TheGrossoneLanguageandMethodology ................... 147 7.4 ObservingTuringMachinesthroughtheLensoftheGrossone Methodology............................................ 153 7.5 ConcludingRemarks ..................................... 165 References.................................................... 167 Contents IX 8 OnParallelArrayPSystems ................................... 171 LinqiangPan,GheorghePa˘un 8.1 Introduction............................................. 171 8.2 DefinitionsandNotations ................................. 172 8.3 ParallelArrayPSystems .................................. 173 8.4 Results ................................................. 175 8.5 ConcludingRemarks ..................................... 180 References.................................................... 181 9 SmallPSystemsDefiningNon-semilinearSets.................... 183 ArtiomAlhazov,RudolfFreund 9.1 Introduction............................................. 183 9.2 Definitions.............................................. 185 9.3 AcceptingPSystems ..................................... 193 9.4 GeneratingbyDoublingintheMaximallyParallelMode ....... 195 9.5 AsynchronousandSequentialPsystems ..................... 202 9.6 PSystemswithCatalysts.................................. 203 9.7 Conclusions............................................. 215 References.................................................... 216 10 GeneralizedCommunicatingPAutomata........................ 219 Erzse´betCsuhaj-Varju´,Gyo¨rgyVaszil 10.1 Introduction............................................. 219 10.2 PreliminariesandDefinitions .............................. 220 10.3 ThePowerofPAutomatawithGeneralizedCommunication.... 226 10.4 Conclusions............................................. 235 References.................................................... 235 11 ComputationalModelsBasedonSplicing ........................ 237 YuriiRogozhin,SergeyVerlan 11.1 Introduction............................................. 237 11.2 SplicingOperationandHSystems .......................... 238 11.3 ControlledSplicing....................................... 241 11.4 DistributedSplicing ...................................... 248 11.5 RefiningtheControl...................................... 253 11.6 Conclusions............................................. 255 References.................................................... 256 12 LinearCellularAutomataandDecidability ...................... 259 KlausSutner 12.1 LinearCellularAutomata ................................. 259 12.2 TheFirst-OrderTheory ................................... 262 12.3 UndecidabilityandHardness............................... 269 12.4 Summary ............................................... 273 References.................................................... 274