# EVM and Turing Machines

###### tags: `thread`

I was very curious about EVM a long time ago. I could still understand the operating system of a physical computer, why Ethereum could implement its own virtual operating system?

And it is fully Turing-complete, meaning that all human computational behavior can be simulated, and that every program running on a personal computer can be migrated to run in an EVM environment.

### I'm so curious

Because I was curious about this issue, I unpacked part of the go-ethereum source code and read it (mainly core/vm), and also read some of the yellow paper (which I didn't understand too well) and the EVM source code interpretation.

But I only understood the skin of the matter, but not completely. Then I came across "Turing Machine Model" while reading "A Brief History of Information" and "Shannon's Biography", and found that there is a very strong correlation between these concepts.

### Turing machine

The essence of Turing machine is to simulate the "thinking" and "calculation" process of human problem solving, and to divide all human problems into "computable" and "non-computable". The latter is done by Turing machines.

The simplest Turing machine model consists of an infinitely long paper bag (tape), a free moving read/write head (header), a set of control rules (table), and a set of state registers (not clearly marked in the diagram).


An infinitely extended paper tape is like the "draft paper" we use when calculating, and then the read/write head is like a "pen and eraser" that can change the specific value of a certain cell on the paper tape.

We will list the calculation steps in the actual calculation, the control rules are similar to the "algorithm", will be based on our current calculation results, determine the next read-write head operation (how to modify the data).

The status register will store the current "state" of the Turing machine, just like we often ask ourselves "where are we now" in actual computation.

The "state of the world" in Ether is very similar to the "state register" of Turing machines.

To be precise, it is the balance of all addresses when time stands still, and the real-time status of all transactions (this concept is more abstract, it is easier to understand by looking at the code).

So the Turing machine model is to use a piece of paper to simulate the process and results of human computation, all the software that our machines run, see all the gorgeous pictures and web pages, and ultimately can be broken down into a series of computational tasks for the computer to run.

I was very excited to see both EVM and Turing machines. There are actually an infinite number of ways to implement a computer (the most fundamental of which can be boiled down to circuits), and Gavin implements it in one of them.

In this way, the EVM is even a bit like the JVM in the java environment. The EVM actually works in a very simple way.

The developer writes a smart contract in solidity, the EVM compiler compiles the human-readable solidity written by the developer into a machine-readable opecode and bytecode, and then mobilizes the EVM to change the state through the opcode, so you can open the yellow book and see that Gavin has defined a bunch of opcodes.

This is a very interesting topic, but if you really want to understand EVM and opcode/bytecode, I think it's better to do it yourself, you can refer to geth's PoC or "First Commit" to see if you can implement a simple EVM prototype. I think this will be the most interesting part, and the part I want to do afterwards.

### What is EVM

Vitalik defines EVM as a "transaction-driven state machine". If you re-read Vitalik's white paper, you will see that he defined Bitcoin from the beginning as a "transaction-driven financial ledger that transitions state ".


defines an `APPLY(S,TX) -> S'` or `ERROR` transition function

For example, if Alice transferred $20 to Bob, this function would look like this

`APPLY({ Alice: $50, Bob: $50 }, "send $20 from Alice to Bob") = { Alice: $30, Bob: $70 }`

I guess he was very familiar with "Turing machines" from the beginning (although vitalik grew up with computers, it's important to be curious and learn more), so he took the state transition system of bitcoin and turned it into the paper tape of the Turing machine we mentioned above, and then drove the movement of this paper tape through transactions, and This process simulates the computational process of a Turing machine and enables all computational tasks.

Turing also proposed a "stop state", if this state is reached, the Turing machine will automatically stop, if the Turing machine can never reach this state, it means that the problem is "uncomputable".

Based on this, Turing divided all problems into computable and non-computable, and if a computer can complete all "computable" tasks is Turing-complete, we now also call them general-purpose computers.

So when Vitalik and his team discovered nine years ago that they could turn a decentralized financial ledger into a "decentralized global computer," they were excited that this computer could perform all human computational tasks and that everyone's software could be migrated to this computer in the future. "What a revolutionary and fascinating idea.

Today, with the breakthrough of zk proofs and the progress of zk-rollups, we will need zkEVM to scale the EVM itself, which will be a very interesting experience.

It's the same as vitalik nine years ago, except that they just wanted to turn the global financial ledger into a "global computer", and this time we want to expand the global computer to a billion users.

### Conclusions

I'm writing this because I happened to see a Turing machine, and I'd like to document my previous study of EVM. I regret that I didn't break down EVM thoroughly and try to implement it (because my time was diverted by other things), but I think I'll continue to do this in the near future, and then I'll look back to see how much I've improved my understanding of EVM.

[Thread](https://twitter.com/LuozhuZhang/status/1514639491163598849?s=20&t=LEAtT7YABXdv2vw89_MJSQ)