On August 24, 2019, Craig S. Wright, a man wrote a conference paper titled Bitcoin, A Total Turing Machine. In Wright’s paper, Wright stated that he demonstrated the Bitcoin script language is capable of primitive recursion, but it can also deploy an Ackermann function. So, the Ackermann function can simply recurse within Bitcoin script: it is proof Bitcoin as a script system is Turing complete (link). Wright went a step further by introducing a new Turing machine class, the PTTM (probabilistic total Turing machine): it allowed him to find an artifact capable of acting as a verifier for a non-interactive, associated TM as a proof system. In typical use cases, Bitcoin is capable of secure contract offers including best fit solutions to logistic information systems, optimization problems such as the travelling salesman problem, and optimizing systems. In application, Bitcoin can be offered in 2 different contracts: open or time-bound contract, guaranteeing payment, but it allows the bidder to have pseudonymity.
In Wright’s case, a Turing complete program is defined as any halting program: only a decidable program halts. So, no Decidable program on a Turing complete system shall run forever: this means all decidable programs loaded onto a Turing complete system are finite.
But what is the meaning of this, in practical terms?
In a single sentence: given any computing algorithm, Bitcoin is capable of simulating any algorithm’s construction (i.e., operating systems to cloud data). So, Bitcoin has a wide amount of resources to gather its proof-of-work from each node (i.e., the financial proof it is worth something). In basic English, it should be able to simulate any algorithm on any computer (i.e., CPU or GPU). Right now, CPUs are faster and smarter than GPUs (link). But GPUs remain the standard for high performance parallel processing.