Turing Machines

Alan Turing (1912-1954) was a British mathematician, logician, and a major contributor to mathematics, cryptanalysis, computer science, and artificial intelligence. He invented the universal Turing machine, an abstract computing machine that encapsulates the fundamental logical principles of the digital computer. Turing played a crucial role in cracking intercepted coded messages during World War II, enabling the Allies to defeat the Axis powers in many crucial engagements.

Alan invented the concept of a "Turing Machine", which is an abstract definition of computation. A machine or programming language is said to be Turing Complete (or a Universal Turing Machine) if every possible programming language or application can be written in it. NOTE: Not every machine that is Turing Complete is a Universal Turing Machine.

Some interesting Turing Complete machines:

• Conway's Game of Life
• Magic the Gathering Card Game
• The NAND Gate. By repeating this simple logical gate, you can create any other logic gate, and thus any computer in the world. In fact, NAND to TETRIS is a complete online digital computer class where you create a working computer that plays TETRIS from just composing NAND gates. There is a free Coursera class on it as well as on YouTube.
• Langton's ant
• Minecraft - with "redstone" some people (with too much time on their hands) have implemented actual CPUs in a world.
• Here is an 8-bit processor that runs in Minecraft - 8-bit processors were the first micro computers to come out about in the later 1970's. Pacman and Space Invaders used them, as well as the TRS-80 and the first Apple computer.
• Minecraft in Minecraft - to add insult to injury, someone created the game of Minecraft that was running in the CPU created in Minecraft. I'm dumbfounded. It runs very slowly (obviously) so it had to run on a server to make the video one frame at a time. There is nothing in "Turing Completeness" that says something has to run fast. I will introduce the acronym TMFTOOH to mean "Too Much Free Time on one's Hand" since I will likely use it again.
• Programmable 4-Way Flying Machine in Minecraft (Full Explanation) - another programmable thingy in Minecraft.
• The Busy Beaver is turing complete.
• Wang Tiles
• x86 MOV Instruction - interesting that a single instruction in the Intel chip (which we all use) is Turing Complete. That means you can write a compiler for all programming languages that compiles to a string of MOV commands.
• Cities: Skylines is a city simulation game that is complex enough to build universal logic gates in it. Using universal logic gates it is possible to construct any circuit including Turing complete machines. So, just like in Minecraft one can build a computer inside Cities: Skylines.
• Chemical Computers - Chemical reactions were seen as a simple move towards a stable equilibrium which was not very promising for computation; until now.
• DNA Computing
• Breaking news: HTML+CSS is Turing complete - because it can be used to program a Rule 110 automaton. Rule 110 is arguably the simplest known Turing complete system. It is one algorithm of many described in Stephen Wolfram's A New Kind of Science book, which is online for free.

• Theory of Computation How simple can we make a computer that can do everything, given enough time?

Links

• Alan Turing (Wikipedia)
• Turing Completeness (Wiki)
• Surprisingly Turing-Complete (Wiki)
• Turing Tarpit - a language that aims for Turing-completeness in an arbitrarily small number of linguistic elements - ideally, as few as possible.
• BrainF (Wiki) - Not the most politely named programming language, but it does exist in Repl.it and you can quickly get an idea of what such a programming language looks like.
• One Instruction Set Computers (Wiki) - It is possible to build a computer with just one instruction, typically with three parameters. Here is a list of many such computers that have been proven to be Turing Complete.
• SUBtract and branch if Less-than or EQual to zero - An example of a language that prints "HI" on the screen.
• Connection between NAND gates and Turing completeness
• One Instruction Set Computer (OISC) Compiler - An actual implementation of a OISC machine.
• HIGHER SUBLEQ - Compiler into OISC language - Talk about students with too much free time on their hand. This is definitely academic.
• Is the NAND gate logical complete? - The NAND gate has the property of functional completeness, which it shares with the NOR gate. That is, any other logic function (AND, OR, etc.) can be implemented using only NAND gates. NAND and NOR are called a "Universal Gate" for just this reason.
• Turing Machines - Stanford Encyclopedia of Philosophy
• Oracle (Wiki) - An Oracle is a mythical, hypothetical computer that can instantly answer a YES or NO question in any context. It is used in proofs of certain types of theoretical computing; e.g. cryptography.
• C2's definition. - C2 was the original computer wiki site.