The halting problem in essence states that no algorithm can exists which determines whether or not a given algorithm will terminate given some input.
Ethereum makes the assumption that given a user-defined algorithm and a user-defined input, that within the limitations of the EVM whether or not the algorithm will halt can be determined. We know that that this can not be the case due to the halting problem. It may always be possible for there to be an implementation specific EVM-escape which could result in a catastrophic failure and loss of Ethereum for the end user.
If my memory serves me well, every step of any program in Ethereum will consume some 'ether' from a predefined stash, that is, someone has paid to run the program. As soon as the ether runs out, the program can not and will not continue.
This hack sidesteps the halting program entirely. Now, we can not know if a program can halt with a theoretical unlimited ether, but as there's no unlimited ether, all programs will halt.
Correct. "Gas" (some amount of Eth set aside for fees) covers the cost of running the contract, so you're free to run a non halting program - the EVM will happily accept however much gas you set aside and continue chugging along.
This isn't the first time PoS has been used to secure a coin, either. (With the number of altcoins out there that's not even surprising). Eth shifting to it would just represent the first major coin to use it.
> Ethereum makes the assumption that given a user-defined algorithm and a user-defined input, that within the limitations of the EVM whether or not the algorithm will halt can be determined.
No, it does not make that assumption. It simply limits the algorithm to a finite number of steps (opcodes in EVM) based on the amount of ether that was paid for.
Imagine an actual Turing machine - a symbol based ticker tape. Each operation of the machine is one step. You can run it for a given number of cycles and stop without knowing or needing to know whether the algorithm expressed through the Turing machine will halt or not.
So is Ethereum's VM simply not Turing complete, then? :) Since by its nature it can not possibly compute every Turing-computable function. If so, why was it even advertised as such?
edit: Haha okay, so I guess I'm not the only person who stumbled on this.
Ethereum's VM is computationally universal, aka Turing complete. You can compute any function.
I'd be happy to help clarify these concepts if I can, but I don't understand what you see is the tension between the halting problem and Ethereum.
Imagine that I run a processor for a certain amount of time, like 10 seconds. We start a stopwatch when we begin executing an algorithm, and then we pause the processor after 10 seconds pass. The processor performs a fixed number of operations each second, e.g., a 1 MHz processor does a million instructions.
If we decide to run a program and stop it after 10 seconds or 10 million instructions, that has no bearing on whether the processor's computational model (or a VM simulating the processor) is Turing complete. Deciding to stop the processor after 10 seconds is an analogy for an Ethereum transaction with "gas" for 10 million instructions.
If you wish, you can think of it as an "external" force is stopping the computation.
The talk that you linked claims that Ethereum isn't Turing complete, but that talk is either: wrong, making a nonsensical distinction, or making an extremely nitpicky distinction (depending on how you want to look at it). By the talk's reasoning, a general personal computer is not Turing complete either. The Turing model specifies a machine with infinite tape, so by the standard of the talk, no machines that humanity has ever made are Turing machines, and none of their execution models are Turing complete, because all of our machines have bounded memory. For similar reasons, the fact that Ethereum executes transactions with a bounded number of computations doesn't influence whether it is Turing complete in a useful sense of the term.
If this hasn't clarified things, then I'd suggest articulating the reason why you think the halting problem matters for Ethereum. The halting problem states that one cannot design an algorithm that determines whether all other algorithms will halt or not. So what? Ethereum does not depend on the existence of such an algorithm. Ethereum doesn't try to predict or analyze whether a program will halt - it simply runs the program and finds out! Since these programs are executed for a finite number of steps, then we know that all programs will halt, either by choosing to halt, or by exhausting their number of allowed steps.
The reason I say that it's wrong that "Ethereum is not Turing complete" is because the amount of "gas" for a transaction, and therefore the number of allowed steps, is arbitrary. You pay for gas when submitting a transaction, and so you can supply as much gas as is needed for any program that you wish to run. Because the user chooses how large the fixed bound is (and pays for it), Ethereum is Turing complete in a practical sense. If you make a mistake and submit a transaction with insufficient gas, then you can try again with a larger amount of gas. Most of the time, you can probably simulate the program yourself locally to determine how much gas it requires ... or you can just provide far more gas than the program is likely to need, since excess gas is returned.
My understanding was that programs are limited to a finite number of steps in the Etherium virtual machine.