Ai đó có thể giải thích Quy tắc 110 theo cách đơn giản nhất có thể không?

Question

Tôi không thể che đầu quanh những gì the Wikipedia article hoặc the answer here. Ai đó có thể giải thích Quy tắc 110 bằng các thuật ngữ đơn giản không? Làm thế nào để đảm bảo Turing đầy đủ?

Answer 1

Tôi sẽ tìm hiểu kỹ hơn: Tôi không nghĩ rằng bạn đang tìm kiếm thêm chi tiết về bằng chứng đã khá phức tạp trong bài viết, mặc dù nó bỏ qua rất nhiều chi tiết.

Để báo giá từ article you cite: "Trong một ô tô sơ cấp, mô hình một chiều 0 và 1 phát triển theo một bộ quy tắc đơn giản. Một điểm trong mẫu sẽ là 0 hoặc 1 phụ thuộc vào Thế hệ mới về giá trị hiện tại của nó, cũng như của hai nước láng giềng của nó. Quy tắc 110 automaton có bộ quy tắc sau đây ... " (xem wikipedia table sau)

Điểm bắt đầu, mà bạn có thể xem như dữ liệu, nhưng có thể được lấy làm đại diện cho mã (biểu diễn mã như dữ liệu là cần thiết cho bất kỳ bằng chứng nào về Turing-đầy đủ; điều này quay lại kết quả ban đầu của Turing), là một chuỗi số 0 và 1, thường, nhưng không necessari ly, được bao quanh trên cả hai mặt bởi các ô chứa chỉ 0. Quy tắc 110 cho thấy trình tự phát triển như thế nào. Ví dụ, nếu có một mẫu của 3 1 trong một hàng, giữa 1 sẽ "chết" (biến thành 0) trong hàng tiếp theo. Điều gì xảy ra với hai người hàng xóm của nó phụ thuộc vào cách mô hình mở rộng ra ngoài chúng. Các biểu đồ hình tam giác mà bạn thấy là một biểu diễn đồ họa về sự tiến hóa của automaton từ trạng thái ban đầu, mã hóa 1 là màu đen và 0 là màu trắng và biểu diễn sự tiến hóa từ trên xuống dưới. Trạng thái ban đầu thường có độ dài rất ngắn để cho thấy các mô hình rất phức tạp có thể tiến hóa như thế nào từ các trạng thái ban đầu đơn giản.

Hai tính năng khác thường của bằng chứng về Turing đầy đủ là trước hết, quy tắc rất đơn giản này có thể làm mọi thứ mà ngôn ngữ lập trình yêu thích của bạn có thể thực hiện được. là bằng chứng đòi hỏi một nền lặp lại dài vô hạn để làm phép thuật của nó. Tôi không thể nhìn thấy bất cứ điều gì về cơ bản không trung thực về điều này mặc dù; không nhiều hơn so với giả sử một băng trống vô hạn hoặc bán vô hạn tiềm tàng, như Turing ban đầu đã làm.

Để hiểu bằng chứng đúng, bạn cần nắm bắt cách dữ liệu (và sau này, mã) được mã hóa trong mẫu bắt đầu và có vẻ như sự quen thuộc với hệ thống thẻ tuần hoàn sẽ giúp ích rất nhiều. Tôi không phải là người giải thích chúng.

Mặc dù có vẻ khó khăn hơn để hiểu tình hình với một ô tô di động 2-D, chẳng hạn như Conway's "Game of Life", tôi thấy nó có tính hướng dẫn để chơi với trò chơi đó, học "tàu lượn", "súng lượn" và "xe lửa" và những công trình thú vị khác. (Một con tàu phun lửa xây dựng các khẩu súng lượn và một con tàu lượn bắn những chiếc tàu lượn). Đây có thể được sử dụng để thiết lập Turing-đầy đủ cho automaton này là tốt.

Bạn cũng có thể tìm thấy thông tin talk page (bạn không đơn độc trong việc không nắm bắt được điểm, xem mục nhập bắt đầu "hình ảnh không có ý nghĩa gì đối với tôi ..").

Answer 2

nỗ lực của tôi tại một gọn gàng, của giáo dân về lời giải thích:

• Rule 110 là một automaton tế bào tiểu học: một quy tắc cho việc chuyển đổi một mô hình hữu hạn trong tổng số 1 và 0 của vào một mô hình của 1 và 0 của.
• Khi quy tắc 110 được áp dụng lặp lại trên một số chuỗi đầu vào nhất định, các mẫu sẽ xuất hiện tùy thuộc vào các chuỗi con được tìm thấy trong các bit đầu vào. Với đủ lần lặp lại, những điều sau có thể xảy ra:
  • Chuỗi con gốc xuất hiện ở cùng vị trí như trong mục nhập ban đầu.
  • Chuỗi phụ gốc được giữ nguyên nhưng 'di chuyển' đến một vị trí khác trong bitfield.
  • Hai chuỗi phụ di chuyển về phía nhau tương tác và 'truyền qua' nhau.
  • Hai chuỗi phụ kết hợp để tạo chuỗi phụ mới.
• Các chuỗi phụ khác nhau có thể có ý nghĩa tượng trưng như '1', '0', 'xung nhịp' hoặc 'quy tắc sản xuất' tương ứng với các phần tử của hệ thống thẻ tuần hoàn.
• Với nhiều lần lặp lại Quy tắc 110 trên trường bit đầu vào được xây dựng cẩn thận, tương tác của các chuỗi con mô phỏng hành vi của một hệ thống thẻ tuần hoàn.
• Một hệ thống thẻ tuần hoàn có thể được sử dụng để mô phỏng một máy Turing phổ dụng. Do đó, một hệ thống thẻ tuần hoàn là Turing-complete.
• Vì quy tắc 110 có thể mô phỏng một hệ thống thẻ tuần hoàn, nó cũng là Turing-complete.

Answer 3

Năm 1970, John Conway đã phát minh Game of Life.

Kể từ đó, tôi nghĩ hầu như mọi lập trình viên đều cố gắng viết việc triển khai của nó - tôi chắc chắn đã làm từ lâu rồi, và nó rất thú vị.

Trò chơi này thực sự là cellular automaton, đặt quy tắc đơn giản giữa các thế hệ ô trong mặt phẳng 2 chiều vô hạn. Ví dụ, nếu trong ô thế hệ hiện tại có ít hơn 2 hàng xóm còn sống (giá trị bit 1), thì nó sẽ chết trong thế hệ tiếp theo của sự cô đơn. Nếu nó có hơn 3 người hàng xóm còn sống, nó sẽ chết vì quá đông đúc. Nếu ô trống (bit giá trị 0, hoặc đã chết) có chính xác 3 hàng xóm, nó sẽ khiến nó được sinh ra (trở thành 1).

Kể từ đó, người ta thấy rằng Game of Life phức tạp đáng kinh ngạc - nó có thể tạo ra rất nhiều mô hình rất phức tạp tiếp tục phát triển. Ngoài ra, nó đã được chỉ ra rằng nó là Turing-hoàn thành, có nghĩa là, bạn có thể mã hóa các thuật toán phức tạp tùy ý bằng cách sử dụng kết hợp tế bào bắt đầu như một chương trình, và kết hợp cuối cùng như là một kết quả. Tuy nhiên, phải mất vài năm để tìm cách tạo ra các biểu mẫu phức tạp như gliders or guns.

Bây giờ trở lại quy tắc 110 là gì. Nói một cách đơn giản, quy tắc 110 là biến thể một chiều của Game of Life.

110 chỉ là biểu thị số thập phân của chuỗi nhị phân 01101110 là dạng hệ thống quy tắc ngắn về cách thế hệ hiện tại của ô (bit) sẽ là translated into next one, tương tự như hệ thống quy tắc của Game of Life chết vì cô đơn hoặc quá tải và được sinh ra có chính xác ba người hàng xóm.

Giống như Game of Life, nó đã được chứng minh rằng quy tắc 110 là Turing-complete. Bạn có thể mã hóa thuật toán phức tạp tùy ý bằng cách sử dụng các ô bắt đầu (bit) kết hợp như chương trình của bạn, và kết quả là các bit cuối cùng kết hợp.

Answer 4

An thực hiện trong python:

(Hãy adviced: lập trình python thực tế sẽ giết bạn cho việc này)

import time 

seed = raw_input("Feed me a string! (At least 3 characters long please)\n>") 

lastline = '>' 
iterator = 0 

while (iterator<len(seed)): 
    temp = (ord(seed[iterator]))%2 
    if (temp == 1): 
     lastline += '#' 
    else: 
     lastline += ' ' 
    iterator += 1 

stop = 0 
while (stop != 1): #Keep printing as long as CTRL-C isn't pressed 
    #dummy = raw_input(lastline) 
    print lastline 
    iterator = 0 
    nextline = '>' 


    while (iterator<len(seed)): #Convert entire string 

     if (len(seed) < 3): # if wrong 
      print "You had ONE JOB!" 
      stop = 1 

     elif (iterator == 0): # if at start 
      if (lastline[1] == ' '): 
       nextline += ' ' 
      else: 
       nextline += '#' 

     elif (iterator+1 == len(seed)): # if at end 
      if (lastline[iterator+1] == ' '): 
       nextline += ' ' 
      else: 
       nextline += '#' 

     else: #if in middle 
      if (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #111 
       nextline += ' ' 
      elif (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #110 
       nextline += '#' 
      elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #101 
       nextline += '#' 
      elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == ' '): #100 
       nextline += ' ' 
      elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #011 
       nextline += '#' 
      elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #010 
       nextline += '#' 
      elif (lastline[iterator] == ' ' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #001 
       nextline += '#' 
      else: # (lastline[iterator-1] == ' ' and lastline[iterator] == ' ' and lastline[iterator+1] == ' '): #000 
       nextline += ' ' 

     iterator += 1 

    lastline = nextline 
    time.sleep(0.02)