Bitcoin: A Total Turing Machine
Date: 2022-12-05
Source: https://craigwright.net/blog/academics/bitcoin-a-total-turing-machine
We demonstrate that the Bitcoin Script language allows not only for primitive recursion, but in the deployment of an Ackerman function and hence the ability to simply recurse in Bitcoin script, we show that the script system is Turing complete.
Extracted Insights (23 total, showing top 10)
R8
We demonstrate that the Bitcoin Script language allows not only for primitive recursion, but in the deployment of an Ackerman function and hence the ability to simply recurse in Bitcoin script, we sho...
R8
In this paper, we demonstrate how Bitcoin’s scripting system forms the basis for a special class of Turing Machines called a decider (Sipser, 1996) or alternatively a total Turing machine (Kozen, 1997...
R7
Any program that is Turing complete is by necessity Finite. Although you cannot decide IF a program will halt, any program that is Turing Complete will halt by definition. Any program that does Halt, ...
R7
The power (and advantages) of such a system [[A3]](#_msocom_3) can be greatly extended in the development of extended compilers that take a high-level recursive construct (such as OP_ForLoop[[1]](#_ft...
R7
The consequence of these results is that the Bitcoin system is not constrained by the original deliberately imposed limitations on the scripting language. From its original conception, the scripting l...
R7
Many misconceptions exist as to the nature of a Turing machine and the capability of such a system. A Turing machine can solve a class of “effectively calculable” functions known as λ-definable functi...
R6
In (Wright, 2016) we demonstrate that the Script system deployed in Bitcoin is formed using the primitive recursive functions (Meyer and Ritchie, 1967). In (Wright, 2017) we extend this [[A2]](#_msoco...
R6
Any program that is decidable must halt. Consequently, it is bounded in time. We can hence state that for any program P(T) that is decidable and is run on a Turing Complete system that it is required ...
R6
It is noted that although we cannot determine if every program is decidable with certainty, we can develop a Total Turing Machine that requires that all programs are “unrolled” and hence are determina...
R6
The Bitcoin scripting language[[3]](#_ftn3) is a stack-based language similar to Forth. There are two stacks known as the main stack and the alt stack. Script commands, knowns as ‘OP_CODEs’ operate on...
+ 13 more insights