Rymdskepp (cellulär automat)

Ortogonala rymdskepp i Conways Game of Life med varierande hastighet (alla som var kända från 2009, exklusive 17c/45 "larven"). Observera att vissa rymdskepp "övertar" andra på grund av hastighetsskillnader.

I en cellulär automat kallas ett ändligt mönster ett rymdskepp om det dyker upp igen efter ett visst antal generationer i samma orientering men i en annan position. Det minsta antalet generationer kallas rymdskeppets period .

Beskrivning

Ett rymdskepps hastighet uttrycks ofta i termer av c , den metaforiska ljushastigheten (en cell per generation) som i många cellulära automater är den snabbaste som en effekt kan spridas. Till exempel sägs ett segelflygplan i Conways Game of Life ha en hastighet på ${\displaystyle c/4} ,$ eftersom det tar fyra generationer för ett givet tillstånd att översättas av en cell. På liknande sätt sägs det lätta rymdskeppet ha en hastighet på $c/2$ , eftersom det tar fyra generationer för ett givet tillstånd att översättas av två celler. Mer allmänt, om ett rymdskepp i en 2D-automat med Moore-kvarteret översätts med $(x,y)$ efter ${\displaystyle n} generationer, då$ är hastigheten $v$ definierad som:

$v={\frac {\max \left(|x|,|y|\right)}{n}}\,c$

Denna notation kan lätt generaliseras till cellulära automater med annan dimensionalitet än två.

En pullalong är ett mönster som inte är ett rymdskepp i sig utan som kan fästas på baksidan av ett rymdskepp för att bilda ett större rymdskepp. På samma sätt är en pushalong placerad framtill. Termen tagalong kan hänvisa till något av dessa mönster eller ett mönster som kan placeras vid sidan av ett rymdskepp för att bilda ett större rymdskepp.

Ett mönster som, när ett rymdskepp matas in, ger en kopia av rymdskeppet som färdas i en annan riktning kallas en reflektor . Om utgången istället är ett annat rymdskepp är mönstret känt som en omvandlare.

Rymdskepp är viktiga eftersom de ibland kan modifieras för att producera puffers . Rymdskepp kan också användas för att överföra information . Till exempel, i Conways Game of Life, är förmågan hos segelflygplanet (Livets enklaste rymdskepp) att överföra information en del av ett bevis på att livet är Turing-komplett .

I mars 2016 gjorde den oväntade upptäckten av ett litet men högperiod rymdskepp entusiasm för Game of Life-gemenskapen. Den fick namnet "copperhead". Ett liknande exempel, kallat "loafer", hittades några år tidigare.

upptäcktes det första elementära rymdskeppet med förskjutning (2,1) ( riddarvis ) och fick namnet Sir Robin.

externa länkar

• Rymdskepp i Conways Game of Life av David I. Bell
• Gliders i "Life"-Like Cellular Automata av David Eppstein