3 ms·

Yes, the Turing completeness of Ethereum means it suffers from the unsolvable halting problem. There is no way to prove that a given Ethereum program does not h

Yes, the Turing completeness of Ethereum means it suffers from the unsolvable halting problem. There is no way to prove that a given Ethereum program does not have a bug that will cause it to halt at some point in the future. Thus it is dangerous to rely on an Ethereum contract as the sole means of releasing funds. The voting problem is a more obvious flaw. There seems to be a naive optimism on the part of certain developers that simple voting rules will surface the best quality viewpoints. This is fine in hackernews, but is not OK for open source software development.

zeven7 10y ago
All Ethereum contracts halt. Performing operations requires spending ether (which is paid to miners) and there's a maximum amount of ether which can be spent per transaction. The more operations your contract performs, the more you have to pay. If you try to perform too many operations, the miner will bail.
- zekevermillion 10y ago
  OK, but that is not "halting" in the sense of the halting problem. That is a design feature of ETH.
  - zeven7 10y ago
    But wasn't your argument that "Ethereum ... suffers from the unsolvable halting problem" and that "there is no way to prove that a given Ethereum program does not have a bug that will cause it to halt at some point in the future"? All Ethereum transactions can be proven to halt. That does of course mean Ethereum isn't really Turing complete, just an approximation.
    - zekevermillion 10y ago
      Any program running on a Turing machine is subject to the halting problem. You may very well find a bug or feature that causes such a program to stop running or halt. This discovery still does not disprove the statement, that it is impossible to prove a program will not halt. Thus your observation does not flow logically.
      - EdHominem 10y ago
        As pointed out, Ethereum is not infinite, thus not a Turing machine, and therefore does not exhibit a "halting problem". There's a limit to the number of "cycles" spent on each program in proportion to how much funding they have. It's like a smaller version of the halting problem where you only have to say if a program will halt in five seconds or not. Turing machines are a theoretical construct, be careful when trying to reason about the real world based on them.

zeven7 10y ago

All Ethereum contracts halt. Performing operations requires spending ether (which is paid to miners) and there's a maximum amount of ether which can be spent per transaction. The more operations your contract performs, the more you have to pay. If you try to perform too many operations, the miner will bail.

zekevermillion 10y ago
OK, but that is not "halting" in the sense of the halting problem. That is a design feature of ETH.
- zeven7 10y ago
  But wasn't your argument that "Ethereum ... suffers from the unsolvable halting problem" and that "there is no way to prove that a given Ethereum program does not have a bug that will cause it to halt at some point in the future"? All Ethereum transactions can be proven to halt. That does of course mean Ethereum isn't really Turing complete, just an approximation.
  - zekevermillion 10y ago
    Any program running on a Turing machine is subject to the halting problem. You may very well find a bug or feature that causes such a program to stop running or halt. This discovery still does not disprove the statement, that it is impossible to prove a program will not halt. Thus your observation does not flow logically.
    - EdHominem 10y ago
      As pointed out, Ethereum is not infinite, thus not a Turing machine, and therefore does not exhibit a "halting problem". There's a limit to the number of "cycles" spent on each program in proportion to how much funding they have. It's like a smaller version of the halting problem where you only have to say if a program will halt in five seconds or not. Turing machines are a theoretical construct, be careful when trying to reason about the real world based on them.