Automat komórkowy von Neumanna

Prosta konfiguracja w automacie komórkowym von Neumanna. Sygnał binarny jest wielokrotnie przekazywany wokół niebieskiej pętli przewodowej, przy użyciu wzbudzonych i spoczynkowych zwykłych stanów transmisji . Konfluentna komórka duplikuje sygnał na długości czerwonego przewodu składającego się ze specjalnych stanów transmisji . Sygnał przechodzi przez ten przewód i na końcu konstruuje nową komórkę. Ten konkretny sygnał (1011) koduje specjalny stan transmisji skierowany na wschód, wydłużając w ten sposób czerwony przewód za każdym razem o jedną komórkę. Podczas budowy nowa komórka przechodzi przez kilka stanów uczulonych, kierowanych przez sekwencję binarną.

Automaty komórkowe von Neumanna są pierwotnym wyrazem automatów komórkowych , których rozwój został zainspirowany sugestiami skierowanymi do Johna von Neumanna przez jego bliskiego przyjaciela i kolegę matematyka Stanisława Ulama . Ich pierwotnym celem było zapewnienie wglądu w logiczne wymagania dotyczące samoreplikacji maszyny i zostały użyte w uniwersalnym konstruktorze von Neumanna .

Automat komórkowy Nobili jest odmianą automatu komórkowego von Neumanna, wzbogaconą o zdolność zlewających się komórek do krzyżowania sygnałów i przechowywania informacji. Ten pierwszy wymaga dodatkowych trzech stanów, stąd automat komórkowy Nobili ma 32 stany zamiast 29. Automat komórkowy Huttona to kolejna odmiana, która pozwala na replikację pętli danych, analogicznej do pętli Langtona .

Definicja

Konfiguracja

Ogólnie rzecz biorąc, automaty komórkowe (CA) stanowią układ automatów skończonych stanów (FSA), które znajdują się w relacjach pozycyjnych między sobą, przy czym każdy FSA wymienia informacje z innymi FSA, z którymi sąsiaduje pozycyjnie. W automacie komórkowym von Neumanna maszyny (lub komórki ) o skończonych stanach są rozmieszczone w dwuwymiarowej siatce kartezjańskiej i łączą się z otaczającymi czterema komórkami. Ponieważ automat komórkowy von Neumanna był pierwszym przykładem wykorzystania tego układu, jest on znany jako sąsiedztwo von Neumanna .

Zestaw FSA definiuje przestrzeń komórkową o nieskończonym rozmiarze. Wszystkie FSA są identyczne pod względem funkcji przejścia między stanami lub zestawu reguł.

Sąsiedztwo (funkcja grupująca) jest częścią funkcji przejścia stanu i definiuje dla dowolnej komórki zbiór innych komórek , od których zależy stan tej komórki.

Wszystkie komórki wykonują swoje przejścia synchronicznie, zgodnie z uniwersalnym „zegarem”, jak w synchronicznym obwodzie cyfrowym.

Stany

Każdy FSA przestrzeni komórkowej von Neumanna może zaakceptować dowolny z 29 stanów zestawu reguł. Zestaw reguł jest pogrupowany w pięć ortogonalnych podzbiorów. Każdy stan zawiera kolor komórki w programie automatów komórkowych Golly w (czerwony, zielony, niebieski). Oni są

stan podstawowy U (48, 48, 48 )
stany przejściowe lub uczulone ( w 8 podstanach)
1. S (świeżo uczulony) (255, 0, 0)
2. S ₀ – (uwrażliwiony, nie otrzymawszy sygnału wejściowego przez jeden cykl) (255, 125, 0)
3. S ₀₀ – (uwrażliwiony, nie otrzymawszy sygnału wejściowego przez dwa cykle) (255, 175, 50)
4. S ₀₀₀ – (uwrażliwiony, nieotrzymując żadnego sygnału wejściowego przez trzy cykle) (251, 255, 0)
5. S ₀₁ – (uwrażliwiony, nie otrzymawszy sygnału wejściowego przez jeden cykl, a następnie sygnał wejściowy przez jeden cykl) (255, 200, 75)
6. S ₁ – (uczulony, otrzymawszy wejście na jeden cykl) (255, 150, 25)
7. S ₁₀ – (uwrażliwiony, otrzymawszy wejście na jeden cykl, a następnie brak wejścia na jeden cykl) (255, 255, 100)
8. S ₁₁ – (uwrażliwiony, po otrzymaniu sygnału wejściowego przez dwa cykle) (255, 250, 125)
stany konfluentne (w 4 stanach wzbudzenia)
1. C ₀₀ – spoczynek (i będzie również spoczynek w następnym cyklu) (0, 255, 128)
2. C ₀₁ – następny wzbudzony (teraz spokojny, ale będzie wzbudzony w następnym cyklu) (33, 215, 215)
3. C ₁₀ – podekscytowany (ale będzie spokojny w następnym cyklu) (255, 255, 128)
4. C ₁₁ – podekscytowany następny-podekscytowany (obecnie podekscytowany i będzie podekscytowany w następnym cyklu) (255, 128, 64)
zwykłe stany transmisji (w 4 kierunkach, wzbudzony lub spoczynkowy, tworząc 8 stanów)
1. Skierowany na północ (podekscytowany i spoczynkowy) (36, 200, 36) (106, 106, 255)
2. Skierowany na południe (podekscytowany i spoczynkowy) (106, 255, 106) (139, 139, 255)
3. Skierowany na zachód (podekscytowany i spokojny) (73, 255, 73) (122, 122, 255)
4. Skierowany na wschód (podekscytowany i spokojny) (27, 176, 27) (89, 89, 255)
specjalne stany transmisji (w 4 kierunkach, wzbudzony lub spoczynkowy, tworząc 8 stanów)
1. Skierowany na północ (podekscytowany i spoczynkowy) (191, 73, 255) (255, 56, 56)
2. Skierowany na południe (podekscytowany i spokojny) (203, 106, 255) (255, 89, 89)
3. Skierowany na zachód (podekscytowany i spokojny) (197, 89, 255) (255, 73, 73)
4. Skierowany na wschód (podekscytowany i spokojny) (185, 56, 255) (235, 36, 36)

Stany „podekscytowane” przenoszą dane z szybkością jednego bitu na krok zmiany stanu.

Należy zauważyć, że stany konfluentne mają właściwość opóźnienia jednego cyklu, dzięki czemu skutecznie przechowują dwa bity danych w dowolnym momencie.

Reguły stanu transmisji

Przepływ bitów między komórkami jest wskazywany przez właściwość kierunku. Obowiązują następujące zasady:

Stany transmisji stosują operator OR do wejść, co oznacza, że komórka w stanie transmisji (zwykłym lub specjalnym) zostanie pobudzona w czasie t+1 , jeśli którekolwiek z wejść wskazujących na nią zostanie wzbudzone w czasie t
Dane przechodzą z komórki A w zwykłym stanie transmisji do sąsiedniej komórki B w zwykłym stanie transmisji, zgodnie z właściwością kierunku A (chyba że B jest również skierowany w stronę A , w którym to przypadku dane znikają).
Dane przechodzą z komórki A w specjalnym stanie transmisji do sąsiedniej komórki B w specjalnym stanie transmisji, zgodnie z tymi samymi zasadami, co w przypadku zwykłych stanów transmisji.
Dwa podzbiory stanów transmisji, zwykłe i specjalne, są wzajemnie antagonistyczne:
- Biorąc pod uwagę komórkę A w czasie t w wzbudzonym zwykłym stanie transmisji
- wskazując na komórkę B w dowolnym specjalnym stanie transmisji
- w chwili t+1 komórka B stanie się stanem podstawowym. Specjalna komórka transmisyjna została „zniszczona”.
- podobna sekwencja wystąpi w przypadku komórki w specjalnym stanie transmisji „wskazując” na komórkę w zwykłym stanie transmisji

Reguły stanu zbieżnego

Następujące szczegółowe zasady mają zastosowanie do stanów konfluencji:

Stany konfluentne nie przekazują między sobą danych.
Stany konfluentne pobierają dane wejściowe z jednego lub więcej zwykłych stanów transmisji i dostarczają dane wyjściowe do stanów transmisji, zwykłych i specjalnych, które nie są skierowane w stronę stanu konfluencji.
Dane nie są przesyłane wbrew właściwości kierunku stanu transmisji.
Dane przechowywane przez stan konfluencji są tracone, jeśli ten stan nie ma sąsiedniego stanu transmisji, który również nie jest skierowany na stan konfluencji.
Zatem komórki stanu konfluentnego są używane jako „pomosty” między liniami transmisyjnymi komórek stanu transmisji zwykłej do specjalnej.
Stan konfluencji stosuje operator AND do wejść, „zapisując” wzbudzone wejście tylko wtedy, gdy wszystkie potencjalne wejścia są wzbudzone jednocześnie.
Komórki konfluentne opóźniają sygnały o jedno pokolenie więcej niż komórki OTS; jest to konieczne ze względu na ograniczenia parytetu .

Zasady budowy

Dziewięć typów komórek, które można zbudować w CA von Neumanna. Tutaj sygnały binarne przechodzą przez dziewięć zwykłych linii transmisyjnych, tworząc nową komórkę, gdy na końcu napotkają stan podstawowy. Na przykład ciąg binarny 1011 jest pokazany w piątym wierszu i konstruuje specjalny stan transmisji skierowany na wschód – jest to ten sam proces, który jest używany w automacie na górze tej strony. Zwróć uwagę, że nie ma interakcji między sąsiednimi przewodami, jak na przykład w Wireworld , co pozwala na kompaktowe upakowanie komponentów.

Początkowo większość przestrzeni komórkowej, wszechświata automatu komórkowego, jest „pusta” i składa się z komórek w stanie podstawowym U. Po otrzymaniu pobudzenia wejściowego z sąsiedniego zwykłego lub specjalnego stanu transmisji, komórka w stanie podstawowym staje się „uwrażliwiona”, przechodząc przez szereg stanów, zanim ostatecznie „spocznie” w spoczynku transmisji lub stanie konfluencji.

Wybór, do którego stanu docelowego osiągnie komórka, zależy od sekwencji sygnałów wejściowych. Dlatego stany przejściowe / uczulone można traktować jako węzły drzewa bifurkacyjnego prowadzącego od stanu podstawowego do każdego ze spoczynkowych stanów transmisji i konfluencji.

W poniższym drzewie sekwencja wejść jest pokazana jako łańcuch binarny po każdym kroku:

komórka w stanie podstawowym U , po otrzymaniu sygnału wejściowego, w następnym cyklu przejdzie w stan S (nowo uczulony) (1)
komórka w stanie S , bez danych wejściowych, przejdzie w stan S ₀ (10)
- komórka w stanie S ₀ , bez danych wejściowych, przejdzie w stan S ₀₀ (100)
  - komórka w stanie S ₀₀ , przy braku danych wejściowych, przejdzie w stan S ₀₀₀ (1000)
    - komórka w stanie S ₀₀₀ , bez danych wejściowych, przejdzie w stan zwykłej transmisji skierowanej na wschód (10000)
    - komórka w stanie S ₀₀₀ , po wprowadzeniu danych wejściowych, przejdzie w stan zwykłej transmisji skierowanej na północ (10001)
  - komórka w stanie S ₀₀ , po wprowadzeniu danych wejściowych, przejdzie w stan zwykłej transmisji skierowanej na zachód (1001)
- komórka w stanie S ₀ , po wprowadzeniu danych wejściowych, przejdzie w stan S ₀₁ (101)
  - komórka w stanie S ₀₁ , przy braku danych wejściowych, przejdzie w stan zwykłej transmisji skierowanej na południe (1010)
  - komórka w stanie S ₀₁ , po wprowadzeniu, przejdzie w specjalny stan transmisji skierowany na wschód (1011)
komórka w stanie S , po wprowadzeniu danych wejściowych, przejdzie w stan S ₁ (11)
- komórka w stanie S ₁ , przy braku danych wejściowych, przejdzie w stan S ₁₀ (110)
  - komórka w stanie S ₁₀ , bez danych wejściowych, przejdzie w specjalny stan transmisji skierowany na północ (1100)
  - komórka w stanie S ₁₀ , biorąc pod uwagę dane wejściowe, przejdzie w specjalny stan transmisji skierowany na zachód (1101)
- komórka będąca w stanie S ₁ po wprowadzeniu danych przejdzie w stan S ₁₁ (111)
  - komórka w stanie S ₁₁ , bez danych wejściowych, przejdzie w specjalny stan transmisji skierowany na południe (1110)
  - komórka w stanie S ₁₁ , biorąc pod uwagę dane wejściowe, przejdzie w spoczynkowy stan konfluentny C ₀₀ (1111)

Pamiętaj, że:

jeden cykl wejścia więcej (cztery po początkowej sensytyzacji) jest wymagany do zbudowania zwykłego stanu transmisji skierowanego na wschód lub północ niż którykolwiek z pozostałych stanów (które wymagają trzech cykli wejścia po początkowej sensytyzacji),
„domyślnym” stanem spoczynku, którego wynikiem jest konstrukcja, jest zwykły stan transmisji skierowany na wschód - który wymaga początkowego wejścia uczulającego, a następnie czterech cykli braku sygnału wejściowego.

Zasady niszczenia

Około 4000 bitów danych w zwiniętej „taśmie” konstruującej złożony wzór. Wykorzystuje to 32-stanową odmianę automatów komórkowych von Neumanna, znaną jako Hutton32.

Wejście do komórki stanu konfluencji z komórki stanu transmisji specjalnej spowoduje, że komórka stanu konfluencji zostanie zredukowana z powrotem do stanu podstawowego.
Podobnie wejście do zwykłej komórki stanu transmisji ze specjalnej komórki stanu transmisji spowoduje, że komórka stanu zwykłej transmisji zostanie zredukowana z powrotem do stanu podstawowego.
I odwrotnie, wejście do specjalnej komórki stanu transmisji z komórki stanu zwykłej transmisji spowoduje, że komórka stanu transmisji specjalnej zostanie zredukowana z powrotem do stanu podstawowego.

Zobacz też

Von Neumann, J. i AW Burks (1966). Teoria samoreprodukujących się automatów. Urbana, University of Illinois Press. [1]

Linki zewnętrzne

Golly - obsługuje CA von Neumanna wraz z Game of Life i innymi zestawami reguł.