4 ms·

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 eve

• Pyxl101 9y ago
  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.
• nebabyte 9y ago
  It can, if you have the funds ;)