Business 24 March 2018

Jasmine Solana

Bitcoin’s scripting language is Turing complete, paper shows

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.

Note: Tokens on the Bitcoin Core (SegWit) chain are referenced as BTC coins; tokens on the Bitcoin Cash ABC chain are referenced as BCH, BCH-ABC or BAB coins.

Bitcoin Satoshi Vision (BSV) is today the only Bitcoin project that follows the original Satoshi Nakamoto whitepaper, and that follows the original Satoshi protocol and design. BSV is the only public blockchain that maintains the original vision for Bitcoin and will massively scale to become the world’s new money and enterprise blockchain.

COMMENT

latest news

Lawmakers vote to force Swiss gov’t to adopt crypto regulations

Business 7 hours ago

Lawmakers vote to force Swiss gov’t to adopt crypto regulations

In a landmark moment for Switzerland, the lower house of parliament has voted in favor of a motion that aims to instruct the country’s Federal Council to apply existing financial regulations to cryptocurrencies.

Read More
New committee seeks to aid lawyers representing QuadrigaCX users

Business 7 hours ago

New committee seeks to aid lawyers representing QuadrigaCX users

The two law firms representing the customers of failed crypto exchange QuadrigaCX have formed a steering committee to help them in the case against the now-shuttered exchange.

Read More
Caspian launches crypto derivative trading

Business 9 hours ago

Caspian launches crypto derivative trading

Caspian, a trading and portfolio management platform backed by Galaxy Capital, is starting trade in cryptocurrency derivatives.

Read More