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

CipherBlade share a lesson about crypto theft

Business 24 May 2019

CipherBlade share a lesson about crypto theft

Coinomi have been blamed for losing a customers funds, but a new investigation shows they probably weren’t to blame at all.

Read More
Brazilian police arrest culprits behind $210 million crypto scam

Business 24 May 2019

Brazilian police arrest culprits behind $210 million crypto scam

Brazil has cracked down on a massive pyramid scheme that brought in over 50 thousand victims.

Read More
Russia’s central bank expects crypto regulation bill in spring

Business 24 May 2019

Russia’s central bank expects crypto regulation bill in spring

A member of the Central Bank of Russia says she expects crypto regulations to kick in sometime in the spring of 2019.

Read More
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]