4 ms·

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

by 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.

by lmm 2y ago

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.