4 ms·

Is it me, or does the section about the Goldbach conjecture have nothing to do with the halting problem, but with finite machines? As TFA points out, the progr

Is it me, or does the section about the Goldbach conjecture have nothing to do with the halting problem, but with finite machines? As TFA points out, the program to solve the Goldbach Conjecture will halt, and we know this. Because it halts, it doesn't solve the conjecture (unless it does solve it within the range of numbers allowed by the finite system memory). So it's got nothing to do with the halting conjecture - we know this program will definitely halt, because we don't have infinite memory. It also doesn't solve the conjecture, because it will halt. This seems like circular reasoning. If we had an infinite machine then we could write a program that could solve the conjecture, if we had infinite time to run it in (or it ran infinitely fast). Because we don't have any of those things, writing a program to solve the conjecture is impossible, regardless of our ability to determine if it halted or not. If we had the ability to determine if that program halted, we would still need an infinite machine to run the program, which we don't, so the ability to determine whether the program halts or not is irrelevant. We can't create such a program (because we can trivially determine that any such program will actually halt - yes it does, because it runs out of memory).

Dylan16807 2y ago
The second version that only goes up to a certain number shows nothing, but that's on purpose, to show that a basic 'finite computer' limit throws out the interesting part of the problem. The first version of the program has nothing wrong with it. If we had an infinity computer, we could run that exact program and get the answer. We don't need an infinity computer to write the program. If we had a halting tester that runs on a normal computer, we could feed it the program and then we would have the answer to the conjecture, without needing an infinity computer.
lmm 2y ago
> So it's got nothing to do with the halting conjecture - we know this program will definitely halt, because we don't have infinite memory. It also doesn't solve the conjecture, because it will halt. This seems like circular reasoning. Nothing circular there. The point is that "does this program halt on a computer of size xyz?" is a very uninteresting question (as you say, it will) whereas "does it halt on an infinite computer?" is a much more interesting question (because it's equivalent to the Goldbach conjecture). So the halting problem really is deep and interesting, in a way that the "finite halting problem" isn't.
- marcus_holmes 2y ago
  Yeah I get that, but if we're inventing magic infinite computers, why not invent magic halting algorithms? > the halting problem was solvable, then anyone with a computer could prove Goldbach's conjecture in an afternoon. This paragraph is essentially saying this - if we had magic computers then we could magic things we them, but we don't so we can't.
  - lmm 2y ago
    > Yeah I get that, but if we're inventing magic infinite computers, why not invent magic halting algorithms? Do you object to doing geometry because it involves a magic infinite plane? The point is that by studying the behaviour of this simple model we can learn useful things. > This paragraph is essentially saying this - if we had magic computers then we could magic things we them, but we don't so we can't. If you knew what a program would do on a magic computer, you could do very interesting things. The point isn't to have an actual magic computer.
  - Dylan16807 2y ago
    > This paragraph is essentially saying this - if we had magic computer Not at all. A halting algorithm very specifically wouldn't need magic computers. Heck, if you had a magic infinite computer then you wouldn't need a halting algorithm. It's the opposite of a prerequisite. A halting algorithm requires the concept of an infinite computer. No more, no less. It's like a calculus program solving some category of infinite sum. It uses the concept of infinite math, it doesn't need or want a computer that's actually capable of infinite additions. And detecting divergence is a lot like detecting halting.

Dylan16807 2y ago

The second version that only goes up to a certain number shows nothing, but that's on purpose, to show that a basic 'finite computer' limit throws out the interesting part of the problem. The first version of the program has nothing wrong with it. If we had an infinity computer, we could run that exact program and get the answer. We don't need an infinity computer to write the program. If we had a halting tester that runs on a normal computer, we could feed it the program and then we would have the answer to the conjecture, without needing an infinity computer.

lmm 2y ago

> So it's got nothing to do with the halting conjecture - we know this program will definitely halt, because we don't have infinite memory. It also doesn't solve the conjecture, because it will halt. This seems like circular reasoning. Nothing circular there. The point is that "does this program halt on a computer of size xyz?" is a very uninteresting question (as you say, it will) whereas "does it halt on an infinite computer?" is a much more interesting question (because it's equivalent to the Goldbach conjecture). So the halting problem really is deep and interesting, in a way that the "finite halting problem" isn't.

marcus_holmes 2y ago
Yeah I get that, but if we're inventing magic infinite computers, why not invent magic halting algorithms? > the halting problem was solvable, then anyone with a computer could prove Goldbach's conjecture in an afternoon. This paragraph is essentially saying this - if we had magic computers then we could magic things we them, but we don't so we can't.
- lmm 2y ago
  > Yeah I get that, but if we're inventing magic infinite computers, why not invent magic halting algorithms? Do you object to doing geometry because it involves a magic infinite plane? The point is that by studying the behaviour of this simple model we can learn useful things. > This paragraph is essentially saying this - if we had magic computers then we could magic things we them, but we don't so we can't. If you knew what a program would do on a magic computer, you could do very interesting things. The point isn't to have an actual magic computer.
- Dylan16807 2y ago
  > This paragraph is essentially saying this - if we had magic computer Not at all. A halting algorithm very specifically wouldn't need magic computers. Heck, if you had a magic infinite computer then you wouldn't need a halting algorithm. It's the opposite of a prerequisite. A halting algorithm requires the concept of an infinite computer. No more, no less. It's like a calculus program solving some category of infinite sum. It uses the concept of infinite math, it doesn't need or want a computer that's actually capable of infinite additions. And detecting divergence is a lot like detecting halting.