Virtual Machines, Turing Completeness and the Capacity for Infinite Computation

Envision an ethereal intelligence wherein, given sufficient explanation of a problem, it will invariably generate a solution. Assuming this intelligence is provided with the requisite resources and necessary time, it could understand, calculate and solve infinitely complex problems. Such intelligence appears at first to be pulled from the annals of science fiction, when in fact they exist and are frequently used throughout the present world. Referred to as Turing complete virtual machines, they have become a staple of blockchain networks due to their ability to execute any program that can be executed as an algorithm. This fascinating invention continues to influence the development of modern computers and forever changed the way we think about computation and the very essence of what it means to be a machine.

Virtual Machines (VMs)

The concept of virtual machines (VMs) has been a cornerstone in the evolution of computing technology, playing a pivotal role in enhancing the capabilities of various computational systems. virtual machines are software-based abstractions that allow multiple operating systems (OSs) or applications to run concurrently on a single hardware platform. In the context of blockchain, virtual machines provide a runtime environment for executing smart contracts. By emulating the characteristics and functionalities of the underlying hardware, VMs offer a versatile and efficient means to harness the full potential of computing resources, enabling tasks to be performed in isolated environments that promote security, flexibility, and performance optimization. Virtual machines effectively create a level of abstraction between the software and the hardware, allowing for improved resource management, load balancing, and fault tolerance.

The underlying mechanics of virtual machines are intriguing as they operate by emulating the functionalities of a computer system’s hardware components through software. This emulation process is made possible through the use of a hypervisor, a specialised software layer that manages the allocation of hardware resources among the various VMs running on a single physical host. The hypervisor ensures that each VM is provided with the necessary resources, such as CPU, memory, and storage, while also maintaining strict isolation between them to prevent interference and maintain security. 

Additionally, the hypervisor is responsible for handling interrupts, managing memory address translation, and maintaining the virtual-to-physical mapping of resources. To achieve this, hypervisors can employ two primary techniques; full virtualization and paravirtualization. Full virtualization involves emulating the entire hardware environment, allowing guest OSs to run unmodified, whereas paravirtualization requires modification of the guest OS to enable more direct interaction with the underlying hardware, resulting in improved performance.

One of the primary motivations behind the development and adoption of virtual machines is the need for increased efficiency and resource utilisation in computing environments. By allowing multiple VMs to run concurrently on a single physical host, VMs enable the efficient use of computing resources, eliminating the need for dedicating an entire physical machine to each OS or application. This consolidation of resources not only reduces the overall cost of hardware acquisition and maintenance but simultaneously leads to significant energy savings and a reduced environmental footprint. Furthermore, VMs enable rapid provisioning and scaling of resources, allowing organisations to quickly respond to fluctuating demands and optimise their computing infrastructure for maximum performance and cost-efficiency. 

A quintessential example of a VM in the blockchain space is the Ethereum Virtual Machine (EVM), which serves as the runtime environment for executing smart contracts on the Ethereum blockchain. The EVM is designed to provide an isolated, secure, and consistent environment for executing code in the form of smart contracts, allowing developers to create decentralised applications (DApps) that can interact with the blockchain and its native cryptocurrency, Ether. 

The EVM operates on a stack-based architecture, which means that it utilises a last-in, first-out (LIFO) data structure for storing and retrieving operands and intermediate results during execution. This architecture allows for efficient execution of operations, as operands are pushed onto the stack, and the results of operations are popped from the stack, making it easier to manage complex computations and nested function calls. This model can be visualised by a stack of plates whereby a plate can physically only be added and taken from the top – this is akin to the first in first out (FIFO) processing method.

The EVM is Turing complete, meaning it is capable of performing any computation that can be described by a Turing machine, given enough resources. This powerful feature enables developers to create complex and sophisticated smart contracts that can automate various tasks, enforce agreements, and facilitate decentralised finance, among other applications. However, the EVM’s Turing completeness also raises concerns about the potential for infinite loops or resource-intensive operations, which could negatively impact the performance and security of the Ethereum network. To mitigate these risks, the EVM employs a gas unit, assigning a specific cost to each operation or instruction executed within a smart contract. 

Another essential aspect of virtual machines, particularly in the context of blockchain technology, is the support for interoperability and cross-platform compatibility. By providing a consistent and standardised runtime environment, VMs enable applications and smart contracts to run on different platforms and hardware configurations without requiring extensive modifications or adaptations. This capability is crucial for decentralised networks, as it allows participants to collaborate and interact seamlessly, despite potentially running on diverse computing infrastructures. 

In the case of the EVM, this interoperability extends to other blockchain networks that have adopted the Ethereum-compatible smart contract execution environment, fostering the development of cross-chain solutions and enhancing the overall capabilities of the decentralised ecosystem. However, when virtual machines are different and not compatible by nature, direct interoperability is impossible, giving rise to severe compatibility issues. Hence the rise of layer 0 networks and other cross-chain communication protocols.

Turing Completeness

Turing machines, conceived by the visionary British mathematician Alan Turing, embody a theoretical framework that revolutionised the realm of computation and laid the groundwork for modern computer science. This abstract construct has risen to prominence as a crucial reference point for understanding the limits and possibilities of computational systems. With the advent of blockchain technology, Turing machines have found renewed relevance in understanding the principles and mechanics of decentralised computational networks. In essence, Alan Turing’s work on Turing machines has left an indelible mark on the computational landscape, with its influence extending far beyond its original scope.

Turing Machines

The origins of Turing machines can be traced back to 1936 when Alan Turing published ‘On Computable Numbers, With An Application To The Entscheidungsproblem’, a paper that outlined the concept as a way to study the limits and capabilities of computation. The Turing machine is an abstract machine that consists of an infinite tape divided into cells, a read/write head that moves along the tape and a finite set of rules (or a program) that governs the machine’s actions. At its core, a Turing machine is designed to perform simple operations such as reading, writing, or modifying symbols on the tape and moving the head left or right. Despite the simplicity of these operations, Turing machines have been proven to be capable of simulating any algorithm or computational process, given enough time and resources 

A key concept in the study of Turing machines is the notion of Turing completeness. A computational system is said to be Turing complete if it can simulate the behaviour of a Turing machine, which essentially means that the system is capable of performing any computation that is theoretically possible. Some well-known examples of Turing complete systems include programming languages such as C++, Python, and JavaScript. In these languages, developers can write code that can simulate the behaviour of a Turing machine, thereby demonstrating their Turing completeness.

In this example, we define a simple Turing machine in Python that simulates the behaviour of a Turing machine using a given set of rules. The TuringMachine class represents the machine, and its step method performs a single operation based on the current state and symbol. The run method allows the machine to execute a specified number of steps. To further clarify how this Python program acts as a Turing machine, an analysis of the specific components of the code and their corresponding roles in the Turing machine paradigm is useful:

1. The tape: In the code, the tape is represented by a Python dictionary called ‘tape’. A dictionary is an unordered collection of key-value pairs, where the keys represent the positions on the tape, and the values denote the symbols stored at these positions. By using a dictionary, the program can dynamically allocate memory as needed, simulating an infinite tape with an arbitrary number of positions.

2. The read/write head: The read/write head’s position on the tape is represented by the variable ‘position’. This variable is an integer that can take on any value, denoting the current position of the read/write head. The program simulates the read/write head’s functionality by manipulating the values in the ‘tape’ dictionary based on the current ‘position’ and the state-transition rules specified in the ‘rules’ dictionary.

3. The state-transition rules: These rules dictate the behaviour of the Turing machine, defining how it should transition between states and modify the tape’s contents. In the code, the state-transition rules are specified as a Python dictionary called ‘rules’. Each key in the ‘rules’ dictionary represents a tuple of the current state and the symbol read from the tape. The corresponding value is a tuple that contains three elements: the new state, the symbol to be written on the tape, and the direction in which the read/write head should move (either ‘L’ for left or ‘R’ for right).

4. The execution loop: The core of the Turing machine’s operation lies in its execution loop, where the state transition rules are repeatedly applied until the machine reaches a halting state. In the code, this execution loop is implemented as a while loop that continues iterating until the current state is equal to the halting state, denoted by ‘HALT’. Inside the loop, the program uses the current state and the symbol read from the tape to look up the appropriate state transition rule in the ‘rules’ dictionary. It then updates the tape, the read/write head’s position, and the current state according to the rule’s instructions.

By implementing these components in a Python program, the code effectively simulates the behaviour of a Turing machine. The specific rules provided in the example dictate a simple algorithm that increments a binary number by one, but the overall structure of the code could be adapted to simulate any Turing machine by modifying the state transition rules and the initial contents of the tape. This Python program serves as a practical demonstration of a Turing machine’s core principles, showcasing the power and versatility of this foundational concept in computer science.

Exploring the concept of Turing machines further, it becomes apparent that many computational systems encountered in everyday life exhibit Turing completeness. For example, cellular automata such as Conway’s Game of Life and even some esoteric programming languages like COW have been proven to be Turing complete. These examples serve to illustrate the widespread impact of Turing’s ideas on the field of computer science and highlight the power and versatility of Turing’s complete systems.

Although Turing machines are purely theoretical constructs, they serve as valuable tools for understanding the fundamentals of computation and the limits of what can be achieved using computational systems. Turing machines have also played a crucial role in the development of the Church-Turing thesis, which posits that the Turing machine is the most general model of computation and therefore, if a function cannot be computed by a Turing machine, then it cannot be computed by any other model of computation. This thesis, although not a formal theorem, has been widely accepted in the field of computer science and has driven the development of various computational models and technologies.

It is important to note that Turing machines, despite their theoretical nature, have had a profound influence on the design and development of real-world technologies. For instance, the architecture of modern computers and their central processing units (CPUs) can be seen as an embodiment of the principles laid down by Turing machines. The instruction sets of CPUs, which define the low-level operations that the processor can perform, can be thought of as a physical realisation of the rules governing a Turing machine. The memory hierarchy found in modern computers, including registers, caches, and main memory, can be viewed as an adaptation of the infinite tape concept.

Blockchains and Turing Completeness

The advent of blockchain technology has brought the concepts of Turing machines and Turing completeness to the forefront once again. Many blockchains employ virtual machines to execute smart contracts that enable DApps and other applications to run on their networks. These VMs, such as the EVM, are designed to be Turing complete, enabling them to support a diverse range of applications and use cases.

Turing completeness in blockchain VMs is achieved through the implementation of a comprehensive instruction set and control structures, much like in general-purpose programming languages. The EVM, for example, supports a wide range of operations, including arithmetic, logic, control flow, and memory manipulation, allowing developers to write complex smart contracts using the Solidity programming language which it then compiles and deploys.

While Turing completeness offers significant benefits for blockchain virtual machines, it also introduces potential risks and challenges, such as the ‘halting problem’ a fundamental problem in computer science that asks whether it is possible to write a program that can determine, for any arbitrary program and input, whether the program will eventually halt or run forever. The problem was first formulated by Alan Turing in the 1930s, and it has since been proven that there is no algorithm that can solve the halting problem for all possible inputs. 

To address these concerns, blockchains like Ethereum, employ a mechanism called gas, that limits the amount of computation that can be performed during the execution of a smart contract. Gas functions as a measure of computational resources, with each operation in the EVM consuming a predefined amount of gas. When a smart contract is executed, the transaction sender specifies a gas limit, and if the execution exceeds this limit, the transaction is reverted, and any consumed gas is forfeited. This mechanism helps mitigate the risks associated with Turing completeness, ensuring that the network remains secure and stable 

The use of Turing complete virtual machines in blockchain networks has opened up new possibilities for decentralised computation and the development of sophisticated, versatile DApps. These VMs provide a robust and expressive platform for developers to create innovative solutions, ranging from decentralised finance (DeFi) platforms to decentralised autonomous organisations (DAOs) and beyond. 

Coding A Turing Complete Virtual Machine

Certain qualities are necessary for a VM to be considered Turing complete, and the EVM exemplifies these qualities.

Firstly, a Turing complete VM must have a means of representing and manipulating variables and memory. In the EVM, variables and memory are managed through a stack-based architecture, which provides an efficient way to handle temporary storage and variable manipulation. The EVM’s stack, memory, and storage components work together to manage data during contract execution. Each of these components serves a specific purpose; the stack is used for temporary storage and quick calculations, memory for more extensive data manipulation, and storage for long-term data persistence. To illustrate this, consider the following simple Solidity contract that demonstrates the EVM’s ability to manage memory:

In this contract, the function storeAndRetrieve takes an input value, stores it in an array, and then retrieves and returns the value. When this contract is compiled, the resulting EVM bytecode includes opcodes such as MSTORE, MLOAD, PUSH, and DUP. An opcode is a short code that represents a specific instruction that a computer processor can execute. The PUSH opcode is used to place the input value onto the stack, while the DUP opcode duplicates the value on the stack to create a new copy for manipulation. The MSTORE opcode stores the input value in the memory array, while the MLOAD opcode retrieves the stored value from memory. This simple example illustrates the EVM’s ability to manage memory and variables during contract execution, a crucial requirement for Turing completeness.

Secondly, a Turing complete VM must be able to perform conditional branching and looping. Conditional branching is a concept that allows the program to execute different sets of instructions based on a specified condition. When employed by a VM, conditional branching allows it to alter its execution flow based on specific conditions. Conversely, looping enables the repetitive execution of a code segment. The EVM provides opcodes such as JUMPI, JUMP, and JUMPDEST to implement conditional branching and looping. Let’s consider a simple Solidity contract that demonstrates the EVM’s ability to perform conditional branching:

In this contract, the function isEven takes an input value and determines if it is even using conditional branching,  The EVM bytecode for this function will include opcodes such as DUP, MOD, PUSH, JUMPI, JUMP, and JUMPDEST. The DUP opcode duplicates the input value on the stack, while the MOD opcode calculates the remainder of the input value with respect to 2. The PUSH opcode places the result on the stack, and the JUMPI opcode checks if the result is equal to 0. If the result is equal to 0, the EVM will jump to the JUMPDEST opcode, which marks the beginning of the true branch, and execute the code within that branch. If the result is not equal to 0, the EVM will continue with the false branch, executing the code within that branch. This example showcases the EVM’s ability to perform conditional branching, which is essential for Turing completeness.

Looping in the EVM can be achieved using similar opcodes, such as JUMP and JUMPDEST, in conjunction with conditional branching. To illustrate this, consider the following simple Solidity contract that demonstrates the EVM’s ability to perform looping:

In this contract, the function sumOfIntegers calculates the sum of all integers from 1 to the input value n using a loop. The EVM bytecode for this function will include opcodes such as DUP, LT, JUMPI, ADD, JUMP, and JUMPDEST. The LT opcode compares the loop counter i with the input value n and checks if i is less than or equal to n. The JUMPI opcode then conditionally jumps to the loop body, marked by a JUMPDEST, if the comparison is true. Within the loop body, the ADD opcode adds the loop counter i to the sum variable. After the loop body is executed, the JUMP opcode unconditionally jumps back to the beginning of the loop to perform the next iteration. This example demonstrates the EVM’s ability to perform looping, another critical aspect of Turing completeness.

Lastly, a Turing complete VM must be capable of performing arithmetic and logical operations. The EVM supports a wide range of arithmetic operations, including addition, subtraction, multiplication, division, and modulo, as well as logic gates such as bitwise, AND, OR, XOR, and NOT. These operations are executed using opcodes like ADD, SUB, MUL, DIV, MOD, AND, OR, XOR, and NOT. These opcodes allow the EVM to perform complex computations and make decisions based on the results of those computations. For example, the earlier isEven function used the MOD opcode to calculate the modulus of the input value with respect to 2, and the JUMPI opcode to perform conditional branching based on the result.

Collectively, these features demonstrate the EVM’s Turing completeness, allowing it to execute any computable function given enough resources. In practice, Turing complete systems encounter practical constraints such as scalability issues that may prevent certain computations from being performed due to their resource-intensive nature. Nevertheless, it remains a powerful tool, enabling a diversity and versatility of computation that is necessary for modern computational systems.

Conclusion

In the realm of technological innovation, virtual machines stand out as a  testament to the capabilities of the human mind, transcending the boundaries of their physical hardware to form a computer that exists solely in the ether. Likewise, the evolution of Turing machines from a mere thought experiment into real-world applications, showcases the advancement of computational theory, drawing ever closer to the ultimate vision of infinite computation. These two technologies have not only revolutionised our understanding of computation yet concurrently ushered in a new era of decentralised networks, enabling the sophisticated smart contracts and DApps that make up the modern blockchain landscape.

About Zerocap

Zerocap provides digital asset liquidity and custodial services to forward-thinking investors and institutions globally. For frictionless access to digital assets with industry-leading security, contact our team at [email protected] or visit our website www.zerocap.com

FAQs

What are Virtual Machines (VMs) and how do they contribute to blockchain technology?

Virtual Machines (VMs) are software-based abstractions that allow multiple operating systems or applications to run concurrently on a single hardware platform. In the context of blockchain, VMs provide a runtime environment for executing smart contracts. They offer a versatile and efficient means to harness the full potential of computing resources, enabling tasks to be performed in isolated environments that promote security, flexibility, and performance optimization.

What is the role of a hypervisor in the functioning of Virtual Machines?

A hypervisor is a specialized software layer that manages the allocation of hardware resources among the various VMs running on a single physical host. It ensures that each VM is provided with the necessary resources, such as CPU, memory, and storage, while also maintaining strict isolation between them to prevent interference and maintain security.

What is Turing Completeness and how does it relate to blockchain technology?

Turing Completeness is a concept in computer science that states a system is Turing complete if it can simulate the behavior of a Turing machine, which means the system is capable of performing any computation that is theoretically possible. Many blockchains employ virtual machines to execute smart contracts that enable DApps and other applications to run on their networks. These VMs, such as the Ethereum Virtual Machine (EVM), are designed to be Turing complete, enabling them to support a diverse range of applications and use cases.

What is the halting problem in the context of Turing Complete systems?

The halting problem is a fundamental problem in computer science that asks whether it is possible to write a program that can determine, for any arbitrary program and input, whether the program will eventually halt or run forever. It has been proven that there is no algorithm that can solve the halting problem for all possible inputs. To mitigate the risks associated with Turing completeness, blockchains like Ethereum employ a mechanism called gas, that limits the amount of computation that can be performed during the execution of a smart contract.

How does the Ethereum Virtual Machine (EVM) demonstrate Turing Completeness?

The EVM demonstrates Turing Completeness through its ability to represent and manipulate variables and memory, perform conditional branching and looping, and execute arithmetic and logical operations. It operates on a stack-based architecture, which provides an efficient way to handle temporary storage and variable manipulation. It also supports a wide range of operations, including arithmetic, logic, control flow, and memory manipulation, allowing developers to write complex smart contracts using the Solidity programming language.

DISCLAIMER

Zerocap Pty Ltd carries out regulated and unregulated activities.

Spot crypto-asset services and products offered by Zerocap are not regulated by ASIC. Zerocap Pty Ltd is registered with AUSTRAC as a DCE (digital currency exchange) service provider (DCE100635539-001).

Regulated services and products include structured products (derivatives) and funds (managed investment schemes) are available to Wholesale Clients only as per Sections 761GA and 708(10) of the Corporations Act 2001 (Cth) (Sophisticated/Wholesale Client). To serve these products, Zerocap Pty Ltd is a Corporate Authorised Representative (CAR: 001289130) of AFSL 340799

All material in this website is intended for illustrative purposes and general information only. It does not constitute financial advice nor does it take into account your investment objectives, financial situation or particular needs. You should consider the information in light of your objectives, financial situation and needs before making any decision about whether to acquire or dispose of any digital asset. Investments in digital assets can be risky and you may lose your investment. Past performance is no indication of future performance.