5 ms·

> EXPTIME complete Isn't EXPTIME completeness only defined for Turing machines? Which again, just proves all of my points. For all we know, if you've reached

> EXPTIME complete Isn't EXPTIME completeness only defined for Turing machines? Which again, just proves all of my points. For all we know, if you've reached the conclusion that an algorithm is EXPTIME-complete, this conclusion could be just as false as the Halting problem and Rice's theorem are for real-world computers.

danbruc 4y ago
I think you are misunderstanding the point. Deciding whether a finite Turing machine - a.k.a. a real computer - halts is EXPTIME-complete, i.e. it would already take forever to decide even if you had access to a real Turing machine but you actually only have access to less powerful real computers.
- wizeman 4y ago
  > Deciding whether a finite Turing machine - a.k.a. a real computer - halts is EXPTIME-complete Can you point me somewhere that proves this exact statement you're making? Or at least, explains why it is true. I'm interested in reading about it. I mean, assuming you are correct (and I have no reason to believe you aren't) it still doesn't guarantee that the problem is intractable (as EXPTIME-complete algorithms can still run very quickly in practice), but yes, I think it would suggest that it is intractable (for real-word applications).
  - swid 4y ago
    Here is a good article you might be able to understand that pretty much provides an answer to your question. https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/ https://www.quantamagazine.org/the-busy-beaver-game-illumina...
    - wizeman 4y ago
      No, it does not provide an answer. What does that have to do with analyzing a finite-state machine in EXPTIME-complete time? The busy beaver problem, again, assumes it is running on a Turing machine with infinite memory. Don't confuse a program defined using a finite number of states with a machine that can only have a finite number of states. It's just another example of the points I'm making about how a theoretical mathematical problem is an interesting curiosity and might even be an interesting problem to solve but it does not necessarily apply to the real world. And how everyone seems to think that this mathematical problem applies to programs running in real-world computers. Someone else mentioned the busy beaver problem and I've given a more complete answer there: https://news.ycombinator.com/item?id=33744326 https://news.ycombinator.com/item?id=33744326
      - swid 4y ago
        Both people are me. I think there is an answer in that article, but I can’t unpack it for you. It explains why what you are asking about is so impractical, and can point you to topics to gain a better understanding. In the real world, a program will either halt, loop, or crash, but this doesn’t help us if a 6 instruction program can take longer than the age of the universe to run while still terminating. No matter how fast you go through its states. 64mb leaves a lot of room for unique states without a cycle.
        wizeman 4y ago
        > In the real world, a program will either halt, loop, or crash, but this doesn’t help us if a 6 instruction program can take longer than the age of the universe to run while still terminating. No matter how fast you go through its states. 64mb leaves a lot of room for unique states without a cycle. Why do you assume that you have to go through all the states of the program to determine whether it will run into a cycle?
        swid 4y ago
        The foundation of cryptography is that there exists algorithms in which the only way the beat them is to iterate over a computationally infeasible number of states to be able to decrypt something. To not believe my assumption would require you to believe that such algorithms do not exist.
        wizeman 4y ago
        Agreed. Since the assumption has not been proven, this is why the foundation of cryptography is still on a bit of a shaky ground, as none of those algorithms are proven to be unbeatable (the one-time pad being the exception, although it's not very useful in practice). It's probably also why weaknesses in cryptographic algorithms are still being discovered every now and then, unfortunately.
        dellamonica 4y ago
    - danbruc 4y ago
      Simulating it step by step is the upper bound establishing that is in EXPTIME, the second part, the reduction to the bounded halting problem, is what establishes EXPTIME-completeness. And the time hierarchy theorem finally establishes that EXPTIME is not equal to P.
  - danbruc 4y ago
    Let's see, I just looked that up before. Let us for simplicity assume that in every step only one bit of state gets accessed, this will only be wrong by some constant factor. With that running a Turing machine for at most n steps will ensure that it does not use more than n bit of memory, therefore solving the halting problem for a machine with n bit is at least as hard as answering the question whether a Turing machine halts within n steps. This is in EXPTIME [1][2] given that the input n is encoded in log(n) bit. So that seems a lot less worse then at first sight, but on the other hand this uses a terrible bound for the number of steps. [1] https://cs.stackexchange.com/questions/112684/halting-problem-in-exp-complete https://cs.stackexchange.com/questions/112684/halting-proble... [2] https://en.wikipedia.org/wiki/EXPTIME https://en.wikipedia.org/wiki/EXPTIME
    - wizeman 4y ago
      > Let us for simplicity assume that in every step only one bit of state gets accessed, this will only be wrong by some constant factor. With that running a Turing machine for at most n steps will ensure that it does not use more than n bit of memory, therefore solving the halting problem for a machine with n bit is at least as hard as answering the question whether a Turing machine halts within n steps. I'm following so far. > This is in EXPTIME [1][2] given that the input n is encoded in log(n) bit. Perhaps I'm reading this incorrectly, but these proofs seem to assume that you're simulating the machine running step by step? Is it proven that the only way to solve the bounded Halting problem is by running the program step by step? If not, it seems that this is only proving a high complexity bound (i.e. that the problem is not more complex that EXPTIME), not a low bound (i.e. that the problem can be solved in less complexity than EXPTIME).
      - danbruc 4y ago
        Replied to the wrong comment. https://news.ycombinator.com/item?id=33749430 https://news.ycombinator.com/item?id=33749430
        wizeman 4y ago
        Interesting, thank you! I am having a bit of difficulty understanding the exact implications in this context, but I will give it some thought.
- evouga 4y ago
  There’s a rather big gap between “exponential time” and “forever”! I routinely solve instances of problems in EXPTIME to solve practical problems with no difficulty…
  - danbruc 4y ago
    That misses the point. The discussion is about whether limiting a Turing machine to a finite but non-trivial tape length makes the halting problem tractable. That you can solve the halting problem in some cases - for example for while (true) { } or return 42; - has no bearing on this. The question is whether you can solve the hardest instances satisfying the constraints, not whether you can solve some easy instances.

danbruc 4y ago

I think you are misunderstanding the point. Deciding whether a finite Turing machine - a.k.a. a real computer - halts is EXPTIME-complete, i.e. it would already take forever to decide even if you had access to a real Turing machine but you actually only have access to less powerful real computers.

wizeman 4y ago
> Deciding whether a finite Turing machine - a.k.a. a real computer - halts is EXPTIME-complete Can you point me somewhere that proves this exact statement you're making? Or at least, explains why it is true. I'm interested in reading about it. I mean, assuming you are correct (and I have no reason to believe you aren't) it still doesn't guarantee that the problem is intractable (as EXPTIME-complete algorithms can still run very quickly in practice), but yes, I think it would suggest that it is intractable (for real-word applications).
- swid 4y ago
  Here is a good article you might be able to understand that pretty much provides an answer to your question. https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/ https://www.quantamagazine.org/the-busy-beaver-game-illumina...
  - wizeman 4y ago
    No, it does not provide an answer. What does that have to do with analyzing a finite-state machine in EXPTIME-complete time? The busy beaver problem, again, assumes it is running on a Turing machine with infinite memory. Don't confuse a program defined using a finite number of states with a machine that can only have a finite number of states. It's just another example of the points I'm making about how a theoretical mathematical problem is an interesting curiosity and might even be an interesting problem to solve but it does not necessarily apply to the real world. And how everyone seems to think that this mathematical problem applies to programs running in real-world computers. Someone else mentioned the busy beaver problem and I've given a more complete answer there: https://news.ycombinator.com/item?id=33744326 https://news.ycombinator.com/item?id=33744326
    - swid 4y ago
      Both people are me. I think there is an answer in that article, but I can’t unpack it for you. It explains why what you are asking about is so impractical, and can point you to topics to gain a better understanding. In the real world, a program will either halt, loop, or crash, but this doesn’t help us if a 6 instruction program can take longer than the age of the universe to run while still terminating. No matter how fast you go through its states. 64mb leaves a lot of room for unique states without a cycle.
      - wizeman 4y ago
        > In the real world, a program will either halt, loop, or crash, but this doesn’t help us if a 6 instruction program can take longer than the age of the universe to run while still terminating. No matter how fast you go through its states. 64mb leaves a lot of room for unique states without a cycle. Why do you assume that you have to go through all the states of the program to determine whether it will run into a cycle?
        swid 4y ago
        The foundation of cryptography is that there exists algorithms in which the only way the beat them is to iterate over a computationally infeasible number of states to be able to decrypt something. To not believe my assumption would require you to believe that such algorithms do not exist.
        wizeman 4y ago
        Agreed. Since the assumption has not been proven, this is why the foundation of cryptography is still on a bit of a shaky ground, as none of those algorithms are proven to be unbeatable (the one-time pad being the exception, although it's not very useful in practice). It's probably also why weaknesses in cryptographic algorithms are still being discovered every now and then, unfortunately.
        dellamonica 4y ago
  - danbruc 4y ago
    Simulating it step by step is the upper bound establishing that is in EXPTIME, the second part, the reduction to the bounded halting problem, is what establishes EXPTIME-completeness. And the time hierarchy theorem finally establishes that EXPTIME is not equal to P.
- danbruc 4y ago
  Let's see, I just looked that up before. Let us for simplicity assume that in every step only one bit of state gets accessed, this will only be wrong by some constant factor. With that running a Turing machine for at most n steps will ensure that it does not use more than n bit of memory, therefore solving the halting problem for a machine with n bit is at least as hard as answering the question whether a Turing machine halts within n steps. This is in EXPTIME [1][2] given that the input n is encoded in log(n) bit. So that seems a lot less worse then at first sight, but on the other hand this uses a terrible bound for the number of steps. [1] https://cs.stackexchange.com/questions/112684/halting-problem-in-exp-complete https://cs.stackexchange.com/questions/112684/halting-proble... [2] https://en.wikipedia.org/wiki/EXPTIME https://en.wikipedia.org/wiki/EXPTIME
  - wizeman 4y ago
    > Let us for simplicity assume that in every step only one bit of state gets accessed, this will only be wrong by some constant factor. With that running a Turing machine for at most n steps will ensure that it does not use more than n bit of memory, therefore solving the halting problem for a machine with n bit is at least as hard as answering the question whether a Turing machine halts within n steps. I'm following so far. > This is in EXPTIME [1][2] given that the input n is encoded in log(n) bit. Perhaps I'm reading this incorrectly, but these proofs seem to assume that you're simulating the machine running step by step? Is it proven that the only way to solve the bounded Halting problem is by running the program step by step? If not, it seems that this is only proving a high complexity bound (i.e. that the problem is not more complex that EXPTIME), not a low bound (i.e. that the problem can be solved in less complexity than EXPTIME).
    - danbruc 4y ago
      Replied to the wrong comment. https://news.ycombinator.com/item?id=33749430 https://news.ycombinator.com/item?id=33749430
      - wizeman 4y ago
        Interesting, thank you! I am having a bit of difficulty understanding the exact implications in this context, but I will give it some thought.
evouga 4y ago
There’s a rather big gap between “exponential time” and “forever”! I routinely solve instances of problems in EXPTIME to solve practical problems with no difficulty…
- danbruc 4y ago
  That misses the point. The discussion is about whether limiting a Turing machine to a finite but non-trivial tape length makes the halting problem tractable. That you can solve the halting problem in some cases - for example for while (true) { } or return 42; - has no bearing on this. The question is whether you can solve the hardest instances satisfying the constraints, not whether you can solve some easy instances.