What logic gates are required for Turing completeness?

turing-complete
dicroce picture dicroce · Feb 5, 2011 · Viewed 12k times · Source

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

Kevin Montrose picture Kevin Montrose · Feb 5, 2011

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.

Related questions

What is Turing Complete?

What does the expression "Turing Complete" mean? Can you give a simple explanation, without going into too many theoretical details?

Read More
Is CSS Turing complete?

CSS isn't, insofar as I know, Turing complete. But my knowledge of CSS is very limited. Is CSS Turing complete? Are any of the existing draft or committees considering language features that might enable Turing completeness if it isn't right …

Read More
C++ templates Turing-complete?

I'm told that the template system in C++ is Turing-complete at compile time. This is mentioned in this post and also on wikipedia. Can you provide a nontrivial example of a computation that exploits this property? Is this fact useful …

Read More