图灵完整性需要什么逻辑门？

Question

我的儿子最近一直在玩Little Big Planet 2,我注意到游戏编辑器允许AND门,OR门和NOT门......图灵是否完整？如果是这样,任何人都可以推荐一个学习如何将这些原语转换为更高级别条件的来源吗？

Answer 1

您需要NOT和AND或OR中的一个才能执行所有二进制逻辑.这基本上就是德摩根定律.

但是,这对图灵完整性来说还不够.为此,您还需要随机(或可还原等效)访问(理论上)无限内存.

可能的情况是,您将能够 使用可用的逻辑门构建一个触发器(使用NAND构建D触发器,因此很容易).从那些,您可以建立一个寄存器,并有足够的那些你将配备来构建一些简单的程序.

Answer 2

只需要一个nand门,所有东西都可以通过它构建,所以你拥有的三个就足够了.这是一门课程,带您从逻辑门,到建立计算机,一直到编写操作系统:计算系统的要素:从第一原则构建现代计算机

Answer 3

一个想法：你应该能够构建一个与非门，这样你就可以构建一个异或门。使用 XOR 和 AND，您可以构建一个半加器。组合半加器来构建全加器。这至少是一个开始。

NAND 和 NOR 是其他门的基本构建块，因此图灵完整性可能指日可待。