In computability theory, the Church–Turing thesis is a thesis about the nature of computable functions. It states that a function on natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine, i.e. meaning that any computable problem can be computed by a Turing machine.

This means we don't need a computer more powerful than a Turing machine to solve computable problems, and the idea of Turing completeness is closely related to this: a system is Turing complete if it can compute every Turing computable function.

A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete.

In general, for a programming language to be Turing-complete, it needs:

1. A form of conditional repetition (loop, while) or conditional jump (if, goto)
2. A way to read and write some form of storage (e.g., variables, tape)

To check if your language is Turing complete, check if you can implement a Turing machine inside it. In layman terms, check the following conditions:

1. Can make decisions - The 'language' that only supports +, -, *, and / on integers is not Turing complete because it can't make a choice based on its input
   ‍
2. Can run forever - Turing proved that you cannot predict whether a program will terminate by simulating it on a computer. In simple terms, we cannot predict the path of a program without running it. Turing-complete systems can run in "infinite loops," an oversimplified term used to describe a program that runs forever.
   
   If you take a modern programming language like Java, Javascript, Python, Rust etc. and you remove the ability to do any sort of loop, goto, or function call, it wouldn't be Turing complete, because it won't be able to perform a computation that never finishes.
   ‍
3. Can use infinite memory - Imagine a language similar to Java that would terminate once it reaches 4 GB of memory (hard limit). It wouldn't be Turing complete, because a Turing machine can use infinite memory. This is why we can't actually build a Turing machine, but the programming language itself is Turing-complete because the Java language has no restriction preventing it from using infinite memory.
   ‍
4. Can read and write data to RAM (i.e. is not only stack-based) - A language that only has stack PUSH and POP instructions is not Turing complete. If we have a language that reads a string only once and can only use push and pop stack instructions, it cannot read random values from the string by just using stack push and pop
‍
5. Can simulate any other Turing machine - A Turing machine, when given an appropriate 'program', can take another Turing machine's 'program' and simulate it on arbitrary input. If you have a language that wouldn't be able to implement a Python interpreter, it wouldn't be Turing complete.

‍

To summarize, if a language has infinite RAM, conditional execution, and some form of repeated execution, it's probably Turing complete.

Most modern programming languages (e.g. Go, Python, Java, JavaScript, Perl, etc.) are all Turing complete because they each implement all the features mentioned above. Then there are "computing environments" that you would not expect to be Turing Complete, but really are:

• For example, Excel spreadsheets are Turing complete. That’s not entirely a surprise, since they include a full-fledged programming language for writing macros/extensions. But even without using that, the formula language of Excel can be argued to be Turing complete
• The redstones in the game Minecraft define a language that is Turing-complete.

Let's look at the EVM now. The EVM's ability to execute a stored program while reading and writing data to memory makes it a Turing-complete system and therefore a Universal Turing Machine (UTM). The EVM can compute any algorithm that can be computed by any Turing machine, given the limitations of finite memory.

Now, knowing that a language is Turing complete assures that if a function (or a script is run), for a given input, the desired output can be achieved. This is important for a language like Solidity, because you can understand the impact of Turing Completeness on Smart Contracts.

uring completeness is very easy to achieve; in fact, the simplest Turing-complete state machine known has 4 states and uses 6 symbols, with a state definition that is only 22 instructions long. Indeed, sometimes systems are found to be "accidentally Turing complete." A fun reference of such systems can be found at http://bit.ly/2Og1VgX.

However, Turing completeness is very dangerous, particularly in open access systems like public blockchains, because of the halting problem. For example, modern printers are Turing complete and can be given files to print that send them into a frozen state. The fact that Ethereum is Turing complete means that any program of any complexity can be computed by Ethereum. But that flexibility brings some thorny security and resource management problems. An unresponsive printer can be turned off and turned back on again. That is not possible with a public blockchain.

Implications of Turing Completeness

Turing proved that you cannot predict whether a program will terminate by simulating it on a computer. In simple terms, we cannot predict the path of a program without running it. Turing-complete systems can run in "infinite loops," a term used (in oversimplification) to describe a program that does not terminate. It is trivial to create a program that runs a loop that never ends.

But unintended never-ending loops can arise without warning, due to complex interactions between the starting conditions and the code. In the EVM, this poses a challenge: every participating node (client) must validate every transaction, running any smart contracts it calls.

But as Turing proved, Ethereum can’t predict if a smart contract will terminate, or how long it will run, without actually running it (possibly running forever).

Whether by accident or on purpose, a smart contract can be created such that it runs forever when a node attempts to validate it. This is effectively a DoS attack.

And of course, between a program that takes a millisecond to validate and one that runs forever are an infinite range of nasty, resource-hogging, memory-bloating, CPU-overheating programs that simply waste resources. In a world computer, a program that abuses resources gets to abuse the world’s resources.

So, is the EVM Turing Complete?

NOT EXACTLY: Solidity is, the EVM isn't.

The EVM is a quasi–Turing-complete state machine; "quasi" because all execution processes are limited to a finite number of computational steps by the amount of gas available for any given smart contract execution.

The EVM can’t predict if a smart contract will terminate, or how long it will run, without actually running it (possibly running forever) because of gas. As the EVM executes a smart contract, it carefully accounts for every instruction (computation, data access, etc.) in terms of predetermined gas units.

When a transaction triggers the execution of a smart contract, it must include an amount of gas that sets the upper limit of what can be consumed for running the smart contract. The EVM will terminate execution if the amount of gas consumed by computation exceeds the gas available in the transaction. Gas is the mechanism the EVM uses to allow Turing-complete computation while limiting the resources that any program can consume.

So there are 2 limits imposed on any I/O by and EVM-compatible blockchain: gas cost and block gas limit.

Fun fact: Vyper is not a Turing-complete language because it doesn’t support the following features:

• Modifiers
• Inline assembly
• Function overloading
• Operator overloading
• Recursive calling
• Infinite-length loops
• Binary fixed point

The tradeoff of Vyper is the added security. Fewer features means more auditability, more security and more predictable resource usage.

‍