Turing Completeness and Gas

As we have already touched on, in simple terms, a system or programming language is Turing complete if it can run any program. This capability, however, comes with a very important caveat: some programs take forever to run. An important aspect of this is that we can’t tell, just by looking at a program, whether it will take forever or not to execute. We have to actually go through with the execution of the program and wait for it to finish to find out. Of course, if it is going to take forever to execute, we will have to wait forever to find out. This is called the halting problem and would be a huge problem for Ethereum if it were not addressed.

Because of the halting problem, the Ethereum world computer is at risk of being asked to execute a program that never stops. This could be by accident or malice. We have discussed that Ethereum acts like a single-threaded machine, without any scheduler, and so if it became stuck in an infinite loop this would mean it would become unusable.

However, with gas, there is a solution: if after a prespecified maximum amount of computation has been performed, the execution hasn’t ended, the execution of the program is halted by the EVM. This makes the EVM a quasi–Turing-complete machine: it can run any program you feed into it, but only if the program terminates within a particular amount of computation. That limit isn’t fixed in Ethereum—you can pay to increase it up to a maximum (called the “block gas limit”), and everyone can agree to increase that maximum over time. Nevertheless, at any one time, there is a limit in place, and transactions that consume too much gas while executing are halted.

In the following sections, we will look at gas and examine how it works in detail.