10

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?
10

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.

  • 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 Nov 25 '13 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 Nov 25 '13 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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