Turing Completeness
The concept of Turing completeness stems from Alan Turing’s definition of a Turing machine. I came across this concept after researching smart contracts. I saw that bitcoin’s used a Turing-incomplete script language vs Ethereum’s Turing-complete language, and it got me wondering what that actually meant.
After a bit of research the concept of a Turing machine and its completeness is pretty open-ended and almost feels philosophical.
A Turing-complete language basically means the language can implement any possible algorithm. This does not mean the language is super complex and has the ability to do calculate inverse moduli with one function. All it means that the language can perform the basic calculative and logical functions that make up an algorithm. It may be a little hard to grasp but when we look at examples of Turing-incomplete languages and why they classified as such, it makes it a little easier to understand.
| Language | Reason |
| Haskell | Can not Implement Loops |
| Prolog | Can not Implement Loops |
| Data Languages (JSON, YAML, etc.) | Unable to do calculations/logic |
A programing language that is Turing-incomplete is actually pretty hard to find. It is actually so hard that there are many cases of being accidentally Turing-complete. One particular funny case is Microsoft Powerpoint, which caused it to “violate” Apple’s iOS app store guidelines, because it “could emulate alternate apps and execute arbitrary code. Here is a great youtube video that shows the Turing-completeness of Powerpoint.
Smart Contracts
Chances are if you have done any light research into cryptocurrencies, the word smart contract popped up once or twice. While it may seem like a new concept, it has actually been around since the early 1990’s. Nick Szabo was first one to coin the term and described it as, “a set of promises, specified in digital form, including protocols within which the parties perform on these promises”. Interesting fact: Nick Szabo designed a mechanism for decentralized digital currency called “bit gold” in 1998, it was never implemented but has been called the precursor to Bitcoin architecture
I like bullet points so here are come things that describe a smart contract:
- Computer program or transactional protocol
- Autonomous
- Used to execute, control or document contracts or agreements.
- Goal is to reduce needed for 3rd parties and increase trust
Vending machines are a great representation of how smart contracts work. It is a very “programatic” way of make an agreement. The vending machine provides an agreement that it will give you a drink for a set amount of money. If you put in less then the amount set, you don’t get the drink. However if you put in more money then the drink costs, you get the drink and change, which is based on the predefined agreement on how much the drink costs.
Vending machines are not perfect though, sometimes the drink gets stuck, the machine eats your money, or runs out of change. You basically need to trust the machine that is directly delivering your drink will work and not rip you off.
Smart contracts work in a similar way to a vending machine except the verification of the contract is done in a decentralized manner, this is beneficial because the verifying parties have no stake in the contract and have no bias toward either side. They do however benefit from validating the contract and receive a small fee for doing so, everyone wins!
Stay tuned for a more detailed deep dive into smart contracts and how they work and maybe even the math behind some of the hashing methods!
