Turing complete Smart Contracts for Turing Complete Virtual Machines


I’ve written a smart contracts that can execute code as an interpreter. While the programming language is primitive, it’s in fact universal, i.e. Turing complete.

So this project presents a computationally universal and programmable decentralized application along with a decentralized persistent program library on the NEO blockchain.

For example, it is the first smart contract on which general mathematical problems have been solved (from arithmetic all the way up to recognizing some unrestricted grammar) despite the source code not knowing anything about those tasks.

The dApp interprets encoded classical Turing machines, which is what a universal Turing machines does. The following documentation video elaborates on this in 7 parts:

00:01 Overview
06:55 Use of the dApp on the NEO testnet
11:38 Historical context
18:24 Turing completeness explained
54:40 In depth code review

The last 30 minutes cover the code in detail. The arguments for the main functions are two strings and an array of integers. The first string denotes an auxiliary name for a machine to be uploaded on the blockchain. For programmer convenience, a Turing machine can be encoded as a string and is provided as the second argument. For efficiency sake, beyond testnet use, the “Assemble” step should be performed offline before the machine is deployed. Once there is a machine with the chosen name on the blockchain, then when invoking this name again, the second argument is used as the input string for the machine and is executed. The third argument is an array of integers that can optionally be used to modify default specifications such as the size of used character alphabet and maximal runtime measures as actions on the Turing machine tape.

The programming language is explained in the forth part of the video in detail.

Hope you find this interesting :slight_smile: