A Brief Explanation of Turing Completeness and Smart Contracts

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.

Dnu72, CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0, via Wikimedia Commons

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
HaskellCan not Implement Loops
PrologCan not Implement Loops
Data Languages (JSON, YAML, etc.)Unable to do calculations/logic
Turing-incomplete Languages

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
Example of a Smart Contract

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!

Related Posts

Terraform Tips & Tricks – Part 1 – Building A Constant Reference

One of the most common problems I see in large organizations when working with terraform is consistency. When we have a large amount of resources being managed…

Istio Architecture Diagram

Everything You Ever Wanted to Know About Istio but Were Afraid to Ask

Istio is a powerful service mesh that integrates natively with Kubernetes, I have been using Istio as my service mesh, ingress, and egress gateways on my personal…

Envoy Modules Solar Monitoring Grafana Dashboard

How to Monitor Your Enphase Home Solar System with Telegraf

How to collect metrics from an Enphase Envoy PV system, with telegraf and influxdb.

Anthos on Bare Metal Architecture Diagram

How to Deploy Anthos on Bare Metal On-Prem

Introduction The main advantage of Anthos on BM over Anthos on VMWare for on-prem deployments is the ability to run Anthos clusters without a hypervisor license. Cluster…

OPA Gatekeeper Architecture

OPA Gatekeeper: Bringing Law and Order to Kubernetes

Introduction Open Policy Agent (OPA) is a policy based control agent that is able to be integrated on various platforms. For the sake of this document we…

Anthos GKE Cluster Traffic Diagram

How to Setup Anthos on GKE Autopilot with Private Certificate Authority

What You Will Create The guide will set up the following: 2 Private GKE autopilot clusters with master global access ASM with multicluster mesh IstioIngress gateway to…

Leave a Reply