Bitcoin’s scripting language is Turing complete, paper shows

Getting your Trinity Audio player ready...

A new research paper authored by nChain Chief Scientist Dr. Craig Wright has demonstrated that Bitcoin’s dual stack push down automata (2-PDA) scripting language is capable of computing values computable in a system compatible with that of Godel’s logic system.

The paper, titled “Beyond Godel,” described a process in which the basic predicate systems used in Kurt Gödel’s logical constructions can be mapped directly into Bitcoin script operations, alongside primitive recursive functions. This, in turn, can be extended to explore the 2-PDA construction within Bitcoin.

A 2-PDA is a “two-way deterministic finite automation” which has already been proven to be as computationally effective as a 3-PDA, a fact that Wright has previously stated in his talks to highlight that 2-PDAs are Turing complete. 2-PDA, according to Wright, allows anyone to do everything that a Turing machine can achieve. It’s a known fact that 2-PDA is functionally equivalent to a Turing machine and can simulate a single or multi-tape Turing machine just as it can simulate a 2-PDA.

Turing completeness is used to describe a computer or software that can solve any problem that a Turing machine. To put it simply, a system that can execute any algorithm—like Bitcoin’s scripting language—is Turing complete.

In his new paper, the nChain chief scientist further explained that integrating basic predicate systems and primitive recursive functions across 2-PDA “allows us to create a system that is equivalent to a Turing machine,” which can handle all grammatical constructs that may be processed within a Turing machine.

“The richness and power of Bitcoin scripting language has been overlooked due to the complexity of the system,” Wright wrote. “In this paper we have demonstrated the true power of the system and how a complete implementation can create a script of a determined length and known maximum processing difficulty.”

Read Dr. Wright’s new paper, “Beyond Gödel,” here.