Edens trädgård (cellautomat)

A Garden of Eden i Conways Game of Life , upptäckt av R. Banks 1971. Cellerna utanför bilden är alla döda (vita).
Ett föräldralöst barn i livet hittat av Achim Flammenkamp. Svarta rutor krävs levande celler; blå x är obligatoriska döda celler.

I en cellulär automat är en Edens trädgård en konfiguration som inte har någon föregångare. Det kan vara den initiala konfigurationen av automaten men kan inte uppstå på något annat sätt. John Tukey döpte dessa konfigurationer efter Edens lustgård i Abrahams religioner , som skapades från ingenstans.

En Edens trädgård bestäms av tillståndet för varje cell i automaten (vanligtvis ett en- eller tvådimensionellt oändligt kvadratiskt gitter av celler). Men för alla Edens lustgård finns det ett ändligt mönster (en delmängd av celler och deras tillstånd, kallad föräldralös ) med samma egenskap att inte ha någon föregångare, oavsett hur de återstående cellerna fylls i. En konfiguration av hela automaten är en Edens lustgård om och bara om den innehåller ett föräldralöst barn. För endimensionella cellulära automater kan föräldralösa barn och Gardens of Eden hittas med en effektiv algoritm, men för högre dimensioner är detta ett obeslutligt problem . Ändå har datorsökningar lyckats hitta dessa mönster i Conways Game of Life .

The Garden of Eden-satsen av Moore och Myhill hävdar att en cellulär automat på det kvadratiska rutnätet, eller på en plattsättning av något högre dimensionellt euklidiskt utrymme , har en Edens trädgård om och bara om den har tvillingar , två finita mönster som har samma efterträdare närhelst den ena ersätter den andra.

Definitioner

En cellulär automat definieras av ett rutnät av celler, en ändlig uppsättning tillstånd som kan tilldelas varje cell och en uppdateringsregel. Ofta är rutnätet av celler det en- eller tvådimensionella oändliga kvadratiska gittret . Uppdateringsregeln bestämmer nästa tillstånd för varje cell som en funktion av dess nuvarande tillstånd och av det aktuella tillståndet för vissa andra närliggande celler ( cellens grannskap ). Grannskapet kan vara en godtycklig ändlig uppsättning celler, men varje två celler bör ha grannar i samma relativa positioner och alla celler måste använda samma uppdateringsregel. En konfiguration av automaten är en tilldelning av ett tillstånd till varje cell.

Efterföljaren till en konfiguration är en annan konfiguration , bildad genom att tillämpa uppdateringsregeln samtidigt på varje cell. Automatens övergångsfunktion är den funktion som mappar varje konfiguration till dess efterföljare . Om efterföljaren till konfiguration X är konfiguration Y , så är X en föregångare till Y. En konfiguration kan ha noll, en eller flera föregångare, men den har alltid exakt en efterföljare. En Edens trädgård definieras som en konfiguration med noll föregångare.

Ett mönster , för en given cellulär automat, består av en ändlig uppsättning celler tillsammans med ett tillstånd för var och en av dessa celler. En konfiguration innehåller ett mönster när tillstånden för cellerna i mönstret är desamma som tillstånden för samma celler i konfigurationen (utan att översätta cellerna innan de matchas). Definitionen av föregångare till konfigurationer kan utvidgas till föregångare till mönster: en föregångare till ett mönster är bara en konfiguration vars efterföljare innehåller mönstret. Ett föräldralöst barn är alltså ett mönster utan någon föregångare.

Söker efter Edens lustgård

För endimensionella cellulära automater kan Gardens of Eden hittas med en effektiv algoritm vars körtid är polynom i storleken på automatens regeltabell. För högre dimensioner är det ett oavgörligt problem att avgöra om en Edens lustgård existerar, vilket innebär att det inte finns någon algoritm som kan garanteras avsluta och producera det korrekta svaret. Icke desto mindre är det i många fall möjligt att använda Edens trädgårdssats (nedan) för att sluta sig till att det finns en lösning och sedan använda en sökalgoritm för att hitta en.

Det skulle vara möjligt för ett datorprogram att söka efter föräldralösa mönster genom att systematiskt undersöka alla ändliga mönster, i ordning genom att öka storleken, och genom att testa alla möjliga föregångare för varje mönster för att avgöra om det faktiskt är ett föräldralöst. Men antalet mönster som skulle behöva genereras för att hitta en Edens lustgård på detta sätt är exponentiellt i mönstrets område. Detta enorma antal mönster skulle göra den här typen av brute-force-sökning oöverkomligt dyr, även för relativt små mönsterstorlekar.

Jean Hardouin-Duparc ( 1972–73 , 1974 ) var pionjär med en mer effektiv beräkningsmetod för att hitta föräldralösa mönster. Hans metod är baserad på teorin om formella språk och tar en tid som är exponentiell i mönstrets bredd snarare än dess område. Nyckelidén är att det för vilken fast bredd som helst är möjligt att konstruera en icke-deterministisk finit automat som känner igen mönster av en given bredd som har en föregångare. Inmatningssymbolerna till denna maskin beskriver varje rad i mönstret, och maskinens tillstånd beskriver de närliggande raderna med möjliga föregångare för den del av mönstret som hittills har matats in. Man kan konstruera från denna maskin en annan finita tillståndsmaskin som känner igen den komplementära uppsättningen , mönstren som inte har föregångare, genom att konvertera den icke-deterministiska finita tillståndsmaskinen till en deterministisk finit automat genom att använda powersetkonstruktionen och sedan komplettera dess uppsättning av accepterande tillstånd . När en maskin som känner igen den komplementära uppsättningen har konstruerats, kan man testa om språket den känner igen är tomt, genom att söka efter en väg från starttillståndet till ett accepterande tillstånd. Denna sökväg, om den finns, ger en rad-för-rad-beskrivning av ett föräldralöst mönster.

Martin Gardner tillskriver Alvy Ray Smith observationen att Edens trädgårdssats gäller Conways Game of Life och bevisar existensen av Edens trädgårdar för denna regel. Den första explicita Edens trädgård i livet, med sina levande celler som passar i en 9 × 33 rektangel, identifierades som en kandidat för att bli en Edens trädgård av Roger Banks 1971, och verifierades sedan genom en uttömmande sökning efter föregångare. Därefter använde Hardouin-Duparc sin formella språkmetod för att hitta de smalaste möjliga Gardens of Eden i Conways Game of Life, där avgränsningsrutan för deras levande celler bara var sex celler bred.

Det minsta kända föräldralösa mönstret i Conways Game of Life (efter område av dess begränsningslåda) hittades av Steven Eker i april 2016. Det har 57 levande celler och passar i en 8×12 rektangel.

Förekomsten av föräldralösa barn

Per definition tillhör varje föräldralös barn en Edens lustgård: att utöka ett föräldralöst barn till en konfiguration av hela automaten, genom att välja ett tillstånd för varje kvarvarande cell godtyckligt, kommer alltid att producera en Edens lustgård. Men det omvända är också sant: varje Edens lustgård innehåller minst ett föräldralöst barn. För att bevisa detta använder Kari ett topologiskt argument, baserat på Curtis–Hedlund–Lyndon-satsen enligt vilken övergångsfunktionerna hos cellulära automater är exakt de translationsinvarianta kontinuerliga funktionerna i konfigurationsrummet. Här definieras kontinuitet genom att tilldela en diskret topologi till den ändliga uppsättningen av tillstånd hos automaten, och sedan använda en produkttopologi med en term i produkten för varje cell i automaten för att konstruera ett topologiskt utrymme vars punkter är automatens konfigurationer. Enligt Tychonoffs teorem är det ett kompakt utrymme .

För varje ändligt mönster är uppsättningen av konfigurationer som innehåller mönstret en öppen uppsättning i denna topologi, kallad en cylinder . Cylindrarna utgör en grund för topologin. Som Kari observerar är samlingen av konfigurationer som inte är Gardens of Eden bara bilden av övergångsfunktionen, så enligt det slutna kartlemmat för kompakta utrymmen är det en sluten uppsättning . Uppsättningen av Edens trädgårdar är på motsvarande sätt en öppen uppsättning. Eftersom den är öppen och cylindrarna utgör en grund, kan uppsättningen av Edens trädgårdar representeras som en förening av cylindrar. Var och en av cylindrarna i denna förening består bara av Gardens of Eden, så mönstret som bestämmer varje cylinder måste vara en föräldralös. Om uppsättningen av Gardens of Eden inte är tom, måste det finnas minst en cylinder i denna förening, så det måste finnas minst en föräldralös. Och någon speciell Edens trädgård måste tillhöra en av dessa cylindrar, och måste därför innehålla den föräldralösa för den cylindern.

Edens lustgårds sats

I en cellulär automat är två finita mönster tvillingar om det ena kan ersätta det andra var det än dyker upp, utan att ändra framtida konfigurationer. En cellulär automat är injektiv om varje par av distinkta konfigurationer av automaten förblir olika efter ett steg i automaten, och lokalt injektiv om den inte har några tvillingar. Det är surjektivt om och bara om varje konfiguration har en föregångare; det vill säga om och bara om den inte har någon Edens trädgårdskonfiguration. En automat som är både injektiv och surjektiv kallas en reversibel cellulär automat .

The Garden of Eden theorem , på grund av Edward F. Moore ( 1962 ) och John Myhill ( 1963 ), hävdar att en cellulär automat i ett euklidiskt utrymme är lokalt injektiv om och bara om den är surjektiv. Med andra ord hävdar den att en cellulär automat har en Edens trädgård, om och bara om den har tvillingar. Mer starkt, varje icke-lokalt-injektiv cellulär automat har ett föräldralöst mönster. En omedelbar följd är att en injektiv cellulär automat måste vara surjektiv. Moore bevisade en riktning av satsen, att automater med tvillingar har föräldralösa barn; Myhill bevisade motsatsen, att en automat med ett föräldralöst barn också har tvillingar.

När det gäller Conways Game of Life är tvillingar mycket lättare att hitta än föräldralösa barn. Till exempel är ett fem gånger fem block av döda celler och ett fem gånger fem block med dess mittcell levande och de återstående cellerna döda tvillingar: mittcellens tillstånd kan inte påverka senare konfigurationer av mönstret. I det här fallet tillåter Edens lustgårds sats att existensen av en Edens lustgård kan demonstreras mycket lättare än genom att hitta ett explicit föräldralöst mönster.

Bevisskiss

Huvudtanken med beviset för satsen är att använda ett räkneargument för att visa att varje misslyckande av lokal injektivitet (tvillingmönster) leder till ett föräldralöst mönster, och vice versa. Antag mer i detalj att automatens underliggande gitter är ett tvådimensionellt kvadratiskt rutnät, att det har olika celltillstånd, att tvillingmönstren P och Q båda passar in i en n × n kvadrat, och att radien av någon cells grannskap är högst n . Sedan, för att avgöra om ett mönster som passar inom en mn × mn kvadrat är ett föräldralöst, behöver man bara titta på de delar av potentiella föregångare som passar inom en ( m + 2) n × ( m + 2) n kvadrat och som inte innehåller mönster Q . Men det finns bara ( s n × n − 1) ( m + 2) × ( m + 2) av dessa potentiella föregångare. För tillräckligt stora värden på m är detta antal mindre än antalet s mn × mn för potentiella föräldralösa barn. Därför har ett av de potentiella föräldralösa barnen ingen föregångare och är verkligen en föräldralös; det vill säga icke-injektivitet innebär icke-surjektivitet. Omvänt (låter n vara storleken på en begränsningsram för ett föräldralöst barn) visar ett mycket liknande räkneargument att antalet mönster som passar inom en ( m + 2) n × ( m + 2) n kvadrat och inte innehåller en föräldralös är för liten för att ge en distinkt efterföljare till varje startmönster inom en mn × mn kvadrat, av vilket det följer att två av de möjliga startmönstren är tvillingar. Därför innebär icke-surjektivitet lokal icke-injektivitet.

Injektivitet kontra lokal injektivitet

Tid-rymddiagram av Regel 90 , som inte har någon Edens lustgård trots att den inte är injektiv. Varje rad visar en konfiguration, med tiden som går nedåt.

Skillnaden mellan injektivitet och lokal injektivitet i satsen är nödvändig, eftersom det finns cellulära automater som är lokalt injektiva men inte injektiva. Ett exempel är Regel 90 , den endimensionella binära automaten vars uppdateringsregel ersätter varje cells tillstånd med den exklusiva eller av dess två grannar. I den här automaten har varje stat fyra föregångare, så den är inte injektiv men har heller ingen Edens lustgård.

Med stilla tillstånd

I automater som Conways Game of Life finns det ett speciellt "vilande" tillstånd så att en vilande cell vars grannskap är helt vilande förblir vilande. I detta fall kan man definiera en "ändlig konfiguration" som en konfiguration med endast ändligt många icke-vilande celler. Varje icke-lokalt injektiv cellulär automat med ett vilande tillstånd har Edens trädgårdar som i sig är ändliga konfigurationer, till exempel vilken ändlig konfiguration som helst som innehåller ett föräldralöst barn. Det kan också vara möjligt för en automat att ha en ändlig konfiguration vars enda föregångare inte är ändliga (till exempel, i Regel 90, har en konfiguration med en enda levande cell denna egenskap). Edens trädgårdssats kännetecknar dock inte förekomsten av sådana mönster.

I icke-euklidiska geometrier

I cellulära automater som definieras över tessellationer av det hyperboliska planet , eller av högredimensionella hyperboliska utrymmen, fungerar inte räkneargumentet i beviset för Edens lustgårds sats, eftersom det implicit beror på egenskapen hos euklidiska utrymmen att gränsen för en regionen växer mindre snabbt än dess volym som en funktion av radien. Det finns hyperboliska cellulära automater som har tvillingar men som inte har en Edens lustgård, och andra hyperboliska cellulära automater som har en Edens lustgård men inte har tvillingar; dessa automater kan definieras, till exempel, på ett rotationsinvariant sätt på de likformiga hyperboliska plattorna där tre heptagoner möts vid varje vertex, eller i vilka fyra femhörningar möts vid varje vertex.

Emellertid kan Edens trädgårds sats generaliseras bortom euklidiska utrymmen, till cellulära automater definierade på elementen i en mottaglig grupp . En svagare form av Edens lustgårds teorem hävdar att varje injektiv cellulär automat är surjektiv. Det kan bevisas för soficgrupper med hjälp av Ax-Grothendieck-satsen , en analog relation mellan injektivitet och bijektivitet i algebraisk geometri. Mer allmänt kallas de grupper som denna svagare form gäller surjunktiva grupper . Det finns inga kända exempel på grupper som inte är surjunktiva.

I fiktion

I Greg Egans roman Permutation City använder huvudpersonen en Garden of Eden-konfiguration för att skapa en situation där en kopia av sig själv kan bevisa att han lever i en simulering. Tidigare hade alla hans simulerade kopior befunnit sig i någon variant av den "verkliga världen"; även om de hade minnen av att vara simulerade kopior som levde i en simulering, fanns det alltid en enklare förklaring till hur dessa minnen blev till. Edens trädgårdskonfiguration kan dock inte förekomma annat än i en intelligent designad simulering. De religiösa parallellerna är avsiktliga.

Anteckningar

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Garden_of_Eden_(cellular_automaton)&oldid=1135805831 "