Rymdskepp (cellulär automatkonfiguration)

Ett rymdskepp [5] ( eng.  rymdskepp ) är en klass av konfigurationer i "Life" - en modell av en cellulär automat skapad av Conway .

Beskrivning

Konfigurationen av "Life" eller en annan cellulär automat kallas ett rymdskepp om det efter ett visst antal generationer dyker upp igen utan tillägg eller förluster, men med en förskjutning i förhållande till sin ursprungliga position. Det minsta sådana antalet generationer är rymdskeppsperioden [ 6] .

Den första rymdfarkosten som upptäcktes var ett segelflygplan . Segelflygplanet hittades när han spårade utvecklingen av R-pentamino 1970 av Richard Guy [1] [7] [8] .

Ett rymdskepp med period p som rör sig ( m , n ) under sin period, där m  ≥  n , är av typen ( m ,  n )/  p . Som bevisats av Conway 1970, p  ≥ 2 m  + 2 n [6] .

Rymdfarkoster som rör sig horisontellt eller vertikalt kallas ortogonala fordon . Om rymdfarkostens rörelse sker diagonalt i en vinkel på 45° kallas ett sådant skepp diagonalt . Rymdskepp som rör sig i andra vinklar kallas sned eller sned .  År 2010 designades den första lutande rymdfarkosten av typen (5120, 1024) / 33699586 [9] .

Hastighet

Ljushastigheten i en given cellulär automat är den högsta hastigheten för informationsutbredning. Ljushastigheten i "Life" är lika med schackkungens hastighet - hastigheten för en cell per generation horisontellt, vertikalt eller diagonalt. Vanligtvis betecknas ljusets hastighet med bokstaven c [1] [6] [10] [11] .

Rymdfarkostens hastighet bestäms av förhållandet mellan förskjutningsavstånd och period. Ofta uttrycks hastigheten i termer av c . Således är hastigheten för ett glidflygplan i "Life" c  / 4, eftersom det rör sig en ruta diagonalt i fyra generationer [7] . Den enklaste ortogonala rymdfarkosten, LKK, rör sig vid c  / 2 [2] .

I allmänhet, om ett rymdskepp i en tvådimensionell cellulär automat på ett kvadratiskt rutnät rör sig med vektorn ( x ,  y ) efter n generationer, är dess hastighet [11]

Exempel

B3/S35

Följande konfigurationer är ortogonala rymdskepp i "Life"-varianten, en cellulär automat med B3/S35 -regler (en cell föds om den har tre grannar och överlever om den har tre eller fem grannar).

Relaterade konfigurationer

Tagalong ( eng.  tagalong "kola") - en konfiguration som inte i sig är en rymdfarkost, men som kan fästas på en rymdfarkost för att bilda en ny rymdfarkost [12] . Med andra ord är en tagalong en del av ett rymdskepp som kan tas bort utan att förstöra skeppet [13] .

Tagalong, som ligger framför rymdfarkosten, kallas pushalong ( eng.  pushalong "crush") [14] .

En konfiguration som kan ändra riktningen på ett rymdskepp utan att förstöras kallas en reflektor . 

En pistol ( engelsk  gun ) är en stationär konfiguration som periodiskt släpper en rymdfarkost [15] .

Betydelse

Rymdskepp kan användas för att överföra information. Segelflygplanets förmåga att bära information blev en del av beviset på att "Life" är Turing komplett [16] [17] .

Anteckningar

1. ↑ 1 2 3 Klumova I. N. Game "Life"  // Kvant . - 1974. - Nr 9 . - S. 26-30 .
2. ↑ 1 2 LKK (lätt rymdfarkost) . Livets ordbok. Hämtad 10 augusti 2013. Arkiverad från originalet 11 oktober 2012. (obestämd)
3. ↑ SKK (mellanstor rymdfarkost) . Livets ordbok. Hämtad 10 augusti 2013. Arkiverad från originalet 10 oktober 2012. (obestämd)
4. ↑ TKK (tung rymdfarkost) . Livets ordbok. Hämtad 10 augusti 2013. Arkiverad från originalet 10 februari 2013. (obestämd)
5. ↑ Ej att förväxla med skepp Arkiverad 9 februari 2013 på Wayback Machine (fartyg) - en stabil konfiguration.
6. ↑ 1 2 3 Rymdskepp . Livets ordbok. Hämtad 10 augusti 2013. Arkiverad från originalet 9 februari 2013. (obestämd)
7. ↑ 1 2 Segelflygplan . Livets ordbok. Hämtad 10 augusti 2013. Arkiverad från originalet 8 februari 2013. (obestämd)
8. ↑ Rymdskepp . conwaylife.com. Hämtad 10 augusti 2013. Arkiverad från originalet 24 augusti 2013. (obestämd)
9. ↑ Rymdskeppet Oblique Life skapat . Game of Life News (19 maj 2010). Hämtad 10 augusti 2013. Arkiverad från originalet 1 juni 2013. (obestämd)
10. ↑ Ljusets hastighet . Livets ordbok. Hämtad 10 augusti 2013. Arkiverad från originalet 10 oktober 2012. (obestämd)
11. ↑ 12 hastighet . _ conwaylife.com. Hämtad 10 augusti 2013. Arkiverad från originalet 30 juli 2013. (obestämd)
12. ↑ Tagalong . Livets ordbok. Hämtad 10 augusti 2013. Arkiverad från originalet 10 februari 2013. (obestämd)
13. ↑ Tagalong . Eric Weissteins Treasure Trove of Life CA. Hämtad 10 augusti 2013. Arkiverad från originalet 22 april 2015. (obestämd)
14. ↑ Pushalong . Livets ordbok. Hämtad 10 augusti 2013. Arkiverad från originalet 6 maj 2019. (obestämd)
15. ↑ Hagelgevär . Livets ordbok. Hämtad 10 augusti 2013. Arkiverad från originalet 9 februari 2013. (obestämd)
16. ↑ Paul Chapman. Life Universal Computer (11 november 2002). Hämtad 12 juli 2009. Arkiverad från originalet 6 september 2009. (obestämd)
17. ↑ Berlekamp, ​​​​ER ; Conway, John Horton & Guy, R.K. (2004), Winning Ways for your Mathematical Plays (2nd ed.), A.K. Peters Ltd, ISBN 978-1-56881-130-7 ; ISBN 1-56881-142-X ; ISBN 1-56881-143-8 ; ISBN 1-56881-144-6 

Länkar

• Nikolay Belyuchenko. Livets ordbok . Arkiverad från originalet den 10 oktober 2012. (obestämd)
• Stephen A. Silver. Livslexikon . Arkiverad från originalet den 26 maj 2013. (obestämd)
• Nikolay Belyuchenko. Rymdskepp i Conways liv . Arkiverad från originalet den 3 oktober 2012. (obestämd)
• David I Bell. Rymdskepp i Conways Game of Life . (obestämd)
• David Eppstein. Segelflygplan i "Life"-Like Cellular Automata . (obestämd)
• Achim Flammenkamp. Naturliga rymdskepp i Game of Life . — fartyg som visas i slumpmässiga konfigurationer. (obestämd)
• Rymdskeppsarkiv . Game of Life Nyheter. (obestämd)