Hacker Read top | best | new | newcomments | leaders | about | bookmarklet login

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.



view as:

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.


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.

Determining whether a Turing machine halts within k steps is computable: 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


Legal | privacy