4 ms·

> But often mathematical models are more informative and interesting than the concrete physical objects they abstract. Yes, I agree. But a model of a machine

> But often mathematical models are more informative and interesting than the concrete physical objects they abstract. Yes, I agree. But a model of a machine with finite states is more informative and interesting for applying it to real-world computers than a model of a Turing machine. Why? Because the first model tells you the Halting problem is decidable and the second one tells you it's undecidable. And as I mentioned, for programs running on real-world computers the Halting problem is decidable.

UncleMeat 4y ago
> But a model of a machine with finite states is more informative and interesting for applying it to real-world computers than a model of a Turing machine. I don't agree at all. I do static analysis for my career. Trying to model the actual set of available memory configurations of a physical machine is going to scale way way way worse for most meaningful problems than approaching this the usual way.
- wizeman 4y ago
  > I don't agree at all. I do static analysis for my career. Trying to model the actual set of available memory configurations of a physical machine is going to scale way way way worse for most meaningful problems than approaching this the usual way. I don't really understand your argument. I didn't say anything about how you need to solve problems like those described by the Halting problem and Rice's theorem for finite-state machines. So I'm not constraining how you would have to solve this issue. You can model the memory configuration if you want. But you don't have to model it in your algorithm. It's just that your algorithm is allowed to assume that the amount of memory available for the program being analyzed is finite (if it wants to). But anyway, the complexity / efficiency of an algorithm that solves the problem is a different issue that than the decidability of the problem, the latter of which many people get it wrong.
  - UncleMeat 4y ago
    > So I'm not constraining how you would have to solve this issue. You can model the memory configuration if you want. But you don't have to model it in your algorithm. It's just that your algorithm is allowed to assume that the amount of memory available for the program being analyzed is finite (if it wants to). What I am saying is that in practice, for the huge majority of interesting problems, it is not useful to finitize the actual program but instead to abstract over the program that assumes no meaningful resource constraints. Wandering off down a road of looking for efficient algorithms that take advantage of the actual finite nature of real programs will only harm you in the enormous majority of cases. > But anyway, the complexity / efficiency of an algorithm that solves the problem is a different issue that than the decidability of the problem, the latter of which many people get it wrong. Again, people only "get it wrong" if you are being maximally pedantic in a way that provides negative value to thinking about these problems.
    - wizeman 4y ago
      > What I am saying is that in practice, for the huge majority of interesting problems, it is not useful to finitize the actual program but instead to abstract over the program that assumes no meaningful resource constraints. Wandering off down a road of looking for efficient algorithms that take advantage of the actual finite nature of real programs will only harm you in the enormous majority of cases. You may very well be correct, but there's no formal result that proves that, right? So your assertion could be wrong. > Again, people only "get it wrong" if you are being maximally pedantic in a way that provides negative value to thinking about these problems. If everyone believed that the Halting problem is undecidable, then nobody would even try to find cycle detection algorithms. Fortunately, some people have proven that these algorithms exist and have created such algorithms. Some have even created new such algorithms, improving their efficiency. I just want more people to try and find more efficient versions of those, which is why we should not be spreading mistaken beliefs that the Halting problem is undecidable when a program runs on a computer. Which is why I would argue, in fact, that saying the Halting problem is undecidable is what provides negative value, because this is only of theoretical interest and generally speaking, it's only a useful result in practice if the program you're analyzing is trying to solve a mathematical question (i.e. one about infinity). For most real-world programs, the question of whether they would halt (or whether they behave correctly, in general) if they weren't allowed to consume infinite memory is much more interesting and useful, and actually decidable! So let's focus instead on improving the time complexity of such algorithms. Let's not focus on saying that they are impossible to solve, which prevents from focusing on the former.

UncleMeat 4y ago

> But a model of a machine with finite states is more informative and interesting for applying it to real-world computers than a model of a Turing machine. I don't agree at all. I do static analysis for my career. Trying to model the actual set of available memory configurations of a physical machine is going to scale way way way worse for most meaningful problems than approaching this the usual way.

wizeman 4y ago
> I don't agree at all. I do static analysis for my career. Trying to model the actual set of available memory configurations of a physical machine is going to scale way way way worse for most meaningful problems than approaching this the usual way. I don't really understand your argument. I didn't say anything about how you need to solve problems like those described by the Halting problem and Rice's theorem for finite-state machines. So I'm not constraining how you would have to solve this issue. You can model the memory configuration if you want. But you don't have to model it in your algorithm. It's just that your algorithm is allowed to assume that the amount of memory available for the program being analyzed is finite (if it wants to). But anyway, the complexity / efficiency of an algorithm that solves the problem is a different issue that than the decidability of the problem, the latter of which many people get it wrong.
- UncleMeat 4y ago
  > So I'm not constraining how you would have to solve this issue. You can model the memory configuration if you want. But you don't have to model it in your algorithm. It's just that your algorithm is allowed to assume that the amount of memory available for the program being analyzed is finite (if it wants to). What I am saying is that in practice, for the huge majority of interesting problems, it is not useful to finitize the actual program but instead to abstract over the program that assumes no meaningful resource constraints. Wandering off down a road of looking for efficient algorithms that take advantage of the actual finite nature of real programs will only harm you in the enormous majority of cases. > But anyway, the complexity / efficiency of an algorithm that solves the problem is a different issue that than the decidability of the problem, the latter of which many people get it wrong. Again, people only "get it wrong" if you are being maximally pedantic in a way that provides negative value to thinking about these problems.
  - wizeman 4y ago
    > What I am saying is that in practice, for the huge majority of interesting problems, it is not useful to finitize the actual program but instead to abstract over the program that assumes no meaningful resource constraints. Wandering off down a road of looking for efficient algorithms that take advantage of the actual finite nature of real programs will only harm you in the enormous majority of cases. You may very well be correct, but there's no formal result that proves that, right? So your assertion could be wrong. > Again, people only "get it wrong" if you are being maximally pedantic in a way that provides negative value to thinking about these problems. If everyone believed that the Halting problem is undecidable, then nobody would even try to find cycle detection algorithms. Fortunately, some people have proven that these algorithms exist and have created such algorithms. Some have even created new such algorithms, improving their efficiency. I just want more people to try and find more efficient versions of those, which is why we should not be spreading mistaken beliefs that the Halting problem is undecidable when a program runs on a computer. Which is why I would argue, in fact, that saying the Halting problem is undecidable is what provides negative value, because this is only of theoretical interest and generally speaking, it's only a useful result in practice if the program you're analyzing is trying to solve a mathematical question (i.e. one about infinity). For most real-world programs, the question of whether they would halt (or whether they behave correctly, in general) if they weren't allowed to consume infinite memory is much more interesting and useful, and actually decidable! So let's focus instead on improving the time complexity of such algorithms. Let's not focus on saying that they are impossible to solve, which prevents from focusing on the former.