Menu
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?
947
In general, for an imperative language to be Turing-complete, it needs: A form of conditional repetition or conditional jump (e.g., while , if + goto ) A way to read and write some form of storage (e.g., variables, tape)
A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory). So, if somebody says "my new thing is Turing Complete" that means in principle (although often not in practice) it could be used to solve any computation problem.
Typically, one proves a given language is Turing-complete by providing a recipe for translating any given Turing machine program into an equivalent program in the language in question. Alternately, one can provide a translation scheme from another language, one that has already been proven to be Turing-complete.
All digital systems can be constructed by only three basic logic gates. These basic gates are called the AND gate, the OR gate, and the NOT gate. Some textbooks also include the NAND gate, the NOR gate and the EOR gate as the members of the family of basic logic gates.
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.
98
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
