turing-complete - 图灵完整性需要哪些逻辑门？

Question

我儿子最近一直在玩Little Big Planet 2，我注意到游戏编辑器允许AND门，OR门和NOT门...图灵完成了吗？如果是这样，那么有人可以推荐一个学习这些原始内容的条件的资源吗？

Answer 1

您不需要，并且不需要AND或OR之一即可执行所有二进制逻辑。
基本上是DeMorgan's Law。
但是，这对于图灵完整性来说是不够的。
为此，您还需要随机(或等效地减少)访问权限
(理论上)无限内存。
奇怪的是，您将能够构建触发器(D flip flop
是使用NAND构建的，因此很简单)
可用的逻辑门。从这些，您可以建立一个
注册，并为您提供足够的装备
构建一些简单的程序。