Written by :
Published on :
There is a controversy that's been emerging in the cryptocurrency community that claims Bitcoin cannot be used as a turing complete system. In computability theory, a system of data-manipulation rules is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine, meaning the ability to recognize or decide other data-manipulation rule sets.
“Unfortunately, a major problem stems from a lack of understanding of many common terms today. Turing completeness does not require an infinite tape, and it was not an infinite tape that Turing mentioned in his paper; it was an unbounded system. Importantly, you cannot have a Turing machine with an infinite tape rather than an unbounded tape—by definition. An infinite tape is not related to a problem that can be computed,” Bitcoin co-founder Dr. Wright said.
He asserts that Bitcoin is demonstrably a Turing complete system, hitting back against criticisms from the BTC Core community.
“Bitcoin is a Turing-complete system even in script. A Turing machine assumes that you have an unbounded tape. In our instance, it would mean an unbounded script size. Given an arbitrarily long script, you can run any possible computable algorithm. The fact that the size of the script becomes unwieldy is irrelevant. Not all Turing machines are efficient. In fact, there is nothing in the foundations of Turing machines that requires efficiency. Whilst it is possible to run many programs that will take a seemingly considerable time to complete, the process of optimising them through parallel paths or through approximation may be sufficient,” according to Dr. Wright.
“The main reason Bitcoin Core attacks the comment that I have made, of Bitcoin being Turing-complete, is related to the introduction of limits that were originally temporarily imposed upon Bitcoin and that have been implemented in more insidious manners within BTC. Whereas I said that Bitcoin would grow to the point where it would end in data centres, they wished to create a separate system, one that was more limited. A limited tape is not one that can run any algorithm. In other words, with a limited transaction size, you can never achieve the same level of computation as you can with an unlimited transaction size.
“As Rogers (1959) demonstrated, degrees of computational unsolvability exist, but it does little to remove the fact that we don’t know, in many cases, whether a program is solvable or not until it is run. Worse still, as Gaboury (1942) and later Rogers (1958) demonstrated, there is no solution addressing whether we can even find a solution to many problems.”
- Aaron Goldstein, Gambling911.com
