Obviously all EVM programs halt, otherwise the Ethereum network would be completely ruined immediately. You already know why they halt: there's a gas limit.
Ethereum programs aren't Turing complete. They always halt. Turing complete programs don't generally halt. That's the definition.
You should demonstrate your understanding by using these terms correctly!
This whole argument about Turing completeness is a huge red herring.
The Parity multisig attack was an extremely simple programming error that has nothing to do with Turing completeness.
That people put their trust in such a contract despite its source code being obviously wrong points to the real problem.
The real problem right now is the lack of convenient tools and established practices for formal verification. If you think formal verification is impossible for EVM, you're wrong and you fundamentally misunderstand computation.
I've seen this criticism over and over again on internet forums: "EVM is so stupid, it can't be formally verified because it's Turing complete."
It's totally wrong: EVM isn't Turing complete, and it doesn't matter.
Look at "The Art of Computer Programming." It's full of Knuth's proofs of the correctness of algorithms written in assembler and imperative code. Look at any proof of correctness of a sorting algorithm.
OBVIOUSLY you can prove the correctness of programs written in Turing complete languages. You just look at the specification of the language, formulate a specification of your program's intended behavior, and then prove that the code matches the specification. This is how formal verification works, regardless of Turing-completeness.
To clarify, what is the impact of Turing completeness on formal verification? It means that for some ARBITRARY program, you cannot ALWAYS prove that it halts.
But even with some non-Turing complete formalism, you obviously cannot automatically prove the correctness of an arbitrary program; that's just nonsense. You could be certain that the program halts, sure, but how valuable is that? Ethereum already guarantees that all programs halt using the very simple gas mechanism.
> You already know why they halt: there's a gas limit.
Did you actually read my post? I'm not claiming halting is a problem; it's merely an example of undecidability. The "gas limit" doesn't help in the cases where the program does halt with unexpected behavior.
> Turing complete programs don't generally halt. That's the definition.
Where did you get this nonsense? See [1] for the actual definition.
> attack was an extremely simple programming error
Yes, which is why it's stupid to use a language with a grammar that cannot be proven. If trivial mistakes happened in production code, how do you expect to find the subtle bugs that happen because of the complex interactions that occur in recursively enumerable grammars?
> prove the correctness of programs
You can do that for some programs, but not all. The point about grammars is there are classes of grammar that allow automatic verification. Using a recursively enumerable grammar instead of a regular or context-free grammar demonstrates a severe misunderstanding of either language theory, or secure/safe engineering practices.
int_19h description[2] of some of the insane parts of Solidity suggests a PHP-style fractal of bad design[3], not a platform for proving correctness.
If you can't prove the correctness of your program, you shouldn't run it. Why are you concerned with proving the correctness of arbitrary programs? Can you give an example of an Ethereum-like program that can't be proven correct?
Here's how reasonable Ethereum contract development should happen. You construct the contract, either in some high level language or in bytecode. Then you prove, using some reasonable formalism (TLA+, Isabelle, paper, symbolic execution, or whatever), that the contract does what it should do. Then people who want to trust the contract look at this proof.
This is not at all hindered by the EVM being quasi Turing complete, because at no point do you have the question "How can I mechanically verify halting of an arbitrary program?"
Ethereum programs aren't Turing complete. They always halt. Turing complete programs don't generally halt. That's the definition.
You should demonstrate your understanding by using these terms correctly!
This whole argument about Turing completeness is a huge red herring.
The Parity multisig attack was an extremely simple programming error that has nothing to do with Turing completeness.
That people put their trust in such a contract despite its source code being obviously wrong points to the real problem.
The real problem right now is the lack of convenient tools and established practices for formal verification. If you think formal verification is impossible for EVM, you're wrong and you fundamentally misunderstand computation.
I've seen this criticism over and over again on internet forums: "EVM is so stupid, it can't be formally verified because it's Turing complete."
It's totally wrong: EVM isn't Turing complete, and it doesn't matter.
Look at "The Art of Computer Programming." It's full of Knuth's proofs of the correctness of algorithms written in assembler and imperative code. Look at any proof of correctness of a sorting algorithm.
OBVIOUSLY you can prove the correctness of programs written in Turing complete languages. You just look at the specification of the language, formulate a specification of your program's intended behavior, and then prove that the code matches the specification. This is how formal verification works, regardless of Turing-completeness.
To clarify, what is the impact of Turing completeness on formal verification? It means that for some ARBITRARY program, you cannot ALWAYS prove that it halts.
But even with some non-Turing complete formalism, you obviously cannot automatically prove the correctness of an arbitrary program; that's just nonsense. You could be certain that the program halts, sure, but how valuable is that? Ethereum already guarantees that all programs halt using the very simple gas mechanism.