3 ms·

(appreciate the background, but fyi I'm very familiar with the theory of computation) I may have misunderstood what you meant when I replied. I agree with bas

(appreciate the background, but fyi I'm very familiar with the theory of computation) I may have misunderstood what you meant when I replied. I agree with basically everything you have written here in spirit, but I don't think "oops an infinity snuck in" is really a useful way to think about computability. There are lots of infinities that can be tamed by Turing machines, by a program that computes membership, for instance. The even numbers are a trivial example. The infinities of computation are asymptotic, not absolute - a Turing machine that solves a decision problem may use unbounded space as a function of input size, but this is not the same thing as literally using an infinite amount of space. Restricting to finite tapes is pointless from a mathematical point of view, precisely because everything becomes computable in finite time/space.

rstuart4133 2y ago
> There are lots of infinities that can be tamed by Turing machines, by a program that computes membership, for instance. To someone (which I assume covers most here) who are familiar with mid-level high school maths (calculus, infinite series) this is obvious, surely. We don't just tame infinities in maths and physics, we put them to work. You not only have to be aware of them, you have use them to get some important results. I doubt you would find someone willing to argue against this in mathematics. The same statement is true in computing. You have to be aware of unwanted infinities. I'd lay long odds there are more programmers out there who have created unwanted infinite loops than there are maths students who have unwittingly divided by 0 and got a nonsensical result. Yet at the same time, infinities lie at the heart of some important results - like the halting problem. Everyone should be aware they are both a nuisance you don't want sneaking in unnoticed, and a very valuable tool. > I agree with basically everything you have written here in spirit, but I don't think "oops an infinity snuck in" is really a useful way to think about computability. I disagree. The halting program is one specific result. It is merely the outcome of a more fundamental idea. To wit, there are infinite states (think: infinite strings of bits) no finite program can describe (or equivalently reproduce, or recognise). It's one of those rare things that is hard to get your head around when you first hear it, then becomes obvious after a bit of thought. Somewhat less obvious, to me anyway, is the result applies even if you give that finite program infinite time and infinite space. Like most fundamental ideas, it leads to other results with little effort. For example, if you view the finite program as a compressed version of the infinite space, it means some infinite spaces can not be compressed. This result is doubly interesting because it extends to finite systems, leading to linking of the seemingly disparate ideas of randomness, compression and computability. It also means if the universe has some infinity hiding inside it it's possible our finite minds can never understand it. It means you will never be able to write a finite program that proves some infinitely long programs halt. It almost certainly means there is an N above which BB(N) isn't computable, and from what we know now that N may be 6. It is why Gödel's theorem holds. Most of those things aren't near as easily deduced from the halting problem, which is why it isn't as useful understanding the effects of infinities on computability. Above I think you are saying "but, but, introducing the idea that some infinities can be described might confuse some programmers. It may lead them to think a finite program can't describe an infinite series of 1's, for example". I'm not sure how many programmers you know, because in the world I live in not a single one would be confused by that. All are perfectly capable understanding some infinities can be described (not in the least because they've probably written a few by mistake) and this new idea some infinities can't be written down.
- bubblyworld 2y ago
  I don't know why you think I'm worried about confusing programmers? Did I say that? My claim is that all of the results you are attributing to "infinity" are true for other reasons, like diagonalisation, and cannot be proven directly from the concept of infinity like you are claiming. It's a heuristic that is not helpful for actually doing the mathematics. Feel free to prove me wrong by giving me a (mathematical, not hand waving) proof of the halting theorem that only makes use of "infinity" as you are describing it. You won't be able to do it, because it's not the crux of the halting problem. It holds for infinite programs too, because diagonalization arguments don't care how big your set is. Anyway, I don't really have the energy for this. I appreciate the time and discussion, for which I thank you. But as someone who studied maths at a PhD level and now programs for a living, I'm not getting much out of these ideas. Perhaps we can just agree to disagree for now.

rstuart4133 2y ago

> There are lots of infinities that can be tamed by Turing machines, by a program that computes membership, for instance. To someone (which I assume covers most here) who are familiar with mid-level high school maths (calculus, infinite series) this is obvious, surely. We don't just tame infinities in maths and physics, we put them to work. You not only have to be aware of them, you have use them to get some important results. I doubt you would find someone willing to argue against this in mathematics. The same statement is true in computing. You have to be aware of unwanted infinities. I'd lay long odds there are more programmers out there who have created unwanted infinite loops than there are maths students who have unwittingly divided by 0 and got a nonsensical result. Yet at the same time, infinities lie at the heart of some important results - like the halting problem. Everyone should be aware they are both a nuisance you don't want sneaking in unnoticed, and a very valuable tool. > I agree with basically everything you have written here in spirit, but I don't think "oops an infinity snuck in" is really a useful way to think about computability. I disagree. The halting program is one specific result. It is merely the outcome of a more fundamental idea. To wit, there are infinite states (think: infinite strings of bits) no finite program can describe (or equivalently reproduce, or recognise). It's one of those rare things that is hard to get your head around when you first hear it, then becomes obvious after a bit of thought. Somewhat less obvious, to me anyway, is the result applies even if you give that finite program infinite time and infinite space. Like most fundamental ideas, it leads to other results with little effort. For example, if you view the finite program as a compressed version of the infinite space, it means some infinite spaces can not be compressed. This result is doubly interesting because it extends to finite systems, leading to linking of the seemingly disparate ideas of randomness, compression and computability. It also means if the universe has some infinity hiding inside it it's possible our finite minds can never understand it. It means you will never be able to write a finite program that proves some infinitely long programs halt. It almost certainly means there is an N above which BB(N) isn't computable, and from what we know now that N may be 6. It is why Gödel's theorem holds. Most of those things aren't near as easily deduced from the halting problem, which is why it isn't as useful understanding the effects of infinities on computability. Above I think you are saying "but, but, introducing the idea that some infinities can be described might confuse some programmers. It may lead them to think a finite program can't describe an infinite series of 1's, for example". I'm not sure how many programmers you know, because in the world I live in not a single one would be confused by that. All are perfectly capable understanding some infinities can be described (not in the least because they've probably written a few by mistake) and this new idea some infinities can't be written down.

bubblyworld 2y ago
I don't know why you think I'm worried about confusing programmers? Did I say that? My claim is that all of the results you are attributing to "infinity" are true for other reasons, like diagonalisation, and cannot be proven directly from the concept of infinity like you are claiming. It's a heuristic that is not helpful for actually doing the mathematics. Feel free to prove me wrong by giving me a (mathematical, not hand waving) proof of the halting theorem that only makes use of "infinity" as you are describing it. You won't be able to do it, because it's not the crux of the halting problem. It holds for infinite programs too, because diagonalization arguments don't care how big your set is. Anyway, I don't really have the energy for this. I appreciate the time and discussion, for which I thank you. But as someone who studied maths at a PhD level and now programs for a living, I'm not getting much out of these ideas. Perhaps we can just agree to disagree for now.