Torben Mogensen header

Turing og Penrose

Titlen refererer til følgende begreber:

  1. Turingkomplet: En turingkomplet maskine er en maskine, der kan lave alle beregninger, som det er muligt for en computer at lave. Det kaldes også en "universel maskine". Se http://en.wikipedia.org/wiki/Turing_complete

  2. Penrose tiling: En dækning af det uendelige plan med fliser, som ikke kan lægges periodisk. En sådan dækning er altså ikke-periodisk. Se http://en.wikipedia.org/wiki/Penrose_tiling

Vi bruger endvidere begrebet

  1. Cellulær automat: Et netværk af felter i 1D eller 2D, hvor hvert felt har en heltallig tilstand, og hvor alle felter samtidigt skifter tilstand baseret på egen tilstand og nabofelternes tilstand. Et velkendt eksempel er Conways "Game of Life". Se http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

Man har længe vidst, at cellulære automater kan være universelle maskiner: Der er lavet konstruktioner for både lineære 1D automater og 2D-automater med kvadratiske felter. F.eks. er det bevist, at Conways oprindelige regler til Game of Life giver en universel maskine ved at konstruere en Turingmaskine i Game of Life. Man har også vist, at der findes reversible cellulære automater (dvs. cellulære automater, hvor hver uendelig konfiguration kun har en mulig forfader), der er universelle for reversible beregninger ved at konstruere en reversibel Turingmaskine. Da en reversible Turingmaskine kan simulere en almindelig (irreversibel) Turingmaskine ved at producere ekstra "garbage" output sammen med Turingmaskinens output, er disse reversible automater også universelle.

Man har også i en del år studeret cellulære automater på Penrose tilings: Selv om de er ikke-periodiske, er der kun endeligt mange mulige lokale naboområder for en givet flise. Så man kan for hvert muligt naboområde definere en tilstandsfunktion, der bestemmer den nye tilstand for midterflisen baseret på tilstandende i naboområdet. I den oprindelige "kite-and-dart" Penrose tiling, er der med hjørnenaboer kun fire forskellige naboområder til en kite og fire forskellige naboområder til en dart. Da der maksimalt er 10 naboer, kan man f.eks. generalisere Conways regel (som bruger summen af de otte naboer i sin tilstandsfunktion) til en, der bruger summen af de otte til ti naboer til sin tilstandsfunktion.

Der har længe været kendt stabile og periodiske konfigurationer på selv simple cellulære automater på Penrose tilings, men det er straks vanskeligere at definere noget, der svarer til gliders: Konfigurationer, der efter et antal tidsskrift gentager sig selv forskudt i forhold til udgangspunktet. Da Penrose tilings er ikke-periodiske, kan man ikke have en fast forskydning, og det komplicerer sagen.

Men i den seneste tid er der ikke alene fundet gliders i en cellulær automat på en Penrose tiling: http://www.newscientist.com/article/dn22134-first-gliders-navigate-everc..., det er også lykkes for nogle japanere at simulere en reversibel Turingmaskine med en cellulær automat på en "kite-and-dart" Penrose tiling: http://arxiv.org/abs/1208.2771

Dermed er det bevist, at cellulære automater på Penrose tiles kan være universelle. Der er næppe nogen praktiske anvendelser af dette resultat, men det siger noget om, at universalitet kan findes på steder, hvor man dårligt tror det muligt. Og så er det også et ret skægt resultat.

Kommentarer (3)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Troels Henriksen

En kompliceret opdatering af den gamle Game of Life-glider som hackersymbol.

PS: Jeg kender ikke nogen anvendt dansk oversættelse af "glider", men er "fliselægning" ikke ret almindeligt brugt for "tiling"?

PPS: Universalitet (evt. i form af standsningsproblemet) og Gödels ufuldstændighedssætning synes jeg ofte har en evne til at dukke uforudset op. De optræder næsten som en fundamental fysisk grænse (ligesom lysets hastighed), men for information.

  • 2
  • 0
Torben Mogensen Blogger

Universalitet (evt. i form af standsningsproblemet) og Gödels ufuldstændighedssætning synes jeg ofte har en evne til at dukke uforudset op. De optræder næsten som en fundamental fysisk grænse (ligesom lysets hastighed), men for information.

Der er to sider af turingkomplethed: Det er en øvre grænse for, hvad man kan med en computer, og det er samtidigt noget, der er ret nemt at opnå (modsat lysets hastighed), så sammenligningen holder ikke helt.

Men mængden af måder, turingkomplethed kan opnås selv i simple eller løst strukturerede systemer, kan sige noget om emergent behaviour: Når kompleks opførsel opstår spontant. Turingkomplette systemer kan have vilkårligt kompleks opførsel, så at det turingkomplethed forekommer selv i simple systemer og i systemer uden global struktur tyder på at emergent behaviour (såsom liv) kan opstå næsten overalt.

  • 1
  • 0
Simon Shine

En kompliceret opdatering af den gamle Game of Life-glider som hackersymbol.


Nu har jeg trykket stop og start på videoen med glideren, og jeg synes ikke at der er nogen af dens atypiske tilstande som karakteriserer den særlig godt. (Så vidt jeg forstår, har gliderens geometriske form ikke en periode, selvom den gennemgår en endelig mængde former.) Jeg synes derfor det er svært at erstatte det klassiske emblem.

Når jeg betragter glideren bevæge sig på et Penrose-gulv, føles det lidt som at vi har sendt en velkendt sonde ud på en fjern planet og modtager billeder derfra. I stedet for at afgøre om atmosfæren kan indåndes, afgøres i stedet om stedets aksiomer kan bære liv. Når glideren først kan overleve, kan andre livsformer måske også, og i forlængelse dem som repræsenterer vilkårlige beregninger. Det er egentlig meget smukt.

Spørgsmålet er selvfølgelig: Hvor havner alle gliderne henne, når de forsvinder ud over skærmbilledet?

  • 0
  • 0
Log ind eller Opret konto for at kommentere