What logic gates are required for Turing completeness?

Question

My son has been playing Little Big Planet 2 lately, and I noticed that the game editor allows AND gates, OR gates and NOT gates... Is it Turing complete? If so, can anyone recommend a source for learning to turn those primitives into something like a higher level conditional if?

Answer 1

An idea: you should be able to construct a NAND gate, so you can then build a XOR gate. With XOR and AND you can build a half-adder. Combine half-adders to build a full-adder. That would be a start at least.

NAND and NOR are basic building blocks for other gates so chances are Turing completeness is just around the corner.

Answer 2

AND, OR and NOT is functionally complete, that is, all possible truth tables can be expressed. Which I believe also makes it turing complete, since you can construct a general purpose processor with any functionally complete set of gates

Answer 3

A NAND gate is all that is required, everything can be built from that, so the three you have are plenty. Here's a course that takes you from logic gates, up through building a computer, all the way to writing an operating system: The Elements of Computing Systems: Building a Modern Computer from First Principles

Answer 4

You need NOT and one of AND or OR to be able to do all binary logic. This is DeMorgan's Law, basically.

However, this is not sufficient for Turing completeness. For that you also need random (or reducably equivalent) access (theoretically) infinite memory.

Odds are, you'll be able to build a flip flop (a D flip flop is built using NANDs, so it's straightforward) using the available logic gates. From those, you can build a register, and with enough of those you'll be equipped to build some simple programs.

Answer 5

You can build logic circuit of any complexity with either NAND or NOR gates.

NAND is an AND with a NOT on the output pin.

NOR is an OR with a NOT on the output pin.

Any NAND-based circuit can be rebuilt using NOR's exclusively and vice versa.

So, you can build any logic circuit given only NAND gates. Or you can use just NOR gates. Or you can use NOT and AND gates. Or you can use NOT and OR gates. Or, you can also use AND, NOT and OR gates: you can certainly reduce the number of transistors by creating an optimal combination by using all three types of gates.

All this can be proven by boolean algebra using truth tables: any combination of truth tables can be built from a combination of above mentioned gates. When there are two inputs, there are 4 possible combinations of inputs, giving 16 possible truth tables. By using combinations of above mentioned gates you can create all of these 16 truth tables, and so, you don't need 16 different gates. This holds when you add more inputs and outputs, and even when you create registers and latches to create memory bits, CPU registers and/or any sequential logic circuits.

https://en.wikipedia.org/wiki/NAND_logic

https://en.wikipedia.org/wiki/NOR_logic

https://en.wikipedia.org/wiki/Truth_table

Answer 6

I'm know I'm late to the game here but yes. I play LBP2, and it has an AND, OR, NOT, XOR, NAND, NOR. You can also add and subtract signals, there is also ways to do binary in the game.

Answer 7

The only gates you need are NOT and OR. With those two you can build all other logic gates. For example, NOT(OR(NOT|NOT)) is an AND gate, OR(NOT|NOT) is NAND, NOT(OR()) is NOR, etc. The difficult one to make (and also most functionally useful) is XOR, which can be made with a tree of NAND gates, which in turn can be made with NOT and OR as shown above.

Answer 8

Theoretically speaking, an infinite number of NAND (inverted AND) logic gates can be used to build a Turing machine. This is because NAND and NOR are the universal logic gates.

In the real world, one can never build a Turing complete machine because infinite memory does not exist.

That's why all computers today are deterministic Finite State Machines.

Modern computers can be considered approximations of Turing machines to aid in program analysis.