5 ms·

Ask HN: How would you explain Turing completeness?

• iwr 16y ago
  A (Universal) Turing Machine is a computation machine that can simulate (virtualize) the operations of any other computation machine, including itself, given enough memory and time. A Turing-complete language is capable of functionally expressing a Turing machine. That is, given the theoretical construct, can the language encode it? An equivalent framework is lambda calculus. Any Turing machine can be expressed as lambda-expressions and vice-versa. The physical world analog to the Turing machine is the Universal Constructor, a machine that can construct a duplicate of itself or a functional analog of any other machine that can duplicate itself, given enough time and raw materials. These concepts are relevant because it's not clear if there is a class of problems not solvable by Turing machines (but solvable by another class of machines). As far as we know, human beings themselves are Turing machines (and constructors) and nothing more.
  • Locke1689 16y ago
    Please note that there is no system in existence which is a Universal Turing machine. All possible physical systems are finite state machines.
• SeanDav 16y ago
  I would argue that no analog or analog/hybrid computer can be TC, almost by definition. If you accept this (arguable) statement, then one can argue further that there is a class of problem solvable by analog machines but not TC machines. True random numbers is one example. (Disclaimer: I am no computer scientist - this is just a personal musing)
• iwr 16y ago
  Non-TC languages in current use are largely representational data formats (like HTML, CSS etc), or Excel spreadsheets (using only formulas, without macros) or languages with a closed topological memory space (like Befunge).
• sgentle 16y ago
  Alright, I'll give it a shot. A couple of definitions will be helpful here: A turing machine is a theoretical device invented by Alan Turing. It consists of a tape (data) and a fixed table of rules (the program). The machine has a head which reads or writes one piece of data at a time. The logic in the table tells the head what to do next (move, read, write etc). That's great, but it only gives you one (fixed) program at a time. So what if you encode the program and the data on the tape, and set up your table of rules such that it can execute any program. Then you have what's called a Universal Turing Machine. That idea is basically the theory behind iterative programming languages. The equivalent theory for functional programming languages is the Alonzo Church's lambda calculus. The two worked together to create the Church-Turing thesis, which states that anything computable can be computed by a turing machine (or expressed using lambda calculus). So you can essentially translate "Turing complete" as meaning "able to compute anything". Since there is nothing that can compute more than a Turing machine, that means all Turing-complete languages are equivalent. (Well, the Church-Turing thesis isn't actually provable, since "computable" is a bit hand-wavy, but it's generally considered to be true). A non-rigourous litmus test is that something is turing complete if it has conditions, looping and memory access, or recursive functions. You can also prove something is Turing-complete by using it to write an interpreter for a Turing-complete language. Examples of things that aren't turing complete: regular expressions, (standard) SQL, markup languages (HTML, XML, etc), some templating languages. Interesting things that are turing complete: basically every iterative or functional programming language, Conway's Game of Life, Minecraft.
  • motxilo 16y ago
    You may add TeX to the latter list :)