4 ms·

> 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

> 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]
    - wizeman 4y ago
      You are making an interesting argument but I am having a bit of difficulty in understanding it. So instead of saying: does program X with input X halt? You redefined the problem to be: does program X with input X halt within T time steps? Then you reach the conclusion: A' halts with input A' iff A says A' does not halt within the desired time bound with input A'. But OK, imagine that we define the time bound T to be 10 steps and so A can always tell you whether a program halts within 10 steps, and always gives the correct answer in 1 step. What does that tell us? > 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. So: 1. If A says (in 1 step) that X halts in the first 10 time steps, then A' enters an infinite loop. 2. If A says (in 1 step) that X doesn't halt in the first 10 time steps, then A' halts (say, in the second step). Now you run A' with A' as input and: 1. If A says (in 1 step) that A' halts in the first 10 time steps, then A' enters an infinite loop. 2. If A says (in 1 step) that A' doesn't halt in the first 10 time steps, then A' halts (say, in the second step). But here's the thing: A can only efficiently, correctly and always prove whether X halts if A is able to use more memory than X would use (otherwise we'd run into the exact same undecidability problem as with Turing machines). This implies that besides the time bound, A also needs to analyze whether X halts within a defined memory bound. So when you run A' with A', for A to work correctly then A would have to use more memory than A' would use, which is a contradiction because A' needs to use as much or more memory than A. So isn't it impossible to use A' with A' as an input if you want A to always give you a correct answer, regardless of the time complexity bound? Because the memory bound would always be exceeded. Does that actually prove that it's impossible to construct such a time-efficient A that works for all X that use less memory, or does it only prove that it's impossible to run A with A' as input correctly because the memory bound would always be exceeded?

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]
  - wizeman 4y ago
    You are making an interesting argument but I am having a bit of difficulty in understanding it. So instead of saying: does program X with input X halt? You redefined the problem to be: does program X with input X halt within T time steps? Then you reach the conclusion: A' halts with input A' iff A says A' does not halt within the desired time bound with input A'. But OK, imagine that we define the time bound T to be 10 steps and so A can always tell you whether a program halts within 10 steps, and always gives the correct answer in 1 step. What does that tell us? > 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. So: 1. If A says (in 1 step) that X halts in the first 10 time steps, then A' enters an infinite loop. 2. If A says (in 1 step) that X doesn't halt in the first 10 time steps, then A' halts (say, in the second step). Now you run A' with A' as input and: 1. If A says (in 1 step) that A' halts in the first 10 time steps, then A' enters an infinite loop. 2. If A says (in 1 step) that A' doesn't halt in the first 10 time steps, then A' halts (say, in the second step). But here's the thing: A can only efficiently, correctly and always prove whether X halts if A is able to use more memory than X would use (otherwise we'd run into the exact same undecidability problem as with Turing machines). This implies that besides the time bound, A also needs to analyze whether X halts within a defined memory bound. So when you run A' with A', for A to work correctly then A would have to use more memory than A' would use, which is a contradiction because A' needs to use as much or more memory than A. So isn't it impossible to use A' with A' as an input if you want A to always give you a correct answer, regardless of the time complexity bound? Because the memory bound would always be exceeded. Does that actually prove that it's impossible to construct such a time-efficient A that works for all X that use less memory, or does it only prove that it's impossible to run A with A' as input correctly because the memory bound would always be exceeded?