I don't know anything about Ethereum, so this is probably a stupid question, but what prevents the contract writer from offering a huge per-cycle fee and then providing an algorithm which (non-trivially) doesn't halt?
The cycles are not free. The success of such an attack is limited by the amount of money the attacker has.
I was assuming that the attacker need only pay for completed machines (that reach a halted state).
If everyone pays for cycles regardless of whether or not the machines halt, could a malicious miner DOS the network by operating machines up until their final state minus one cycle?
(I'm asking dumb questions that are all answered in the referenced paper, just like ppl do when they don't read the original Satoshi paper, aren't I? Be honest....)