This week, we explore the case of BSV as a Turing machine. This topic delves into a very specialist field that is normally the realm computational theory, but I will attempt to address it in a way that applies to the general developers and focus on its practical applications instead of being pedantic about the theories.
Being Turing complete is a common term used to describe computer languages and systems, and centers on their ability to do the same thing as a theoretical machine, called a Turing machine. A Turing machine is a theoretical computer system and mental model which describes a machine with a read/write head, an arbitrarily long tape on which instructions can be written and read from, and a rule set. If a system can theoretically accomplish the same tasks as a Turing machine, then it is said to be Turing complete. Practically speaking, if a computer language is descriptive enough to execute computations complex enough that the result of the computation cannot be determined beforehand (analytically) without actually doing the computation, then it is Turing complete.
A common feature of computer languages which generally make them Turing complete is the ability for the language to allow for structured control flow of a program, either through loops or jumps. In computer science terms, a language must support sequencing, selection, and repetition. But the necessary condition for Turing completeness for languages is the support for conditional branching, or selection. It has been long thought that Bitcoin’s script wasn’t Turing complete, because it did not support looping, and therefore, the notion of branch execution didn’t seem possible. But thanks to the re-enabling of the original Bitcoin op-codes in BSV, it has now been shown that BSV is indeed Turing Complete, proved via simulating Conway’s Game of Life (a cellular automata which is known to be Turing complete) on a bitcoin script.
That is wonderful, but how does that affect the average programmer? It is one thing to theoretically be equivalent to a Turing machine, but an entirely different matter to have average developers be able to wrap their head around how to program computations into the system. We already know that the original criticism of Bitcoin script (made mostly by Ethereum developers and the original founders of the project) was that there is no facility for looping, or repetition in Bitcoin. This limitation was overcome by just unrolling the loops (much like what a compiler does in modern languages) as loops are just syntactic sugar for high level languages to achieve repetition. But how do we achieve the conditional branching required to do useful computation? Besides which, every bitcoin script output is simply a predicate, it only can evaluate to TRUE/FALSE, so how do we get more complex computations out of it?
Simply speaking computation can be simply getting an output from a predefined function, given specific inputs.
Most generally we want to be able to do:
y = f(x)
Where y is the output desired, f is the function that is the computation algorithm constructed beforehand, and x is the specific instance input.
So how do we do this on Bitcoin?
We certainly can put functions to be evaluated into Bitcoin transactions outputs (coins). These can sit there in the blockchain until such time in which they are executed when given an input x. These take the form of locking scripts in Bitcoin, which is what needs to be unlocked (by way of an unlocking script) when you want to spend the output. Therefore in Bitcoin, the ‘x’ takes the form of an unlocking script, and the ‘f’ is the locking script that was previously put into an output (with some associated bitcoins).
But if a given ‘f’ is public on the blockchain, and anyone can spend it by giving it any arbitrary ‘x’ as an unlocking script, then this wouldn’t be terribly useful right?
Right.
So one way of solving this is the method of passing transactions around in payment channels, and only seen by intended parties (off chain). This way, they won’t just unlock the f with an arbitrary x, but only the inputs that were requested or needed. Why they would do so is likely due to some locked funds in the channel which were already pre-negotiated with the computation requester beforehand.
Another technique that may be employed could be the use of un-finalized transactions. Transactions on BSV are not mineable until all the inputs have been marked finalized, so one way to ensure that a transaction isn’t published before it is ready is by repeatedly signing incremental versions of the same transaction, successively, between nodes, and not finalizing the inputs until the desired output y has been produced.
One can imagine a method by which a requester of computation could put a function f into the network, and then publish an un-finalized transaction into the network, with the needed input x, and allowing arbitrary parties to execute the f and publish an updated transaction with the output y as an output. Then the requester could finalize the transaction which would allow the transaction to be mined and thus paying for the computation and its result.
How about function composition?
i.e.
y = h(g(f(x)))
Namely, being able to take previous outputs, and chain them as inputs into the next function to be executed?
Successive functions can be chained, or sequenced, by successively passing transactions back and forth between the requester and the network. The requester would post the initial un-finalized input which would contain the x that would be input for the computation along with the sequence of functions that need to be executed in succession, namely, f, g, h. The network of computing nodes would then compete to be the first to chain f, g, and h together as inputs in the txn, in order to produce the final output y.
The key point is that the actors in the BSV computational network is just a requestor, which specifies the functions to be executed, in what sequence, and with what initial input x. Conditional branching can be achieved by controlling which functions are made spendable. The one thing we have to rely on is that the network of nodes as a whole will do the work of selecting and creating the txns that compute and produce an output, because by doing so they will be able to pay themselves a bitcoin reward. So unlike a normal computer that executes code because it is hardwired to do so, the Bitcoin computer executes code because we can rely on the fact that some node out there will want to make money, and do the computation, so that they can earn money.
New to blockchain? Check out CoinGeek’s Blockchain for Beginners section, the ultimate resource guide to learn more about blockchain technology.
