4 ms·
I keep wondering though if this can be thought of as a variation of the halting problem. I.e. it is a question of halting state rather than halting execution.
by einhverfr 13y ago
I keep wondering though if this can be thought of as a variation of the halting problem. I.e. it is a question of halting state rather than halting execution. The problem here seems to be the inverse:
Can you guarantee that, over time, the program sequence will not halt even if the individual programs in fact do halt.
"Halting" would have to be defined differently, i.e. with the capacity to resume.
Am I missing something?
- kevingadd 13y agoArguably since the transaction scripts don't loop, something resembling 100% branch coverage testing would probably suffice. The issue is classifying the test results: should the test succeed with these inputs, should it fail with these other inputs, etc. Given that the scripts are usually used to verify basic transactions, though, you could probably provide a few basic rules and autogenerate appropriate tests.
- einhverfr 13y agoArguably a mining approach that would require that miners return the transactions that can't complete to their previous individual could provide formal proof that it will not "halt" ever. It seems to me that the obvious issue is sending invalid transactions. If these are not handled and the bitcoins are lost that means that bitcoin itself must eventually disappear because some percentage of transactions will be bad and over time, the sum of all of these will lead to enough losses to ensure that there is no practical value to the remaining bitcoins. It seems to me that programs can be guaranteed not to halt a lot more than they can be guaranteed to halt.