Turing completeness describes the ability of a system to solve an identical class of problems as on a simplified model of a programmable computer – a Turing machine. In other words, it is the ability of a computing system to simulate another computing system conditioned on resources such as time and memory. In today's article, we would like to tell you about Alan Turing and his contribution to science. 

Alan Turing – distinguished mathematician and logician

Alan Turing has become known in history as one of the fathers of modern computer science. He was born on 23 June 1912. From childhood, he showed exceptional mathematical ability. He received his education at Cambridge University, where his work led to the concept of a Turing machine – one that would be able to perform arbitrary calculations if they were algorithmically feasible. During the Second World War, he worked on breaking the Enigma. He was also a pioneer of artificial intelligence, creating the Turing test to determine whether a machine thinks in a human-like way. He passed away at the age of just 41, on 7 June 1954. 

Curiosity: An inverted form of the Turing test is the CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart), which determines whether a program is interacting with a human or, for example, an artificial intelligence bot. 

The Turing machine – operation 

In 1936, the mathematician proposed an abstract computational model that defines the theoretical basis for the operation of modern computers. A Turing machine consists of the following elements: an infinite tape divided into cells, a head that can read and write symbols on the tape and a set of rules controlling the head. The model allows arbitrary calculations to be performed if they are algorithmically possible and is able to simulate the operation of any other computer.

Turing completeness – definition

The Turing machine described above is the basis for defining Turing completeness, which is the ability of a computational system to perform calculations that are theoretically possible for the machine to perform. As mentioned in the introduction – if a programming language or computational system is Turing-complete, it can simulate any other computational system, assuming it has enough memory and time. 

Summary – what do cryptocurrencies and Turing completeness have in common? 

The Ethereum Virtual Machine (EVM) is said to be featured by Turing completeness. Operations on the Ethereum network require the use of gas to execute the provisions of smart contracts. Gas is a unit of measurement of the computational resources needed to complete a task. Its existence ensures that the network cannot loop. It also provides rewards for validators. Ethereum is characterised by Turing completeness, as the EVM allows any computation to be performed if adequate resources are provided. 

Naturally, Ethereum is not an isolated case of Turing completeness in the blockchain network. Many other prominent examples, such as Cardano, TRON, NEO, Tezos, Polkadot, Solana, and many others, also provide users with a variety of benefits and solutions while still featuring Turing completeness.