lamr

Appearance

Turing Machine ​

Reddit

A Turing machine is a hypothetical machine with an infinite memory tape that can only:

  • read the value on the tape,
  • write a new value to the tape,
  • move the tape left or right to a new position,
  • maintain and change between a finite set of states,
  • conditionally do the above based on the result of a tape read.

It is proven that mathematically, any machine that can do the above can compute anything that is mathematically computable.

That is, the set of all problems that a Turing machine be can solve is equal to the set of all problems solvable by lambda calculus (the mathematical formalism of computation, see Church-Turing thesis).

In real life, no Turing machines can exist due to the requirement for an infinite memory. But ignoring that, we call a language Turing complete if it can perform the operations of a Turing machine.

How about being Turing-incomplete? ​

Turing completeness is one of those things where it can lead to people using a language for more than is needed from it. Dhall is meant as a slightly more powerful way of configuring stuff (like JSON or TOML) but without the full power and complexity of a programming language. HTML by itself is also not Turing complete, as it's only purpose is to create document layouts.

On the other hand, HTML+CSS and Microsoft PowerPoint are Turing complete if you allow for a user to click elements. Microsoft Excel is also Turing complete using just cell formulas. You can find YouTube videos of people who made low-powered CPU emulators in PowerPoint and Excel.

In fact, if you define your language well enough, a single instruction is all that is needed for a Turing complete language (although very impractical).