チューリングの完全性のためにはどのような論理ゲートが必要ですか？

Question

最近私の息子はLittle Big Planet 2をプレイしていましたが、ゲームエディタではANDゲート、ORゲート、NOTゲートが可能です。もしそうなら、誰もがそれらのプリミティブをより高いレベルの条件付きのようなものに変えることを学ぶためのソースを推薦することができますか？

Answer 1

NAND gateを構築できるので、a XOR gateを作成することができます。 XORとANDで、half-adderを構築することができます。半加算器を組み合わせてfull-adderを構築します。それは少なくとも始まりになるだろう。

NANDとNORは他のゲートの基本的なビルディングブロックなので、チャンスはTuring completeness is just around the cornerです。

Answer 2

AND、ORおよびNOTはfunctionally completeです。つまり、すべての可能な真理値表を表現できます。機能的に完全なゲートセットを備えた汎用プロセッサを構築することができるので、私はこれも完全にチューリングします。

Answer 3

ナンドゲートはすべて必要です。すべてがそれから構築できます。たくさん。ここでは、アップコンピュータを構築して、論理ゲートからオペレーティングシステムを書くまでずっとあなたを取るのコースです：The Elements of Computing Systems: Building a Modern Computer from First Principles

Answer 4

あなたがする必要はないとの1つのANDやORすべてのバイナリのロジックを行うことができるように。 これは基本的にDeMorgan's Lawです。

ただし、これはチューリングの完全性では不十分です。 そのためには、ランダム（または縮小可能）のアクセス （理論的には）無限のメモリが必要です。

オッズは、あなたが（D flip flop は、その簡単なので、のNANDを使用して構築されている） 可能な論理ゲートを使用してフリップフロップを構築することができるでしょう、です。それらから、 レジスタを構築することができ、それらのうちのいくつかで簡単なプログラムを構築するために が装備されます。

Answer 5

必要なゲートは、NOTとORだけです。これらの2つで、他のすべての論理ゲートを構築することができます。例えば、NOT（OR（NOT | NOT））はANDゲートで、OR（NOT | NOT）はNAND、NOT（OR（））はNORなどです。 XORは、NANDゲートのツリーで作ることができ、上で示したようにNOTとORで作ることができます。

Answer 6

私はここにゲームに遅れていると知っています。私はLBP2をプレイし、AND、OR、NOT、XOR、NAND、NORを持っています。また、信号を加算したり減算したりすることもできますし、ゲームでバイナリを行う方法もあります。