3 ms·

You are making this unnecessarily complicated. Remember that all models are wrong, but some of them are useful. Turing machines and other similar formalisms hav

You are making this unnecessarily complicated. Remember that all models are wrong, but some of them are useful. Turing machines and other similar formalisms have proven useful models of real computers. Things that are logically impossible on Turing machines appear to be effectively impossible on real computers, at least in the worst case. Using cycle detection for solving the finite version of the halting problem is a good example of this. You are not even trying to solve the problem. You are simply brute-forcing it by running two copies of the program at different speeds and comparing their internal states. An actual solution would try to analyze the program to see whether it a) halts; b) enters a cycle; or c) attempts to use more memory than the space bound. But it feels unnatural that you could do that analytically without being able to say that the program attempts to use ever-increasing amounts of memory. Based on what we understand of computation, it's more plausible that analyzing a program is impossible in the general case, and finite bounds simply give us the ability to simulate the outcome. After computability theory was "solved", complexity theory became the new frontier. But it turned out to be much harder. While you can teach many of the key proofs in computability theory to undergrads, complexity theorists still haven't managed to solve basic questions like P vs. NP. While you can simulate an arbitrary program, reasoning about its behavior seems to be effectively impossible in the general case.

wizeman 4y ago
> Things that are logically impossible on Turing machines appear to be effectively impossible on real computers, at least in the worst case. My problem is when Turing machines are used to justify something being true when it is actually false for the vast majority of cases that we actually care about. Sure, the problem is undecidable if your program requires infinite memory because it's trying to solve some mathematical problem (i.e. something related to infinity). But for most programs, we would actually prefer knowing whether they will run into a memory limit or whether they cycle forever (or not), which is a decidable problem. > You are not even trying to solve the problem. You are simply brute-forcing it by running two copies of the program at different speeds and comparing their internal states. Indeed! But at least now we know that it's possible to solve the problem. So here's a question which is actually more interesting, now that we know it's possible to solve it: can we solve the same problem without simulating how the program runs step-by-step? Or in other words, can we reduce the time complexity and/or increase the efficiency of such algorithms? That's the actual interesting question to me. I agree with the rest of your comment.
- jltsiren 4y ago
  > So here's a question which is actually more interesting, now that we know it's possible to solve it: can we solve the same problem without simulating how the program runs step-by-step? Despite a century of research, simulation is still pretty much the only tool we have. Simulation can also be used to rule out many hypothetical solutions using similar tricks to the proof of Rice's theorem. Assume that program A, with input X, decides whether program X with input X halts within a fixed resource bound. Assume that the resource bound is high enough that running A with an input of size |A| + C, for a reasonable constant C, uses much less resources than the bound. Then we can write a program A' that runs A with the input. If A says that the input halts (within the bound), A' enters an infinite loop. If A says that the input does not halt (within the bound), A' halts. If we run A' with input A', it halts iff A says A' does not halt (within the bound) with input A'. We can avoid the situation by allowing A to make mistakes, by allowing it to say "don't know", or by allowing it to exceed the resource bound.
  - wizeman 4y ago
    > or by allowing it to exceed the resource bound. Exactly. When running A, in some cases you would necessarily need more memory to run it than the memory bound that you defined for the input program, if you want it to work for all input programs without mistakes and without saying "don't know". But that doesn't say anything about the time complexity, or does it?
    - jltsiren 4y ago
      The same argument applies to time complexity as well. A' is A plus some trivial logic, so its running time should be marginally higher. A' halts with input A' iff A says A' does not halt within the desired time bound with input A'. That's a contradiction if A is substantially faster than the time bound.
      - deleted 4y ago
        [deleted]
      - 4y ago

wizeman 4y ago

> Things that are logically impossible on Turing machines appear to be effectively impossible on real computers, at least in the worst case. My problem is when Turing machines are used to justify something being true when it is actually false for the vast majority of cases that we actually care about. Sure, the problem is undecidable if your program requires infinite memory because it's trying to solve some mathematical problem (i.e. something related to infinity). But for most programs, we would actually prefer knowing whether they will run into a memory limit or whether they cycle forever (or not), which is a decidable problem. > You are not even trying to solve the problem. You are simply brute-forcing it by running two copies of the program at different speeds and comparing their internal states. Indeed! But at least now we know that it's possible to solve the problem. So here's a question which is actually more interesting, now that we know it's possible to solve it: can we solve the same problem without simulating how the program runs step-by-step? Or in other words, can we reduce the time complexity and/or increase the efficiency of such algorithms? That's the actual interesting question to me. I agree with the rest of your comment.

jltsiren 4y ago
> So here's a question which is actually more interesting, now that we know it's possible to solve it: can we solve the same problem without simulating how the program runs step-by-step? Despite a century of research, simulation is still pretty much the only tool we have. Simulation can also be used to rule out many hypothetical solutions using similar tricks to the proof of Rice's theorem. Assume that program A, with input X, decides whether program X with input X halts within a fixed resource bound. Assume that the resource bound is high enough that running A with an input of size |A| + C, for a reasonable constant C, uses much less resources than the bound. Then we can write a program A' that runs A with the input. If A says that the input halts (within the bound), A' enters an infinite loop. If A says that the input does not halt (within the bound), A' halts. If we run A' with input A', it halts iff A says A' does not halt (within the bound) with input A'. We can avoid the situation by allowing A to make mistakes, by allowing it to say "don't know", or by allowing it to exceed the resource bound.
- wizeman 4y ago
  > or by allowing it to exceed the resource bound. Exactly. When running A, in some cases you would necessarily need more memory to run it than the memory bound that you defined for the input program, if you want it to work for all input programs without mistakes and without saying "don't know". But that doesn't say anything about the time complexity, or does it?
  - jltsiren 4y ago
    The same argument applies to time complexity as well. A' is A plus some trivial logic, so its running time should be marginally higher. A' halts with input A' iff A says A' does not halt within the desired time bound with input A'. That's a contradiction if A is substantially faster than the time bound.
    - deleted 4y ago
      [deleted]
    - 4y ago