Theoretical Turing machines are very simple, but have infinite resources, and are thus a bad way of determining the difficulty of things.
If you can’t do it with a Turing machine, maybe you can’t do it. This sort of hedges against ‘does someone come up with a better algorithm’, or a more efficient data structure, so things don’t get broken when something we thought was impossible is accomplished.
Other approaches include working out a minimum amount of computation, then looking at:
Practical costs (today)*
Minimum amount of energy used in theory, per physics laws re: deleting information
(Both might get thrown out of whack by quantum computers, if they pan out. Also, reversible computing might lower theoretical and practical costs.)
*This one can be affected by ‘if someone buys hardware specifically for doing this once, they can reuse it’ , if there’s not enough padding.
Yes, I suppose I left out that you can determine that something can’t be computed if you couldn’t do it with a Turing machine. Proofs of impossibility are actually somewhat important.
Practical costs today are a shifting sand, but worthwhile for difficult and important tasks, while being useless on a number of other ones due to the difficulty of determining them. What algorithm, and what should be the reference computer? (Or reference computer building / buying process. It would be silly to include a massive R&D program, but what about a small one that doesn’t take very long to make a component that vastly improves results?)
Reversible computing is a huge question mark, but so are the lower bounds of minimum energy used to delete information. [I think the theories haven’t really been tested in that area, because we have no idea how to, and are many orders of magnitude away.] On a side note, I expect based purely on my own intuition that reversible computing will actually end up taking more energy in all practical cases than the minimum reachable efficiency of nonreversible.
Quantum computing does change the mark quite a bit cost on very specific algorithms if quantum computers actually manage to scale to large enough sizes for them, but that is still many orders of magnitude for most problems they are likely superior for. Nonetheless, I think that an algorithm that is improved sufficiently by a quantum computer should be considered using a quantum version as soon as we have good number for it.
If you can’t do it with a Turing machine, maybe you can’t do it. This sort of hedges against ‘does someone come up with a better algorithm’, or a more efficient data structure, so things don’t get broken when something we thought was impossible is accomplished.
Other approaches include working out a minimum amount of computation, then looking at:
Practical costs (today)*
Minimum amount of energy used in theory, per physics laws re: deleting information
(Both might get thrown out of whack by quantum computers, if they pan out. Also, reversible computing might lower theoretical and practical costs.)
*This one can be affected by ‘if someone buys hardware specifically for doing this once, they can reuse it’ , if there’s not enough padding.
Yes, I suppose I left out that you can determine that something can’t be computed if you couldn’t do it with a Turing machine. Proofs of impossibility are actually somewhat important.
Practical costs today are a shifting sand, but worthwhile for difficult and important tasks, while being useless on a number of other ones due to the difficulty of determining them. What algorithm, and what should be the reference computer? (Or reference computer building / buying process. It would be silly to include a massive R&D program, but what about a small one that doesn’t take very long to make a component that vastly improves results?)
Reversible computing is a huge question mark, but so are the lower bounds of minimum energy used to delete information. [I think the theories haven’t really been tested in that area, because we have no idea how to, and are many orders of magnitude away.] On a side note, I expect based purely on my own intuition that reversible computing will actually end up taking more energy in all practical cases than the minimum reachable efficiency of nonreversible.
Quantum computing does change the mark quite a bit cost on very specific algorithms if quantum computers actually manage to scale to large enough sizes for them, but that is still many orders of magnitude for most problems they are likely superior for. Nonetheless, I think that an algorithm that is improved sufficiently by a quantum computer should be considered using a quantum version as soon as we have good number for it.