11

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 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?
Improve this question

1 Answer 1

Reset to default
11

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) 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.

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.

Improve this answer
2
  • 3
    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
    Commented Nov 25, 2013 at 17:13
  • 4
    @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
    Commented Nov 25, 2013 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.