What is Turing Complete?

A Turing complete is a feature that enables computer language or a platform to perform any kind of computation. It is assumed that to perform such computation there exists infinite resources available such as CPU and MEMORY.

The Church Turing Thesis (computability thesis) states that any performance calculation can be made by a Turing machine. A Turing machine is a machine with an infinite arbitrary access to a memory and the final program that dictates when it should read, write, and move across that memory, when it should terminate with a certain result, and what it should do next. The entrance of a Turing machine is put in its memory before it starts.

There are few things that can make a language or platform NOT Turing complete. A Turing machine can make decisions based on what it sees in memory. The language that only supports +, -, and / on integers is not Turing complete because it can't make a choice based on its input, but a Turing machine can.

A Turing machine can run forever. If we take a look at computer languages such as Java, Javascript, or Python and removed their capability to do any type of loop, GOTO, or function call, it would not be a Turing complete because it cannot perform an arbitrary calculation that never finishes otherwise.  A Turing Machine can use Infinite Memory.  Languages such as Java would terminate once it utilized more than 4 Gigabytes of memory.

This is why we cannot actually construct a Turing machine, but Java is still a Turing complete language since Java language doesn't have any restriction preventing it from using infinite memory.  Regular expressions (RegEx) are not Turing complete. Regular expressions are formal grammar used to parse strings that otherwise would be very tedious to implement in regular computer languages.

Ethereum blockchain platform is said to be Turing complete. We will see why in next part of this series.