<p>Bitcoin Script isn't Turing complete in a single transaction scope for obvious reasons.</p>
<p>But is it Turing complete if we consider a transaction chain as the tape? Also no, because Bitcoin scripting language doesn't have transaction introspection opcodes, so there's no way for a program to carry the program state over to the next transaction to execute the next &quot;CPU cycle&quot;. Even if it were, to execute an infinite program you'd need to pay infinite fees :)</p>
<p>Introspection opcodes would enable theoretical Turing-completeness of transaction chains, there's been some work discussing this: <a href="https://www.semanticscholar.org/paper/Self-Reproducing-Coins-as-Universal-Turing-Machine-Chepurnoy-Kharin/05c6514c671d380cb2aa02ffa504bb4faca7b92c" rel="nofollow noreferrer">Self-Reproducing Coins as Universal Turing Machine, A. Chepurnoy, Vasily Kharin, D. Meshkov</a></p>
<p>Note that nodes wouldn't be automatically evolving the program. Some blockchain-external agent would have to construct the next transaction and broadcast it to the network. The program could code-in a reward for this and incentivize anyone to construct and post the next transaction, or external agents could do it for free. The program would halt when it runs out of money for the fees/incentives, but then again, other external agents could give it more money to continue evolving.</p>

CC BY-SA 4.0
2022-11-02T10:13:12.630Z
2022-11-02T12:49:06.443Z
2022-11-02T12:49:06.443Z
bca-0353f40e
<p>In this Medium Article (<a href="https://medium.com/@craig_10243/bitcoin-a-total-turing-machine-5a6c3c68f5a7#_ftn2" rel="nofollow noreferrer">https://medium.com/@craig_10243/bitcoin-a-total-turing-machine-5a6c3c68f5a7#_ftn2</a>), C. Wright states:</p>

<p>"...It is known that all primitive recursive functions are total and computable, in this paper we also demonstrate using the Ackermann function that the Bitcoin script constructs include the ability to extend to total computable functions that are not primitive recursive. This demonstrates that Bitcoin can incorporate total computable functions that are simply “recursive” as well as primitive recursive."</p>

<p>What does this mean in mathematical terms?</p>

CC BY-SA 4.0
2020-05-02T17:28:04.803Z
Craig Wright is a known conman. There is no point in trying to decode his gibberish.
Pieter Wuille
CC BY-SA 4.0
2020-05-03T02:15:10.213Z
It’s also not turing complete, in any sense of the word. You can not prove it is because it simply isn’t. It has a execution tape with defined opcodes, which have a specific and well understood limit.
Claris
CC BY-SA 4.0
2020-05-03T02:20:28.817Z
The meaningless article seems to be saying that with an infinitely sized execution tape you could run a program indefinitely, which while literally true assumes an infinitely sized transaction and infinitely long execution, which doesn’t exist in Bitcoin.
Claris
CC BY-SA 4.0
2020-05-04T06:12:05.510Z
@PieterWuille I would like to give it a shot from the point of an aspiring academic simply aiming to resolve some questions.
Abhinav
CC BY-SA 4.0
2020-05-04T06:14:01.423Z
@Anonymous Right got your point. I simply enquired about use of Ackermann functions in using proving Turingness of a Script.
Abhinav
<script><academic-research>
How does one prove total turingness of the bitcoin script using the Ackermann Functions?
Abhinav
# How does one prove total turingness of the bitcoin script using the Ackermann Functions?

(Asked by: username_0 on 2020-05-02)

In this Medium Article (<https://medium.com/@craig_10243/bitcoin-a-total-turing-machine-5a6c3c68f5a7#_ftn2>), C. Wright states:

"...It is known that all primitive recursive functions are total and computable, in this paper we also demonstrate using the Ackermann function that the Bitcoin script constructs include the ability to extend to total computable functions that are not primitive recursive. This demonstrates that Bitcoin can incorporate total computable functions that are simply “recursive” as well as primitive recursive."

What does this mean in mathematical terms?

**Tags:** script, academic-research

> **Comments:**
> **username_1**: Craig Wright is a known conman. There is no point in trying to decode his gibberish.  
> **username_2**: It’s also not turing complete, in any sense of the word. You can not prove it is because it simply isn’t. It has a execution tape with defined opcodes, which have a specific and well understood limit.  
> **username_2**: The meaningless article seems to be saying that with an infinitely sized execution tape you could run a program indefinitely, which while literally true assumes an infinitely sized transaction and infinitely long execution, which doesn’t exist in Bitcoin.  
> **username_0**: @username_1 I would like to give it a shot from the point of an aspiring academic simply aiming to resolve some questions.  
> **username_0**: @Anonymous Right got your point. I simply enquired about use of Ackermann functions in using proving Turingness of a Script.  

---

## 1 answers

### Answer by username_3 on 2022-11-02. Score: 1

Bitcoin Script isn't Turing complete in a single transaction scope for obvious reasons.

But is it Turing complete if we consider a transaction chain as the tape? Also no, because Bitcoin scripting language doesn't have transaction introspection opcodes, so there's no way for a program to carry the program state over to the next transaction to execute the next "CPU cycle". Even if it were, to execute an infinite program you'd need to pay infinite fees :)

Introspection opcodes would enable theoretical Turing-completeness of transaction chains, there's been some work discussing this: [Self-Reproducing Coins as Universal Turing Machine, A. Chepurnoy, Vasily Kharin, D. Meshkov](https://www.semanticscholar.org/paper/Self-Reproducing-Coins-as-Universal-Turing-Machine-Chepurnoy-Kharin/05c6514c671d380cb2aa02ffa504bb4faca7b92c)

Note that nodes wouldn't be automatically evolving the program. Some blockchain-external agent would have to construct the next transaction and broadcast it to the network. The program could code-in a reward for this and incentivize anyone to construct and post the next transaction, or external agents could do it for free. The program would halt when it runs out of money for the fees/incentives, but then again, other external agents could give it more money to continue evolving.


---

