4 ms·

Ethereum gets around the halting problem by using a "gas" model, where it halts your execution if you run out of gas before the program returns. If Ethereum is

Ethereum gets around the halting problem by using a "gas" model, where it halts your execution if you run out of gas before the program returns. If Ethereum is actually the PHP of cryptocurrencies, that puts it in a great spot for adoption.

keymone 6y ago
In any non-trivial program you will not know how much gas it requires to complete because that’s what it means - to solve the halting problem. What a great basis for your financial system handling all people’s economic interactions. What can possibly go wrong. I’ll stick with deterministic bitcoin script, thankyouverymuch.
- mvanaltvorst 6y ago
  You don't have to know how much gas it requires to /complete/, you can just run the program and check whether it runs out of gas before it exits. You do not need to solve the halting problem. Actually, it's pretty trivial to implement this and this model has scaled quite well considering the size of Ethereum today.
- throwingduck001 6y ago
  Determining whether a Turing machine halts within k steps is computable: https://math.stackexchange.com/questions/3370296/halting-problem-within-a-finite-time-interval https://math.stackexchange.com/questions/3370296/halting-pro... If the number of steps is specified in unary, then the problem is NP-complete: https://www.ics.uci.edu/~eppstein/161/960312.html https://www.ics.uci.edu/~eppstein/161/960312.html