I'm new to programming and I've been told that "Javascript is a Turing complete programming language". What is a "Turing complete" P.language?... I've tried to read some articles in Wiki like Turing complete, or Turing completeness but still couldn't get an asnwer that was enough primal and clear to me...
2 Answers
In layman's terms, you can think of it as a "complete" programming language.
In practice, languages which are not Turing complete have somewhat crippling limitations, such as ones which disallow recursion. It may be fine for a limited-purpose language, but it means that some algorithms cannot be expressed, and some others require tortured workarounds.
In computer science, it is an important principle that complex systems can be "reduced" (proven to be isomorphic, i.e. fundamentally equivalent) to very simple systems which we can reason about. It is fairly easy to reason about what a Turing machine (a very crude theoretical abstraction of a modern computer) can and cannot do; we then know that our conclusions must be true for any system which can be reduced to a Turing machine.
But for your concrete question, this is just a snobbish way to tell the snobs you are one of them, actually.
6 Comments
slebetman
Technically, it's not that a language can be reduced to a Turing machine. But that it can be used to implement a Universal Turing machine. The Church-Turing hypothesis kind of "cheats" in proving one language/system/machine is equal to another. If they are not equal then simply write an emulator for that other language/system/machine and run that other language's program in the emulator. That's the crux of the theorem proof.
Jerry Coffin
It should be noted that some Turing complete languages still require torturous workarounds. In fact, quite a bit of research has been done on the minimum a language must support and still be Turing complete. It's gotten to the point of a machine with only a single instruction, such as "subtract and branch if zero". With the correct combinations of that, you can produce anything--but most such machines are purely theoretical, not practical. One recent paper proved that the x86 Move instruction (by itself--no other instructions at all) is enough to be Turing complete.
tripleee
But then "workaround" means something else than I intended. It's a language designer's choice if the language is spare; if you cannot implement a C compiler or a Lisp interpreter to get you where you want to go, that's where the real workarounds start.
slebetman
@JerryCoffin: You'd be surprised. Single instruction CPUs have been built and mass produced. Google "New England Digital Able CPU" - it only had move. NED closed shop in the 90s but I think the Able is still produced in small quantities because it's used in some musical instrument. A more modern example is the MAXQ from Dallas Semi. Both are "move" machines. The technical term for the architecture is Transfer Triggered Architecture (TTA). I've designed some myself. They're quite easy to program because you use the "high level" language of the memory addresses as your instruction set.
|
Before explaining what Turing Complete is, one must explain what a Turing Machine is.
In simple words, (but not-exactly-layman's-terms,) a Turing Machine is a machine that contains mutable state, executes sequences of simple instructions that read and write that state, and can pick different execution paths depending on the state (via conditional branch instructions.)
Very importantly, note that the ability to branch also means the ability to loop, and that different execution paths can perform different mutations on the state.
As simple as the above description is, it has an astonishing emergent characteristic: it is impossible to tell what a non-trivial Turing Machine is going to do via static analysis alone; any analysis aiming to tell how a Turing Machine is going to behave necessarily has to perform an amount of work that is proportional to the amount of work that the machine will do as it runs. (And therefore, if the machine runs forever, then the analysis will never produce an answer, hence The Halting Problem.)
A Turing Complete system is a system that abides by, or can be reduced to, the above description. (So, essentially, it has what it takes to emulate any other Turing Complete system, which is the "isomorphic, i.e. fundamentally equivalent" part that user tripleee wrote in his answer.)
In practical terms, all programming languages are Turing Complete.
Examples of languages that are not Turing Complete are HTML, JSON, CSS, and in general all description languages and markup languages. You can debate as to whether they have mutable state, but what they certainly do not have is instructions reading and writing that state, and branching. If markup languages had these features then they would be Turing Complete, but then we would not be calling them markup languages, we would be calling them programming languages.
