When I read Turing's paper some years ago, this really confused me. The best sense I could make was that "circle-free" means "halts". But in popular explanations, writers often equate "halts" with "gives a result" and "doesn't halt" with "has a bug", i.e. an infinite loop. And Turing seems to connote just the opposite. The point is to print a real number, so if the program stops printing digits, something went wrong. (I guess many numbers would end in 0s forever.) From today's paper:
> a program is circular, when it produces only finitely many digits of the output digit sequence, and circle-free, when it has succeeded in giving us an infinite digit sequence for the output real number.
But I could never really believe my interpretation. It was just the best I could come up with, as an amateur reading the paper alone for fun. Later I read Petzold's book, and I'm not sure that really solved the trouble for me either.
I've only read a few pages so far, but I'm gathering it's not as simple as I wanted: "circle-free" is not merely equivalent to "halts" after all. I'm looking forward to seeing their more nuanced take.
EDIT: Btw, this reminds me of the best riddle I've ever invented myself. Q: What do you call a fully autonomous self-driving car that can operate with as much understanding as a person? A: N Gheavat Znpuvar. (I didn't say it was a good riddle.)
I don't think the examples are meant as actual real world things, but rather abstractions to help reason about the problem.
The most important thing about the halting problem, is that Turing gave an example of a computational problem that is unsolvable, thereby proofing that from all possible computational problems, some of them are be unsolvable.
When I read Turing's paper some years ago, this really confused me. The best sense I could make was that "circle-free" means "halts". But in popular explanations, writers often equate "halts" with "gives a result" and "doesn't halt" with "has a bug", i.e. an infinite loop. And Turing seems to connote just the opposite. The point is to print a real number, so if the program stops printing digits, something went wrong. (I guess many numbers would end in 0s forever.) From today's paper:
> a program is circular, when it produces only finitely many digits of the output digit sequence, and circle-free, when it has succeeded in giving us an infinite digit sequence for the output real number.
But I could never really believe my interpretation. It was just the best I could come up with, as an amateur reading the paper alone for fun. Later I read Petzold's book, and I'm not sure that really solved the trouble for me either.
I've only read a few pages so far, but I'm gathering it's not as simple as I wanted: "circle-free" is not merely equivalent to "halts" after all. I'm looking forward to seeing their more nuanced take.
EDIT: Btw, this reminds me of the best riddle I've ever invented myself. Q: What do you call a fully autonomous self-driving car that can operate with as much understanding as a person? A: N Gheavat Znpuvar. (I didn't say it was a good riddle.)