And even more problematic, some of the algorithms will run forever without producing output—and we can’t prove they will never stop running.
Maybe it is just my reading, but these 2 sentences seem to contradict each other. You say the algorithms “will run forever” but then you say that you can’t prove that they will never stop running forever. Doesn’t “never stop running forever” equal “will run forever”? If you don’t know that they will never stop running forever, how can you say that they will run forever?
Some algorithms run forever, some do not, and we do not have any way to prove that an algorithm is in the first set and not the latter, that was my interpretation at least.
You can prove that some algorithms run forever. Similarly, you can prove that some algorithms halt. What you can’t do is come up with a procedure that will determine whether an arbitrary algorithm you feed it halts or not.
Maybe it is just my reading, but these 2 sentences seem to contradict each other. You say the algorithms “will run forever” but then you say that you can’t prove that they will never stop running forever. Doesn’t “never stop running forever” equal “will run forever”? If you don’t know that they will never stop running forever, how can you say that they will run forever?
Some algorithms run forever, some do not, and we do not have any way to prove that an algorithm is in the first set and not the latter, that was my interpretation at least.
How do you know some algorithms run forever if you have no way of proving that an algorithm is in the set “runs forever” or not?
You can prove that some algorithms run forever. Similarly, you can prove that some algorithms halt. What you can’t do is come up with a procedure that will determine whether an arbitrary algorithm you feed it halts or not.