Turing-Complete Rule 110 trên Bitcoin

bởi Phương Anh

Bài viết này ban đầu xuất hiện trên Medium , và chúng tôi tái bản với sự cho phép từ Xiaohui Liu.

Chúng tôi đã triển khai  Quy tắc 110  trên Bitcoin. Tương tự như tự động dữ liệu di động hai chiều (CA)  Trò chơi cuộc sống của Conway , Quy tắc 110, CA một chiều, cũng hoàn chỉnh Turing. Bằng cách suy diễn, chúng tôi đã chỉ ra rằng Bitcoin là Turing Complete, một lần nữa .

Quy tắc 110

250 lần lặp lại quy tắc 110
250 lần lặp lại quy tắc 110

Cơ chế tự động di động Quy tắc 110 là CA cơ bản 1 chiều, trong đó mẫu tuyến tính gồm các số 0 và 1 phát triển theo một tập hợp các quy tắc đơn giản. Việc một điểm trong mẫu sẽ là 0 hay 1 trong thế hệ mới phụ thuộc vào giá trị hiện tại của nó và giá trị của hai điểm lân cận của nó. Quy tắc 110 có bộ quy tắc sau:

Quy tắc 110
Quy tắc 110

Tên “Quy tắc 110” dựa trên thực tế là quy tắc này có thể được tóm tắt trong chuỗi nhị phân 01101110, tương ứng với giá trị thập phân 110.

Hoạt ảnh của Quy tắc 110
Hoạt ảnh của Quy tắc 110

Turing-Complete

Mặc dù đơn giản, Quy tắc 110 vẫn hoàn chỉnh, như đã được chứng minh trong Tính  phổ biến trong Dữ liệu tự động di động cơ bản  (Cook 2004). Điều này ngụ ý rằng, về nguyên tắc, nó có thể mô phỏng bất kỳ phép tính hoặc chương trình máy tính nào. Quy tắc 110 được cho là hệ thống hoàn chỉnh Turing đơn giản nhất được biết đến.

Thực hiện

Chúng tôi đã triển khai Quy tắc 110, theo cách tiếp cận tương tự để triển khai Trò chơi cuộc sống.

Quy tắc 110
Quy tắc 110

0 bình luận

Có thể bạn quan tâm

Để lại bình luận