The Ethereum Virtual Machine (EVM) is a turing-complete virtual machine developed by Ethereum's developers to run smart contracts on their blockchain. The concept of a virtual machine is not new. Languages like JAVA and C# do not natively support coding at the processor level, and to ensure that code produces the same output regardless of the processor model or operating system, these virtual machines were developed. While there are many virtual machines today, I will now discuss the Ethereum Virtual Machine and the theories and Turing Machine on which it was developed.

Formal Language Theory

Formal language theory is one of the fundamental branches of theoretical computer science. A formal language consists of sequences defined on a given set of symbols called the alphabet. Formal languages are described using expressions, rules, or automata that accept sequences belonging to the defined language. Therefore, the relationship between automata theory and formal language theory is important.

Formal languages are divided into 4 classes according to the Chomsky classification:

• Type 3: Regular languages.
• Type 2: Context-free languages.
• Type 1: Context-sensitive languages.
• Type 0: Recursive languages.

Each type mentioned above is a subset of the types with smaller numbers. Type 0 is the most general type, encompassing every language discussed with Turing machines and computer programs.

This classification (hierarchy) is based on the computational power of the rules or machines that generate the sequences of languages.

This topic, which is important in terms of theoretical computer science, plays a significant role in the preparation of compiler and interpreter software that allows computer programmers to produce computer programs using programming languages from scratch.

Formal language theory is one of the first topics a computer programmer who wants to develop a programming language from scratch needs to learn.

Automata Theory

Automata theory is a course offered in the computer engineering department; it was one of my favorite courses during my university years and one of the few courses for which I thought "I'm glad they included this in the curriculum." Automata theory is the branch of theoretical computer science that studies abstract machines and the use of these machines to solve computational problems. We call these abstract machines automata.


Automata theory is the study of abstract machines, automata, and the computational problems that can be solved using them. The word automata (plural of automaton) comes from the Greek word αὐτόματα, meaning "self-acting." An automaton (plural Automata) is an abstract, self-acting information-processing device that automatically follows a predetermined sequence of operations. A finite state automaton (FSA) or finite state machine (FSM) is an automaton with a finite number of states, state transitions, and actions. An action is the definition of an activity performed at a specific time. There are several types of actions:

• Entry action: This action is performed when the machine enters the state in question.
• Exit action: This action is performed when the machine exits the state in question.
• Input action: This action is performed depending on the current state and input conditions.
• Transition action: This action occurs when a specific transition is made.

Turing Machine

A Turing machine is fundamentally an algorithm and a component of automata theory. In the early 20th century, there was a great deal of debate about whether or not complex calculations could be performed by a specific mechanism. While manual or mental calculations have always been time-consuming and error-prone, the famous mathematician Alan M. Turing published his article "On Computable Numbers, with an Application to the Entscheidungsproblem" in 1936. In his article, Turing discussed a theoretical and mathematically-based virtual machine and claimed that all mathematical calculations could be performed with this virtual machine. Turing's second article, "Computing Machinery and Intelligence," published in 1950, addressed many controversial issues related to machines and intelligence. The virtual machine mentioned in these articles was later named the Turing machine.

A Turing machine is a mathematical model of computation that defines a tape consisting of symbols governed by a table of rules. Despite the simplicity of the model, a Turing machine can be constructed to simulate the logic of any computer algorithm given. The machine operates on an infinite memory tape divided into discrete "cells." The machine positions its "head" over a cell, "reading" or "scanning" the symbol there. Then, depending on the symbol and the machine's own current state, it writes a symbol (e.g., a digit or a letter from a finite alphabet) corresponding to the value in the "finite table" of user-defined instructions. The head on the machine is then moved one cell left or right on the tape (some models do not allow movement, others only allow movement of the machine head). Then (as determined by the observed symbol and the machine's own state in the table), it either proceeds to the next instruction or halts the computation.

Operations that can be performed on the machine are:

• Writing
• Reading
• Forward tape winding
• Rewind the tape

Chomsky Hierarchy and Turing Machines

This whole theory is based on these four simple operations, and languages and operations are classified according to whether a job can be done or a language can be reduced to these four simple operations.

Ethereum Virtual Machine

Ethereum developers refer to the EVM as a machine that lives on as a single entity maintained by thousands of connected computers running the Ethereum client. The Ethereum protocol itself exists solely to ensure that this special-purpose machine operates continuously, seamlessly, and immutably. It is the environment where all Ethereum accounts and smart contracts reside. In any block in the chain, there is only one universally accepted state of Ethereum, and the EVM is the construct that defines the rules by which a new valid state is calculated from block to block. To understand the EVM, it is also necessary to understand the concepts of bytes, stack, and memory.

The "Distributed Ledger" analogy is commonly used to describe blockchains such as Bitcoin, which generally enable a decentralized currency using basic cryptography tools. A cryptocurrency acts like a 'normal' currency due to the rules that govern what it can and cannot do to change the ledger. For example, a Bitcoin address cannot spend more Bitcoin than it has previously received. These rules form the foundation of all transactions in Bitcoin and many other blockchains. However, this is different in Ethereum. You can make transactions with Ether, Ethereum's native token. Unlike other blockchains, it has made a difference with both the ability to develop "Smart Contracts" and the fact that it has a state machine. Ethereum's state is a large data structure that holds not only all accounts and balances but also a machine state that can change from block to block according to a predefined set of rules and can execute arbitrary machine code. The specific rules for changing the state from block to block are defined by the EVM.


State Machine Instead of Distributed Ledger: While Ethereum has its own native cryptocurrency (Ether) that follows almost the same intuitive rules, it also hosts smart contracts, providing a much more powerful function. A more complex analogy is needed for this more complex feature. Instead of a distributed ledger, Ethereum is a distributed state machine. Ethereum's state is a large data structure that holds not only all accounts and balances but also a machine state that can change from block to block according to a predefined set of rules and can execute arbitrary machine code. The specific rules for changing the state from block to block are defined by the EVM.

Opcodes: This is the name given to the commands that allow us to perform machine-level operations on the EVM. We can also call it Assembly language. It currently contains around 150 instruction sets. With the commands in this instruction set, operational operations such as arithmetic operations, memory operations, and modification operations can be performed.


Gas Concept: A fee is determined for all operations performed on the EVM, and the word Gas is used for this fee. 21000 gas is consumed to start a transaction. Calculations are made over Ether units of Gwei. 1 gas can also be considered as 1 gwei.

Gas Fee: Gas unit (limit) * (Base Fee + Tip)

With the above calculation, we can calculate how much gas our transactions will consume. For example, a transaction call that performs a simple addition operation consumes 21,003 gas, including 21,000 gas for the call and 3 gas for the addition. Let's say 100 gwei for the base fee, and if we want the job to be done faster, we can add a Tip value, but let's continue without adding it. For this transaction, our total gas value is (21,003). Multiplying this value by our base value of 100 gives us a gas fee of 0.0021003 ether.


Block size: Before the London upgrade, Ethereum block sizes were fixed and limited to 15 million gas. After the London upgrade, this value was changed to increase up to 30 million gas.

EIP-1559: With the implementation of the London upgrade, gas fee calculations have become more complex, but they allow transactions to occur within certain limits with basic gas fees and maximum possible gas fees and make transaction fees predictable. You can get the necessary information from here.


SOURCE:

• Ethereum Virtual Machine(EVM)