폰 노이만 셀룰러 오토매틱

Von Neumann cellular automaton
폰 노이만의 셀룰러 오토메이션의 단순한 구성. 흥분 및 정지 상태의 일반 전송 상태를 사용하여 파란색 와이어 루프를 중심으로 이진 신호가 반복적으로 전달된다. 합체 셀은 신호를 특수 전송 상태로 구성된 빨간색 와이어의 길이에 복제한다. 그 신호는 이 전선을 통과하여 끝부분에 새로운 전지를 건설한다. 이 특정 신호(1011)는 동향 특수 전송 상태를 코드화하므로 적색 와이어가 매번 1셀씩 확장된다. 건설하는 동안, 새로운 셀은 이항 순서에 의해 지시된 몇 개의 감각화된 상태를 통과한다.

폰 노이만 세포 오토마타는 세포 오토마타의 원래 표현으로, 존 폰 노이만에게 그의 절친한 친구이자 동료 수학자 스타니슬라브 울람이 제안한 것에 의해 발전되었다. 그들의 원래 목적은 기계 자기복제를 위한 논리적인 요구조건에 대한 통찰력을 제공하는 것이었고, 그것들은 폰 노이만의 보편적인 건설자(con Neumann's universal constructor.

노빌리의 세포 자동화는 폰 노이만의 세포 자동화를 변형시킨 것으로, 결합 세포가 신호를 교차시키고 정보를 저장하는 기능으로 증강되었다. 전자는 3개의 주를 추가로 필요로 하기 때문에 노빌리의 세포자동차는 29개가 아닌 32개의 주를 가지고 있다. Hutton의 세포 자동화는 Langton의 루프와 유사한 데이터 루프를 복제할 수 있는 또 다른 변형이다.

정의

배열

일반적으로 셀룰러 오토마타(CA)는 서로 위치 관계에 있는 유한 상태 오토마타(FSA)의 배치를 구성하며, 각 FSA는 위치적으로 인접한 다른 FSA들과 정보를 교환한다. 폰 노이만의 세포자동화에서는 유한 상태 기계(또는 세포)가 2차원 카르테시안 그리드에 배열되어 있으며, 주변 4개의 세포와 접한다. 폰 노이만의 세포 자동화가 이 배치를 사용한 첫 번째 예였기 때문에 폰 노이만 근린으로 알려져 있다.

FSAs 세트는 무한대의 셀 공간을 정의한다. 모든 FSA는 상태 변환 함수 또는 규칙 집합 측면에서 동일하다.

근린(그룹화 함수)은 상태 변환 함수의 일부로서, 셀의 상태가 의존하는 다른 셀의 집합을 정의한다.

모든 셀은 동기식 디지털 회로에서와 같은 범용 "클록"에 맞추어 동기식으로 전환한다.

미국.

폰 노이만 세포 공간의 각 FSA는 규칙 집합의 29개 상태 중 하나를 받아들일 수 있다. 규칙 집합은 5개의 직교 하위 집합으로 그룹화된다. 각 주는 셀룰러 오토마타 프로그램 골리 인(빨간색, 녹색, 파란색)에 있는 셀의 색상을 포함한다. 그들은 그렇다.

  1. 지상주 U. (48, 48, 48)
  2. 전환 또는 감작 상태(8개 변전소)
    1. S (신규 감작) (255, 0, 0)
    2. S0 – (감지됨, 한 사이클 동안 아무런 입력도 수신하지 않음)(255, 125, 0)
    3. S00 – (감지됨, 두 사이클 동안 아무런 입력도 수신하지 않음)(255, 175, 50)
    4. S000 – (감지됨, 3 사이클 동안 아무런 입력도 수신하지 않음)(251, 255, 0)
    5. S01 – (감지됨, 한 사이클 동안 입력을 수신하지 않고 한 사이클 동안 입력을 수신함)(255, 200, 75)
    6. S1 – (감지, 한 사이클 동안 입력 수신)(255, 150, 25)
    7. S10 – (감지됨, 한 사이클 동안 입력을 수신한 후 한 사이클 동안 입력이 없음) (255, 255, 100)
    8. S11 – (감지, 2 사이클 동안 입력 수신)(255, 250, 125)
  3. 합체 상태 (4개 흥분 상태)
    1. C00 – 대기 전류(0, 255, 128)
    2. C01 – 차상위(지금은 대기 중이지만 다음 사이클은 흥분됨)(33, 215, 215)
    3. C10 – 흥분됨(255, 255, 128)
    4. C11 – 흥분된 다음 단계(현재 흥분되고 다음 사이클이 흥분됨)(255, 128, 64)
  4. 일반 변속기 상태(4방향, 흥분 또는 대기 상태, 8개 상태 설정)
    1. 북쪽 방향 (흥분 및 대기) (36, 200, 36) (106, 106, 255)
    2. 남향(흥분 및 대기)(106, 255, 106)(139, 139, 255)
    3. 서부 방향 (흥분 및 대기) (73, 255, 73) (122, 122, 255)
    4. 동부 방향 (흥분 및 대기) (27, 176, 27) (89, 89, 255)
  5. 특수 트랜스미션 상태(4방향, 흥분 또는 대기 상태, 8개 상태
    1. 북쪽 방향(191, 73, 255) (255, 56, 56)
    2. 남향(흥분 및 대기)(203, 106, 255)(255, 89, 89)
    3. 서부 방향(197, 89, 255) (255, 73, 73)
    4. 동쪽 방향(흥분 및 대기)(185, 56, 255)(235, 36, 36)

"흥분된" 상태는 상태 전환 단계당 1비트 속도로 데이터를 전송한다.

결합 상태는 1주기 지연의 특성을 가지므로 주어진 시간에 효과적으로 2비트의 데이터를 보유한다는 점에 유의하십시오.

전송 상태 규칙

셀 사이의 비트 흐름은 방향 속성으로 표시된다. 다음과 같은 규칙이 적용된다.

  • 전송 상태는 OR 연산자를 입력에 적용하며, 즉, 전송 상태(일반 또는 특수)의 셀은 시간 t+1에서 이를 가리키는 입력 중 하나가 흥분하면 시간 t+1에 흥분한다.
  • 데이터는 A의 방향 속성에 따라 일반 전송 상태의 셀 A에서 일반 전송 상태의 인접 셀 B로 전달된다(B도 A로 향하지 않는 한, 데이터가 사라지는 경우).
  • 데이터는 일반 전송 상태와 동일한 규칙에 따라 특수 전송 상태의 셀 A에서 특수 전송 상태의 인접 셀 B로 전달된다.
  • 일반적 및 특수적 전송 상태의 두 하위 집합은 상호 적대적이다.
    • 흥분된 일반 전송 상태에서 시간 t에 셀 A를 부여함
    • 특수 전송 상태에서 셀 B를 가리킴
    • 이때 t+1 세포 B가 지면 상태가 된다. 특수 전송 셀이 "파괴"되었다.
    • 일반적인 전송 상태의 셀에 대한 특수 전송 상태 "인"에서 셀의 경우에도 유사한 시퀀스가 발생할 것이다.

혼합 상태 규칙

다음과 같은 특정 규칙이 결합 상태에 적용된다.

  • 합체 상태는 서로 간에 데이터를 전달하지 않는다.
  • 결합 상태는 하나 이상의 일반적인 전송 상태로부터 입력을 받아, 결합 상태를 향하지 않는 보통 및 특수 전송 상태에 출력을 전달한다.
  • 데이터는 전송 상태 방향 속성에 반하여 전송되지 않는다.
  • 합체 상태에 의해 보유되는 데이터는 합체 상태를 가리키지 않는 인접 전송 상태가 없는 경우 손실된다.
  • 따라서, 혼합 상태 셀은 일반-전송 상태 셀의 전송 라인에서 특수 전송 상태 셀로 "교량"으로 사용된다.
  • 결합 상태는 AND 연산자를 입력에 적용하며, 모든 잠재적 입력이 동시에 흥분되는 경우에만 흥분된 입력을 "저장"한다.
  • 합체 셀은 OTS 셀보다 한 세대 이상 신호를 지연시킨다. 이것은 패리티 제약으로 인해 필요하다.

공사규칙

폰 노이만의 CA에서 만들 수 있는 9가지 세포 타입. 여기서 이진 신호는 9개의 보통 전송선을 따라 통과하며, 마지막에 접지 상태에 부딪힐 때 새로운 셀을 형성한다. 예를 들어, 바이너리 문자열 1011이 다섯 번째 줄에 표시되며, 동방향 특수 전송 상태를 구성한다. 이 프로세스는 이 페이지의 맨 위에 있는 자동화에 사용되는 프로세스와 동일하다. 예를 들어 와이어월드와 달리 인접 와이어 간의 상호작용이 없으므로 컴팩트한 구성 요소 패킹이 가능하다는 점에 유의하십시오.

초기에는 세포 자동화의 우주인 세포 공간의 상당 부분이 "빈칸"으로, 지상 상태 U에 있는 세포로 구성된다. 인접한 통상적 또는 특수 전송 상태에서 입력 팽창을 받으면, 지상 상태의 세포는 "감각"되어 일련의 상태를 거쳐 마침내 정지 상태에서 "휴식"된다.투과 또는 합체 상태를 포함

셀이 도달하는 목적지 상태의 선택은 입력 신호의 순서에 의해 결정된다. 따라서 전환/감지 상태는 지상 상태에서 각 대기 전송 및 혼합 상태로 이어지는 분기 트리의 노드로 생각할 수 있다.

다음 트리에서 입력 순서는 각 단계 후 이진 문자열로 표시된다.

  • 입력된 접지 상태 U의 셀은 다음 사이클(1)에서 S(신규 감작) 상태로 전환된다.
  • 입력되지 않은 S 상태의 셀은 S 상태로0 전환된다(10)
    • 입력되지0 않은 S 상태의 셀은 S00 상태(100)로 전환된다.
      • 입력되지00 않은 S 상태의 셀은 S000 상태(1000)로 전환된다.
        • 입력되지000 않은 S 상태의 셀은 동방향 일반 전송 상태(100)로 전환된다.
        • 입력이 주어지는000 S 상태의 셀은 북쪽 방향의 일반 전송 상태(10001)로 전환된다.
      • 입력된 S00 상태의 셀은 서향 일반 전송 상태(1001)로 전환된다.
    • 입력된 S 상태의0 셀은 S 상태로01 전환된다(101)
      • 입력되지01 않은 S 상태의 셀은 남향 일반 전송 상태(1010)로 전환된다.
      • 입력된01 S 상태의 셀은 동방향 특수 전송 상태(1011)로 전환된다.
  • 입력된 S 상태의 셀은 S 상태로1 전환된다(11)
    • 입력되지1 않은 S 상태의 셀은 S10 상태(110)로 전환된다.
      • 입력되지10 않은 S 상태의 셀은 북쪽 방향 특수 전송 상태(1100)로 전환된다.
      • 입력된 S 상태의10 셀은 서향 특수 전송 상태(1101)로 전환된다.
    • 입력된 S 상태의1 셀은 S 상태로11 전환된다(111).
      • 입력되지11 않은 S 상태의 셀은 남향 특수 전송 상태(110)로 전환된다.
      • 입력된 S 상태의11 셀은 대기 전류 합금 상태 C(111100)로 전환된다.

참고:

  • 동향 또는 북향의 일반적 전송 상태를 구축하기 위해서는 (초기 감작 후 3회의 입력 사이클이 필요한) 입력 사이클이 1회 더 필요하다.
  • 구성을 초래하는 "기본" 대기 전류 상태는 동향 일반 전송 상태로서, 초기 감작성 입력을 필요로 하고 그 다음, 무입력 4 사이클을 필요로 한다.

파괴 규칙

복잡한 패턴을 형성하는 웅크린 "테이프"의 약 4000비트의 데이터. 이것은 Hutton32로 알려진 폰 노이만 세포 자동자의 32개 주 변형을 사용한다.
  • 특수전송 상태 셀에서 합체 상태 셀로의 입력은 합체 상태 셀이 다시 접지 상태로 감소하는 결과를 초래할 것이다.
  • 마찬가지로, 특수 전송 상태 셀에서 일반 전송 상태 셀로 입력하면 일반 전송 상태 셀이 다시 지면 상태로 축소된다.
  • 반대로, 일반 전송 상태 셀에서 특수 전송 상태 셀로의 입력은 특수 전송 상태 셀이 다시 지면 상태로 감소되는 결과를 초래할 것이다.

참고 항목

참조

  • 본 노이만, J., A. W. 버크스(1966년). 자가 생산 오토마타 이론. 일리노이 대학 출판부의 우르바나. [1]

외부 링크