Máy tự động di động Von Neumann – Wikipedia

Posted on by lordneo

Một cấu hình đơn giản trong thiết bị tự động di động của von Neumann. Một tín hiệu nhị phân được truyền đi lặp lại xung quanh vòng dây màu xanh, sử dụng trạng thái truyền thông thường bị kích thích và không hoạt động . Một tế bào hợp lưu nhân đôi tín hiệu trên một chiều dài của dây màu đỏ bao gồm trạng thái truyền đặc biệt . Tín hiệu truyền xuống dây này và xây dựng một ô mới ở cuối. Tín hiệu đặc biệt này (1011) mã cho trạng thái truyền đặc biệt theo hướng đông, do đó kéo dài dây đỏ thêm một ô mỗi lần. Trong quá trình xây dựng, tế bào mới đi qua một số trạng thái nhạy cảm, được định hướng bởi chuỗi nhị phân.

Von Neumann cell automata là biểu hiện ban đầu của automata di động, sự phát triển được nhắc nhở bởi John von Neumann người bạn thân của ông và nhà toán học đồng nghiệp Stanislaw Ulam. Mục đích ban đầu của họ là cung cấp cái nhìn sâu sắc về các yêu cầu logic để tự sao chép máy và được sử dụng trong nhà xây dựng phổ quát của von Neumann.

Máy tự động di động của Nobili là một biến thể của máy tự động di động của von Neumann, được tăng cường khả năng cho các tế bào hợp lưu truyền tín hiệu chéo và lưu trữ thông tin. Cái trước đòi hỏi thêm ba trạng thái, do đó, máy tự động di động của Nobili có 32 trạng thái, thay vì 29. Máy tự động di động của Hutton là một biến thể khác, cho phép một vòng lặp dữ liệu, tương tự như các vòng lặp của Langton, để sao chép.

Định nghĩa [ chỉnh sửa ]

Cấu hình [ chỉnh sửa ]

Nói chung, automata di động (CA) tạo thành một sự sắp xếp của automata trạng thái hữu hạn (FSA) có mối quan hệ vị trí giữa nhau, mỗi FSA trao đổi thông tin với các FSA khác mà nó nằm liền kề nhau. Trong máy tự động di động của von Neumann, các máy trạng thái hữu hạn (hoặc tế bào ) được sắp xếp trong một lưới Cartesian hai chiều và giao diện với bốn ô xung quanh. Vì máy tự động di động của von Neumann là ví dụ đầu tiên sử dụng sự sắp xếp này, nó được gọi là khu phố von Neumann.

Tập hợp các FSA xác định không gian ô có kích thước vô hạn. Tất cả các FSA đều giống hệt nhau về chức năng chuyển trạng thái hoặc bộ quy tắc.

Vùng lân cận (một chức năng nhóm) là một phần của chức năng chuyển trạng thái và định nghĩa cho bất kỳ ô nào tập hợp các ô khác mà trạng thái của ô đó phụ thuộc.

Tất cả các tế bào chuyển trạng thái đồng bộ, theo từng bước với một "đồng hồ" phổ quát như trong một mạch kỹ thuật số đồng bộ.

Các tiểu bang [ chỉnh sửa ]

Mỗi FSA của không gian tế bào von Neumann có thể chấp nhận bất kỳ trong số 29 trạng thái của bộ quy tắc. Bộ quy tắc được nhóm thành năm tập hợp con trực giao. Mỗi trạng thái bao gồm màu của ô trong chương trình automata di động Golly in (đỏ, lục, lam). họ đang

  1. a ground state U (48, 48, 48)
  2. quá trình chuyển đổi hoặc )
    1. S (mới được nhạy cảm) (255, 0, 0)
    2. S 0 – (đã nhạy cảm, không nhận được đầu vào trong một chu kỳ) (255, 125, 0 )
    3. S 00 – (nhạy cảm, không nhận được đầu vào trong hai chu kỳ) (255, 175, 50)
    4. S 000 – ( được nhạy cảm, không nhận được đầu vào trong ba chu kỳ) (251, 255, 0)
    5. S 01 – (đã nhạy cảm, không nhận được đầu vào nào trong một chu kỳ và sau đó là đầu vào cho một chu kỳ) (255, 200, 75)
    6. S 1 – (nhạy cảm, đã nhận được đầu vào cho một chu kỳ) (255, 150, 25)
    7. S 10 – (được nhạy cảm, đã nhận được đầu vào trong một chu kỳ và sau đó không có đầu vào cho một chu kỳ) (255, 255, 100)
    8. S 11 – (đã được nhạy cảm, đã nhận được đầu vào cho hai chu kỳ) (255, 250, 125)
  3. hợp lưu (trong 4 trạng thái kích thích)
    1. C 00 – không hoạt động (và cũng sẽ được kiểm tra chu kỳ tiếp theo) (0, 255, 128)
    2. C 01 – tiếp theo , nhưng sẽ bị kích thích theo chu kỳ tiếp theo) (33, 215, 215)
    3. C 10 – bị kích thích (nhưng sẽ không hoạt động theo chu kỳ tiếp theo) (255, 255, 128)
    4. C 11 – phấn khích tiếp theo phấn khích (hiện đang phấn khích và sẽ được kích thích chu kỳ tiếp theo) (255, 128, 64)
  4. đường truyền thông thường trạng thái (theo 4 hướng, bị kích thích hoặc không hoạt động, tạo thành 8 trạng thái)
    1. Hướng về phía Bắc (phấn khích và không hoạt động) (36, 200, 36) (106, 106, 255)
    2. Hướng về phía Nam (phấn khích và không hoạt động) (106, 255, 106) (139, 139, 255)
    3. Hướng tây (phấn khích và không hoạt động) (73, 255, 73) (122, 122, 255)
    4. Hướng đông (phấn khích và yên tĩnh) (27, 176, 27) (89, 89, 255)
  5. đường truyền đặc biệt (theo 4 hướng, bị kích thích hoặc không hoạt động, tạo thành 8 trạng thái)
    1. Hướng về phía Bắc (phấn khích và không hoạt động) (191, 73, 255) (255, 56, 56)
    2. Hướng về phía Nam (phấn khích và không hoạt động) (203, 106, 255) (255, 89, 89)
    3. Hướng tây (phấn khích và không hoạt động) (197, 89, 255) (255, 73, 73)
    4. Hướng đông (phấn khích và không hoạt động) (185, 56, 255) (235, 36, 36)

Các trạng thái "Vui mừng" mang dữ liệu, với tốc độ một bit trên mỗi bước chuyển trạng thái.

Lưu ý rằng các trạng thái hợp lưu có đặc tính trễ một chu kỳ, do đó có hiệu quả giữ hai bit dữ liệu tại bất kỳ thời điểm nào.

Quy tắc trạng thái truyền [ chỉnh sửa ]

Luồng bit giữa các ô được chỉ định bởi thuộc tính hướng. Các quy tắc sau được áp dụng:

  • Các trạng thái truyền áp dụng toán tử OR cho các đầu vào, nghĩa là một ô ở trạng thái truyền (thông thường hoặc đặc biệt) sẽ bị kích thích tại thời điểm t + 1 nếu bất kỳ của các đầu vào trỏ theo đó nó bị kích thích vào thời điểm t
  • Dữ liệu truyền từ ô A ở trạng thái truyền thông thường sang một ô liền kề B ở trạng thái truyền thông thường, theo đến thuộc tính chỉ đạo của A (trừ khi B cũng được chuyển hướng tới A trong trường hợp đó dữ liệu biến mất).
  • Dữ liệu truyền từ ô ] ở trạng thái truyền đặc biệt đến một ô liền kề B ở trạng thái truyền đặc biệt, theo các quy tắc tương tự như đối với trạng thái truyền thông thường.
  • Hai tập hợp con của trạng thái truyền, thông thường và đặc biệt, là đối kháng lẫn nhau:
    • Cho một ô A tại thời điểm t ở trạng thái truyền thông thường bị kích thích
    • chỉ vào một ô B trong bất kỳ trạng thái truyền đặc biệt nào
    • tại thời điểm t + 1 ô B sẽ trở thành trạng thái cơ bản. Tế bào truyền đặc biệt đã bị "phá hủy".
    • một chuỗi tương tự sẽ xảy ra trong trường hợp một tế bào ở trạng thái truyền đặc biệt "trỏ" đến một tế bào ở trạng thái truyền thông thường

Quy tắc trạng thái hợp lưu chỉnh sửa ]

Các quy tắc cụ thể sau đây áp dụng cho các trạng thái hợp lưu:

  • Các trạng thái hợp lưu không truyền dữ liệu lẫn nhau.
  • Các trạng thái kết hợp lấy đầu vào từ một hoặc nhiều trạng thái truyền thông thường và cung cấp đầu ra cho các trạng thái truyền, thông thường và đặc biệt, không hướng đến trạng thái hợp lưu. [19659018] Dữ liệu không được truyền theo thuộc tính hướng trạng thái truyền.
  • Dữ liệu được giữ bởi trạng thái hợp lưu sẽ bị mất nếu trạng thái đó không có trạng thái truyền liền kề cũng không được chỉ ra ở trạng thái hợp lưu.
  • Do đó, các ô trạng thái hợp lưu được sử dụng làm "cầu nối" từ các đường truyền của các tế bào trạng thái truyền thông thường đến đặc biệt.
  • Trạng thái hợp lưu áp dụng toán tử AND cho các đầu vào, chỉ "tiết kiệm" một đầu vào bị kích thích nếu tất cả các đầu vào tiềm năng được kích thích đồng thời. Các tế bào kết hợp làm chậm tín hiệu bởi một thế hệ nhiều hơn các tế bào OTS; điều này là cần thiết do các ràng buộc tương đương.

Quy tắc xây dựng [ chỉnh sửa ]

Chín loại tế bào có thể được xây dựng trong CA của von Neumann. Ở đây, tín hiệu nhị phân truyền dọc theo chín đường truyền thông thường, xây dựng một ô mới khi chúng gặp trạng thái cơ bản ở cuối. Ví dụ, chuỗi nhị phân 1011 được hiển thị trên dòng thứ năm và xây dựng trạng thái truyền đặc biệt theo hướng đông – đây là quy trình tương tự như được sử dụng trong máy tự động ở đầu trang này. Lưu ý rằng không có sự tương tác giữa các dây lân cận, chẳng hạn như trong Thế giới dây chẳng hạn, cho phép đóng gói các thành phần nhỏ gọn.

Ban đầu, phần lớn không gian tế bào, vũ trụ của máy tự động di động, "trống", bao gồm các tế bào ở trạng thái cơ bản U . Khi được kích thích đầu vào từ trạng thái truyền thông thường hoặc đặc biệt lân cận, tế bào ở trạng thái cơ bản trở nên "nhạy cảm", chuyển qua một loạt trạng thái trước khi cuối cùng "nghỉ ngơi" ở trạng thái truyền tĩnh hoặc hợp lưu.

Việc lựa chọn trạng thái đích mà ô sẽ đạt được được xác định bởi chuỗi tín hiệu đầu vào. Do đó, các trạng thái chuyển tiếp / nhạy cảm có thể được coi là các nút của cây phân nhánh dẫn từ trạng thái cơ bản đến từng trạng thái truyền và trạng thái hợp lưu.

Trong cây sau, chuỗi đầu vào được hiển thị dưới dạng chuỗi nhị phân sau mỗi bước:

  • một tế bào ở trạng thái cơ bản U được cung cấp đầu vào, sẽ chuyển sang trạng thái S (mới được nhạy cảm) trong chu kỳ tiếp theo (1)
  • một tế bào trong trạng thái S không có đầu vào, sẽ chuyển sang trạng thái S 0 (10)
    • một tế bào ở trạng thái S 0 không có đầu vào, sẽ chuyển sang trạng thái S 00 (100)
      • một tế bào ở trạng thái S 00 không có đầu vào, sẽ chuyển sang trạng thái S 000 (1000)
        • một tế bào ở trạng thái S 000 không có đầu vào, sẽ chuyển sang trạng thái truyền thông thường theo hướng đông (10000)
        • một tế bào trong S 000 trạng thái, được cung cấp đầu vào, sẽ chuyển sang trạng thái truyền thông thường theo hướng bắc (10001)
      • một tế bào ở trạng thái S 00 được cung cấp một đầu vào, sẽ chuyển sang trạng thái truyền thông thường theo hướng tây (1001)
    • một tế bào ở trạng thái S 0 được đưa vào một đầu vào, sẽ chuyển sang trạng thái S 01 (101)
      • một tế bào ở trạng thái S 01 không có đầu vào, sẽ chuyển sang trạng thái truyền thông thường theo hướng nam (1010)
      • một tế bào trong S 01 trạng thái, được cung cấp đầu vào, sẽ chuyển sang trạng thái truyền đặc biệt theo hướng đông (1011)
  • một tế bào trong S trạng thái, được cung cấp một đầu vào, sẽ chuyển sang trạng thái S 1 (11)
    • một tế bào ở trạng thái S 1 không có đầu vào, sẽ chuyển sang trạng thái S 10 (110)
      • một tế bào ở trạng thái S 10 không có đầu vào, sẽ chuyển sang trạng thái truyền đặc biệt theo hướng bắc (1100)
      • một tế bào trong S [19459026Trạngthái10 được cung cấp đầu vào, sẽ chuyển sang trạng thái truyền đặc biệt theo hướng tây (1101)
    • một tế bào ở trạng thái S 1 được cung cấp một đầu vào, sẽ chuyển sang trạng thái S 11 (111)
      • một tế bào ở trạng thái S 11 không có đầu vào, sẽ chuyển sang trạng thái truyền đặc biệt theo hướng nam (1110)
      • một tế bào trong S [19459026Trạngthái11 được cung cấp đầu vào, sẽ chuyển sang trạng thái hợp lưu tĩnh C 00 (1111)

Lưu ý rằng:

  • cần thêm một chu kỳ đầu vào (bốn sau độ nhạy ban đầu) để xây dựng trạng thái truyền thông thường theo hướng đông hoặc bắc so với bất kỳ trạng thái nào khác (yêu cầu ba chu kỳ đầu vào sau độ nhạy ban đầu), [19659018] trạng thái không hoạt động "mặc định" dẫn đến việc xây dựng là trạng thái truyền thông thường theo hướng đông – yêu cầu đầu vào nhạy cảm ban đầu, và sau đó bốn chu kỳ không có đầu vào.

Quy tắc phá hủy [ chỉnh sửa ]

Khoảng 4000 bit dữ liệu trong một "băng" cuộn tròn xây dựng một mô hình phức tạp. Điều này sử dụng một biến thể 32 trạng thái của tự động di động von Neumann được gọi là Hutton32.

  • Một đầu vào vào một tế bào trạng thái hợp lưu từ một tế bào trạng thái truyền đặc biệt sẽ dẫn đến việc tế bào trạng thái hợp lưu bị giảm trở lại trạng thái cơ bản.
  • Tương tự như vậy, một đầu vào vào một tế bào trạng thái truyền thông thường từ một tế bào đặc biệt tế bào trạng thái truyền dẫn sẽ dẫn đến việc tế bào trạng thái truyền thông thường bị giảm trở lại trạng thái cơ bản.
  • Ngược lại, một đầu vào vào một tế bào trạng thái truyền đặc biệt từ một tế bào trạng thái truyền thông thường sẽ dẫn đến trạng thái truyền đặc biệt tế bào bị giảm trở lại trạng thái cơ bản.

Xem thêm [ chỉnh sửa ]

Tài liệu tham khảo [ chỉnh sửa ] ]

  • Von Neumann, J. và A. W. Burks (1966). Lý thuyết về automata tự tái tạo. Urbana, Nhà xuất bản Đại học Illinois. [1]

Liên kết ngoài [ chỉnh sửa ]