Turing Completeness and the Ethereum Blockchain

Since about a week, I have been reading about Turing machine and slowly extending the concept to the world of blockchain. Primarily, the Ethereum blockchain. After gaining enough insights into the subject, I decided to give voice to my thoughts.

Let me delineate the scope of this article so that you know what you’re in for.

I’ll start off by giving a gentle introduction to the Turing machine followed by a discussion on the Church-Turing thesis. I’ll touch the Chomsky hierarchy. (Just a bit) I’ll discuss the fundamentals of an I/O Turing Machine by taking an example, accompanied with some basic mathematics.

After this, we will see how the Ethereum blockchain is not completely Turing complete and why it is rudimentary in the present-day. We will see what implications Turing completeness can have on the Ethereum blockchain with respect to the concept of Ethereum gas. We will go over the fundamentals of the Vyper language. We will then see in what scenarios a true Turing machine can transform smart contracts (this section contains futuristic talk).

I’ll try to keep my language as simple as possible, for obvious reasons.

This article is best enjoyed with a cup of strong filter coffee. If you don’t know what is filter coffee then you are missing out on life, my friend.

Alan M. Turing and his Turing Machine

The idea of Turing machine was conceived about 83 years ago, in 1936, by an English computer-scientist named Alan M. Turing. It was the time when the British empire was in its prime, so Turing had part of his early education in India. All of Turing’s contributions were not respected in the UK due to the fact that he was homosexual even though he broke the ‘unbreakable’ German Enigma code during WW II. He rose to intellectual fame becoming founder of computer science and artificial intelligence only after his death. Turing died anonymous, penniless, and impotent. Such is life?

The Turing machine is a theoretical, abstract idea which can simulate any algorithm that can be logically constructed. This means that a Turing machine can solve any problem if it can be coded out. There’s special emphasis on the word any. It certainly doesn’t guarantee how much time it will take to solve the problem, but it is certain that it will solve the problem. So it can take a second, a minute, a lifetime, or an entire generation to solve a problem.

But don’t you worry, your problem will be solved sooner or later!

Construction of a Turing Machine

Take an infinitely long tape (the length of the tape depends upon the length of the input, expected output, and complexity of the problem to be solved). The tape is divided into discrete cells. There would be infinite cells on the tape. The machine has a pointer, or a head which is capable of maneuvering left or right on the tape. A head also has the ability to erase data on the cell and write new data.

Everything that is to be deleted from the tape and everything that is to be added to the tape is governed by user-described instructions.

When a Turing machine starts, anything written on the tape is the input. When the Turing machine halts after completion of the problem, anything written on the tape is the output.

To compute the solution for a given problem, the Turing machine may read and write on the tape for infinite amount of time. There is no boundary on any resource like time, memory whatsoever.

Each cell has an associated state with it which is governed by user-described instructions. The state of the cell changes when an event occurs. When state changes, the value on the cell may be rewritten.

The mappings on the Turing machine are as follows:

Where,

𝛿 is a function.

q is the current state

a is the value on the cell

P is the new state

A is the new value on the cell

R means that the head will move right

L would mean that the head would move left

Church-Turing thesis or Computability thesis

This thesis says that whatever that can be called an effective procedure can be realized by a Turing machine.

A procedure is slightly different than an algorithm. An algorithm always comes to a halting state sooner or later. A procedure may or may not halt, it can go on forever.

There are some functions which can’t even be calculated by a Turing machine. For instance, quantum computers can simulate procedures in less amount of time as compared to modern computers. In contrast, there exist problems such as halting problem which an ordinary computer cannot answer. And according to Church-Turing thesis, no computational device can answer such a question.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever. Source: Wikipedia.

Chomsky Hierarchy

According to Chomsky, there are 4 types of languages which are differentiated based on the freedom of usability. Type 0 is the most flexible, free language and Type 3 is the most restricted language.

The language used in a Turing machine falls under Type 0 classification because the programmer has all the flexibility in the world to write whatever program they wish to write. Most of the languages today are Turing complete or Type 0 languages like C++, Java, JavaScript, Solidty, Pascal etc. Almost all languages today are Turing complete. The only languages that are not Turing complete are markup languages.

Turing machine as an I/O device

Let’s solve a problem on the Turing machine.

Problem statement: Check if the number of 1s in the string is even or odd.

Let’s take an infinitely long tape with a random string on it. Let the string be

0 1 0 1 1 0. The other cells are blank.

The Turing machine should print ‘o’ if the number of 1s is odd and should print ‘e’ if the number of 1s is even.

The rules governing machine behavior are as follows:

The initial state of the machine is q0.

Since the head is on the start of the string, the mapping would be as follows:

The Turing machine will look like this now:

This is because the data on the first cell was 0. The state will change only when the machine head will encounter 1.

Next mapping:

The Turing machine will look like this now:

Next mapping:

The Turing machine will look like this now:

Next mapping:

The Turing machine will look like this now:

Next mapping:

The Turing machine will look like this now:

Next mapping:

The Turing machine will look like this now:

Next mapping:

H is the halting state. This means the machine has stopped since it encountered a blank. The head won’t move left or right so there is a — .

The Turing machine will look like this now:

Since the machine halted at q1 state, there are odd number of 1s. If the machine halted at q0 state, there would be even number of 1s.

Note that ‘o’ is printed on the first encountered blank.

This is how a Turing machine is an I/O device.

I hope this gave you a gist of what a Turing machine really is. In the next section, we will explore the consequences of Turing machine with respect to the Ethereum blockchain.

Let’s see how the Ethereum blockchain is NOT actually Turing complete.

For those who don’t know the concept of Gas in Ethereum. This will be used a lot in the article. Here’s a basic definition:

Gas is the unit of measurement used to measure cost of running an operation on the Ethereum blockchain. The concept of gas exists to separate computational cost of running an operation (opcode) from market value of Ethereum (which is currently highly volatile).

So the cost to add 2 numbers in gas will always be the same even if 1 ETH = 10,000 USD or 1 ETH = 1 USD.

Each block on the Ethereum blockchain has Block gas limit. This is the maximum amount of gas that can be spent.

On 14th Feb 2019, 3:10 PM, the gas limit was 8000029 gas and the gas price was 5.1 gwei. This information can be easily found at ethstats.net. It’s a really cool site.

Such limits are imposed to protect the blockchain from DDoS attacks.

If you want to translate gas spent per unit time, you can check out ethgasstation.info for the conversion.

So effectively, there are 2 limits imposed on any I/O on the Ethereum blockchain. These are gas cost and block gas limit.

And, we know that a true Turing machine works with unlimited resources and the concept of Gas prevents the Ethereum blockchain to be truly Turing complete.

And that’s perfectly alright! Because…

Today, we do not really need Turing completeness due to the fact that present day smart contracts are very mundane. They solve really basic stuff like transferring funds, changing ownership, maybe adding two numbers. That’s all! Really. Nothing fancy is being done here.

I’ll tell you what fancy is.

Fancy is:

1. Powering solar panel using electricity purchased from a decentralized grid to power your water heater.

2. Your smart car interacts with other smart cars on the road and when your car pays the other smart car in crypto, those cars will clear the way for you.

3. Your smart car will not ignite if you consume too much alcohol. Alcohol consumption can be recorded using smart sensors.

Let your imagination run wild. The things you would imagine; they are classified as fancy.

This stuff is fancy because it deals with autonomous intelligence. For such things, we need very sophisticated smart contracts which will run for a higher gas than the current block gas limit. This is the future. The future is not P2P, rather it is M2M. This is where we need Turing completeness.

Although, with great power comes great responsibility!

Solidity, the Turing complete language for Ethereum smart contract, gives a lot of flexibility to the smart contract developer. A smart contract can only be deployed once on the blockchain. If anything minor goes wrong, the consequences can be drastically catastrophic.

A hacker can run any algorithm on EVM written in solidity to create an unauthorized effect. Most of it will be prevented due to the gas limit, but still, the damage cannot be undone. Of course, running arbitrary code is dangerous! For instance, there can be a buffer overflow in a banking application that allows the hacker to change their balance. This kind of vulnerability arises due to the fact that Solidity gave the hacker such freedom.

The current ERC20 token cannot securely and cheaply handle hyper-efficient, high throughput processing for carrying out sophisticated M2M interactions devoid of human intervention and oversight.

This is why some folks say that Solidity is not the right choice for the smart contract. We need something more secure, auditable. This is where Vyper comes in. A basic example of this would be to store health data on Ethereum blockchain. Solidity may not be the best language for that. Vyper surely is.

If you want to create super-secure smart contracts, go for Vyper.

Don’t get me wrong, the language Solidity is Turing complete but the “world-computer” EVM is not.

The language Vyper is NOT Turing complete, Solidity is. At the same time, a program written in Vyper will always have a predictable output. A program written in Solidity will not have a predictable output until and unless it is deployed and executed.

In Vyper, simplicity and readability of the language by a lay-man is more important than freedom and flexibility of Turing complete languages.

Vyper doesn’t support the following features:

1. Modifiers

2. Class inheritance

3. Inline assembly

4. Function overloading

5. Operator overloading

6. Recursive calling

7. Infinite-length loops

8. Binary fixed point

A fun fact, in Python 0.3 + 0.3 + 0,3 + 0.1 is NOT equal to 1.

Coming back…

So, there’s a tradeoff between security and freedom here. Fewer features, more auditability, and more security. More features, less auditability and less security.

Developers of Vyper say it themselves —

Will deliberately forbid things or make things harder if it deems fit to do so for the goal of increasing security.

Don’t get me wrong. Vyper was NOT created to replace Solidity. It was created to boost security. A recent study found more than 3000 vulnerable contracts contain security flaws.

Since we are talking about blockchain, let’s take a while to remember the Bitcoin blockchain. The Bitcoin scripting language is NOT Turing complete. The script only performs one function: transfer funds from one account to another. So there is no need for Turing completeness. So the behavior space of bitcoin script is predictable, as opposed to Solidity.

I’d like to take this final opportunity to re-emphasise on the future of smart contracts. Some of us might call autonomous machines interacting with each other ‘too fancy’. But I kid you not, probably by the time you are a grandparent, you’d be surprised to see that this, in fact, will become a reality. Do you want to be one of those old people who don’t understand technology anymore? I am guessing the answer here is no. So, don’t tag such ideas as ‘fancy’ and start contributing to these futuristic thoughts! Who cares if we sound crazy? If crazy people love to ideate, call me crazy!

That’s enough of me ranting there, lol. In the next article, I’d probably show you how to write smart contracts in Vyper language.

I really hope you enjoyed this. If you did, please applaud and support these ‘crazy’ ideas!