Bitcoin is Turing Complete

During nChain’s presentation at “The Future of Bitcoin” conference in Arnhem, Netherlands, Dr Wright made mention again that Bitcoin is ‘Turing complete’. But he did go into some detail this time. I cannot over-emphasise the gravity of this statement.

If Bitcoin is Turing complete, then it has incredible applications that most of us have not even come to think about just yet.

His explanation follows that Bitcoin completes the Predicate system Godel hypothesised.

In his talk at the conference, Wright states that “Bitcoin is a 2-PDA”. A 2-PDA is a ‘two-way deterministic finite automation” which has already been proven to be as computationally effective as a 3-PDA, but Wright restates this fact during his talk to highlight that 2-PDAs are Turing complete.

Turing completeness is a term used to identify a computer or software that is capable of solving any problem that a Turing machine can. In layman’s terms, this means that it can execute any algorithm.

Therefore, by stating that Bitcoin is Turing complete, it means that we are not just talking about ‘scripting’, we are talking about low level instruction execution.

In the next slide during his talk, Wright explains that Wolfram 110 is in Bitcoin and that it was running for 2 years, but only stopped in the last few months due to the fees. Wolfram 110 is known to be Turing complete.

In personal correspondence, Dr Wright was explaining the purpose of the 2 stacks, and how a 2-PDA can do everything a 3-PDA can, and then says “now you know what the alt-stack is for”. He was referring to Bitcoin.

And yes, it’s in there in the code.

Wright believes that BTC is a Total Turing Machine (TTM) – the first one to ever come into existence outside a lab:

In private correspondence:

“Bitcoin is what is known as a decider. There is very little written on this concept, and I believe bitcoin is the first system to implement a completely total system as a Turing machine”

“All deciders are able to be statically analysed. This means that they can be determined in advance. They do not have the Gas problem…. Ethereum has a huge issue that most have not seen yet. It collapses.”

“As a 2PDA, bitcoin can do remarkably more than anyone knows, but soon they are going to learn just how much.”

I believe nChain’s intention is that they will produce something in this area very soon.

Some of the work that nChain will be producing will be patented work, and some of it will not be. Rest assured, none of patents concern Bitcoin itself directly. Wright states “you cannot patent bitcoin. It surprises me how many people misunderstand the system. What you can patent are the new novel ideas. They can be extensions to existing protocols that make it better but you can never patent prior art.”

I’m looking forward to seeing nChain’s reveals in the very future. There’s been much kept intentionally under cover, but Dr Wright, who is Chief Scientist at nChain, has promised there will be many reveals in the next weeks and months.

When I asked about Ethereum he responded with:

“Bitcoin can do anything Ethereum does, but in a form that is statically analysable. It is a new form of security model, so I do understand people not seeing it yet.”

Dr Wright promises that the papers concerning Bitcoin being a decider (which will be heavy in lambda calculus!) will be published soon. I certainly look forward to the publication.

Eli Afram
@justicemate