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)
188w · thesis:0
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...
157w · thesis:0
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...
138w · thesis:3
From this, we can deduce that all Turing Complete programs and functions form a subset of the set of all possible programs. The set of all possible programs includes both those that halt on a Turing m...
118w · thesis:0
Wolfram’s conjecture that a 2-state 3-symbol Turing Machine is a UTM (Wolfram, 2002, p709) was proven in 2007[[4]](#_ftn4) by Smith (2007). Using the logic in Wright (2017), we can show that the predi...
116w · thesis:0
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...
104w · thesis:0
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...
102w · thesis:0
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...
97w · thesis:5
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, ...
97w · thesis:1
The problem is not whether a computer can be built that can run any conceivable decidable program (i.e. that halts). It becomes the problem of determining the most effective means to minimise the size...
86w · thesis:3
First, we define any Turing complete program to be a program that halts. Whilst it is true that we cannot determine in advance if any particular program will halt for any set of input data, we do know...
+ 13 more insights