<p>If scripts were Turing-complete, you could construct a fairly short script that took an extremely long time to run (a la the <a href="http://en.wikipedia.org/wiki/Busy_beaver">Busy Beaver</a>) or contained an infinite loop.  This would tend to result in a denial of service against everyone on the network, when they tried to verify the transaction.  </p>

<p>And there would be no general way to tell whether a script would loop infinitely or would eventually finish: that's the <a href="http://en.wikipedia.org/wiki/Halting_problem">halting problem</a>.</p>

<p>One could try to avoid this by including some sort of cutoff on how long a client will spend verifying a transaction, but it would have to be done very carefully so as to be consistent across all clients: if some accept it and others don't, the block chain will fork. </p>

<p>It seems simpler to avoid the situation all together.</p>

CC BY-SA 3.0
2013-11-25T17:13:38.100Z
If there was a limit, it would be better to have a limit on how many instructions could be executed rather than time spent, to ensure consistency
RentFree
CC BY-SA 3.0
2013-11-25T18:08:49.783Z
@RentFree: Which essentially reduces to what we have now.  If the script you want has a loop that is guaranteed to finish within a certain number of instructions, you can unroll the loop into a straight-line script with a fixed number of instructions.  Actually, as it stands, the number of instructions you execute, the number of bytes in the script, and the fee you pay, are all approximately proportional.
Nate Eldredge
CC BY-SA 3.0
2013-11-25T16:43:45.207Z
2013-11-25T21:29:19.250Z
2013-11-25T21:29:19.250Z
Nate Eldredge
<p>For me, scripts are one of the most interesting features of Bitcoin. They provide possibilities which have no equivalent in classical currencies. However, the <a href="https://en.bitcoin.it/wiki/Script">wiki</a> states</p>

<blockquote>
  <p>It is purposefully not Turing-complete, with no loops.</p>
</blockquote>

<ol>
<li>What's the rationale behind this decision?</li>
<li>Are there any proposals for useful contracts which would only be possible in a Turing complete script implementation?</li>
<li>Are there any alternative crypto currencies with Turing complete scripts? If so, how do they solve the problems from 1?</li>
</ol>

<transactions><script><development><alternatives><turing-completeness>
Turing completeness of Bitcoin Script
jnnk
# Turing completeness of Bitcoin Script

(Asked by: username_0 on 2013-11-25)

For me, scripts are one of the most interesting features of Bitcoin. They provide possibilities which have no equivalent in classical currencies. However, the [wiki](https://en.bitcoin.it/wiki/Script) states

> It is purposefully not Turing-complete, with no loops.

1. What's the rationale behind this decision?
2. Are there any proposals for useful contracts which would only be possible in a Turing complete script implementation?
3. Are there any alternative crypto currencies with Turing complete scripts? If so, how do they solve the problems from 1?

**Tags:** transactions, script, development, alternatives, turing-completeness


---

## 1 answers

### Answer by username_1 on 2013-11-25. Score: 11 | Accepted answer

If scripts were Turing-complete, you could construct a fairly short script that took an extremely long time to run (a la the [Busy Beaver](http://en.wikipedia.org/wiki/Busy_beaver)) or contained an infinite loop. This would tend to result in a denial of service against everyone on the network, when they tried to verify the transaction.

And there would be no general way to tell whether a script would loop infinitely or would eventually finish: that's the [halting problem](http://en.wikipedia.org/wiki/Halting_problem).

One could try to avoid this by including some sort of cutoff on how long a client will spend verifying a transaction, but it would have to be done very carefully so as to be consistent across all clients: if some accept it and others don't, the block chain will fork.

It seems simpler to avoid the situation all together.

> **Comments:**
> **username_2**: If there was a limit, it would be better to have a limit on how many instructions could be executed rather than time spent, to ensure consistency  
> **username_1**: @username_2: Which essentially reduces to what we have now.  If the script you want has a loop that is guaranteed to finish within a certain number of instructions, you can unroll the loop into a straight-line script with a fixed number of instructions.  Actually, as it stands, the number of instructions you execute, the number of bytes in the script, and the fee you pay, are all approximately proportional.  

---

