Con trai tôi đã chơi Little Big Planet 2 gần đây, và tôi nhận thấy rằng trình chỉnh sửa trò chơi cho phép VÀ cổng, HOẶC cổng và KHÔNG cổng ... Có phải Turing đã hoàn thành? Nếu vậy, bất cứ ai có thể giới thiệu một nguồn cho việc học để biến những nguyên thủy thành một cái gì đó giống như một mức độ cao hơn có điều kiện nếu?Cổng logic nào cần cho Turing đầy đủ?
Ý tưởng: bạn sẽ có thể xây dựng một NAND gate, vì vậy, bạn có thể xây dựng a XOR gate. Với XOR và AND bạn có thể tạo một half-adder. Kết hợp một nửa người bổ sung để tạo một full-adder. Đó sẽ là một khởi đầu ít nhất.
NAND và NOR là các khối xây dựng cơ bản cho cửa khác rất có thể là Turing completeness is just around the corner.
cũng là một subtractor, để làm so sánh, và có lẽ flip-flop mạch để lưu trữ dữ liệu. –
AND, OR và NOT là functionally complete, có nghĩa là, tất cả các bảng sự thật có thể có thể được bày tỏ. Mà tôi tin rằng cũng làm cho nó turing hoàn thành, kể từ khi bạn có thể xây dựng một bộ xử lý mục đích chung với bất kỳ chức năng hoàn thành bộ cổng
Một cổng nand là tất cả những gì cần thiết, tất cả mọi thứ có thể được xây dựng từ đó, vì vậy ba bạn có rất nhiều. Đây là khóa học đưa bạn đến các cổng logic, thông qua xây dựng một máy tính, tất cả cách để viết hệ điều hành: The Elements of Computing Systems: Building a Modern Computer from First Principles
Liên kết được tham chiếu giờ đây trỏ tới http://www.nand2tetris.org/ (Cảm ơn liên kết đó!) – DukeZhou
Bạn KHÔNG cần và một trong VÀ HOẶC để có thể thực hiện tất cả logic nhị phân. Đây là cơ bản là DeMorgan's Law.
Tuy nhiên, điều này là không đủ cho Turing đầy đủ. Đối với điều đó, bạn cũng cần truy cập ngẫu nhiên (hoặc giảm tương đương) (về mặt lý thuyết) bộ nhớ vô hạn.
Tỷ lệ là, bạn sẽ có thể xây dựng một flip flop (D flip flop được xây dựng bằng cách sử dụng NAND, do đó dễ dàng) sử dụng các cổng logic có sẵn. Từ đó, bạn có thể tạo một thanh ghi và với đủ số lượng bạn sẽ được trang bị để xây dựng một số chương trình đơn giản.
Đặc tả của hệ thống bộ nhớ, đặc biệt là bộ nhớ truy cập ngẫu nhiên không cần thiết để chứng minh tính hoàn chỉnh. Xem phép tính kết hợp SKI. http://en.wikipedia.org/wiki/SKI_combinator_calculus – mcandre
Tập hợp các máy có thể được xác định bằng cách sử dụng một số lượng hữu hạn các cổng logic là một tập hợp con của tập các máy có thể được xây dựng như tự động xác định hữu hạn. – Patrick87
Các cửa duy nhất bạn cần là KHÔNG và OR. Với hai bạn có thể xây dựng tất cả các cổng logic khác. Ví dụ, NOT (OR (NOT | NOT)) là một cổng AND, OR (NOT | NOT) là NAND, NOT (OR()) là NOR, vv. Khó thực hiện (và cũng hữu ích nhất về mặt chức năng) là XOR, có thể được thực hiện với một cây cổng NAND, mà lần lượt có thể được thực hiện với NOT và OR như được hiển thị ở trên.
Tôi biết tôi đến trễ để các trò chơi ở đây nhưng có. Tôi chơi LBP2, và nó có AND, OR, NOT, XOR, NAND, NOR. Bạn cũng có thể cộng và trừ tín hiệu, cũng có cách để thực hiện nhị phân trong trò chơi.
+1 for nerdiness. – delnan
Tôi không biết về BP2, nhưng mọi người đã làm những việc điên rồ với minecraft như ALU này: https://www.youtube.com/watch?v=0CN6USEIkwU – jjmontes