Glossário

Turing Completeness

Easy

Turing completeness refers to the capability of a system or programming language to solve any problem that can be solved by a machine created by mathematician Alan Turing.

What Is Turing Completeness?

Turing completeness refers to the capability of a system or programming language to solve any problem that can be solved by a machine created by mathematician Alan Turing. It signifies the ability of a system or language to carry out any calculation that a general-purpose computer can perform.

This concept holds significance in the field of computer science as it determines the power of different systems and programming languages. If a system is deemed Turing complete it means it has the capacity to execute any computation that a computer's capable of. Conversely, if a system is not Turing complete it implies limitations, in its abilities.

How Do You Determine Turing Completeness?

A system can be considered Turing complete if it meets the criteria;

1. Input/output operations; The system must have the capability to read data and generate output.
2. Conditional branching; It should be able to alter its behavior based on computation results.
3. Loop constructs; The system must have the ability to repeat sets of instructions times.
4. Computation; It should have the ability to perform any calculation that can be done by a Turing machine.

After establishing these properties it can be concluded that the system meets the criteria of being Turing complete. However, it's important to note that being Turing complete in theory doesn't automatically mean the system is practical or efficient for all calculations.

Is ETH Turing Complete?

Yes, Ethereum is indeed classified as Turing complete. It functions as a decentralized and open source platform that facilitates contracts. Smart contracts are self executing agreements where the terms and conditions between buyers and sellers are directly encoded into lines of code.
To accomplish this, Ethereum employs a programming language called Solidity for writing contracts. These contracts are subsequently executed on the Ethereum Virtual Machine (EVM). The EVM is characterized as Turing complete since it has the capability to perform any computation that can be described in a form. This empowers developers to construct applications on the Ethereum platform, capable of executing a wide range of computations.

Is Bitcoin Turing Complete?

No, Bitcoin does not possess the attribute of being Turing complete. It operates as an open-source cryptocurrency functioning on a network. Its primary objective is to enable decentralized value transfers between individuals.

In contrast to Ethereum, Bitcoin does not support logic. The scripting language employed in Bitcoin transactions is limited in scope. It lacks the ability to perform computations. Consequently, Bitcoin cannot be classified as Turing complete since it lacks the capacity to execute computations described by algorithms.

The decision to implement this design was deliberate aiming to enhance the security of the system and reduce the risk of errors or potential harm caused by entities. Nonetheless, it also implies that Bitcoin lacks the ability to provide the extent of complexity and functionality as a Turing platform such as Ethereum.