10 ms·

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-gam

by 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
        It seems that your assumption is that there could be an efficient algorithm that can analyze any program with a bounded number of states and check that it halts. However, it is simple to show that this is at least as hard as NP complete. For instance, you can map the Hamiltonian cycle problem to a halting problem over programs that do an infinite walk on graphs without a Hamiltonian cycle and those that stop whenever they complete a walk along a Ham cycle. At this time P vs NP is still wide open and, in general, statements in complexity theory are usually dependent on some unproven hypothesis so I still don't understand what is your point exactly.
        wizeman 4y ago
        Yes, exactly, you seem to be understanding my point: there could be an efficient algorithm that can analyze any program with a bounded number of states and check that it halts. Among other things, because the P vs NP issue is still wide open, yes. I'd just like to add three more minor points: 1. Many people believe the above to be false, because they believe that the problem is undecidable also for programs with a bounded number of states. 2. That I would like if more people focused on finding such an efficient algorithm. 3. And that I think that even some people who believe that the problem is decidable think that it's impossible to have an efficient algorithm because of the Halting problem and Rice's theorem, which formally speaking, neither of them say anything about whether such efficient algorithms exist or not.
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.

by swid 4y ago

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
        It seems that your assumption is that there could be an efficient algorithm that can analyze any program with a bounded number of states and check that it halts. However, it is simple to show that this is at least as hard as NP complete. For instance, you can map the Hamiltonian cycle problem to a halting problem over programs that do an infinite walk on graphs without a Hamiltonian cycle and those that stop whenever they complete a walk along a Ham cycle. At this time P vs NP is still wide open and, in general, statements in complexity theory are usually dependent on some unproven hypothesis so I still don't understand what is your point exactly.
        wizeman 4y ago
        Yes, exactly, you seem to be understanding my point: there could be an efficient algorithm that can analyze any program with a bounded number of states and check that it halts. Among other things, because the P vs NP issue is still wide open, yes. I'd just like to add three more minor points: 1. Many people believe the above to be false, because they believe that the problem is undecidable also for programs with a bounded number of states. 2. That I would like if more people focused on finding such an efficient algorithm. 3. And that I think that even some people who believe that the problem is decidable think that it's impossible to have an efficient algorithm because of the Halting problem and Rice's theorem, which formally speaking, neither of them say anything about whether such efficient algorithms exist or not.

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.