In trying to understand what Ethereum was, I was "thrown for a loop" on day one a bit. That was by the introduction regarding the halting problem--which is repeated currently on the Wikipedia entry:
Ethereum is a decentralized publishing platform featuring stateful user-created digital contracts and a Turing-complete contract programming language. Ethereum uses its underlying network unit, ether, as payment to execute Ethereum contracts as a workaround to the Halting Problem.
I didn't understand this statement then, before knowing what Ethereum was. Now after reading and being fairly confident I "get it" (arbitrary code and state storage engine, leveraging first-to-file concepts of bitcoin, decentralized ledger verification but *not* decentralized authority)...I still don't know how it is meaningful to invoke the halting problem to explain it.
Consider: if I ask Amazon Elastic Computing cloud why they charge me per processor cycle, or why I have to pay more for a larger disk, they don't snap back with: "because of the halting problem". Computation and storage requires resources: Turing-complete or not. If you are asking a network to do computation or storage on your behalf, it doesn't matter whether you can analyze a program to determine if it halts. The network must be willing to bear the burden of running your code and saving your data under some incentive.
So does anyone have a concrete answer as to why the halting problem is being invoked so often? How is the protocol in any way affected by its inability to determine if the contracts it is being asked to execute terminate or not? Why would the collective network agree to execute a long-running (but guaranteed to terminate...someday...) contract without cost?