|
|
|
|
|
|
by tromp
721 days ago
|
|
|
Chaitin has pointed out an important difference between such questions [1] : > In our approach to incompleteness, we shall ask whether or not
a program produces an infinite amount of output rather than asking
whether it produces any; this is equivalent to asking whether or not
a diophantine equation has infinitely many solutions instead of asking
whether or not it is solvable.
If one asks whether or not a diophantine equation has a solution
for N different values of a parameter, the N different answers to this
question are not independent; in fact, they are only log2 N bits of information. But if one asks whether or not there are infinitely many
solutions for N different values of a parameter, then there are indeed
cases in which the N different answers to these questions are independent mathematical facts, so that knowing one answer is no help in
knowing any of the others [1] https://theswissbay.ch/pdf/Gentoomen%20Library/Information%2... |
|
|
"...the term halting problem, the modern formulation of the problem, as well as the common self-referential proof of its undecidability, are all, strictly speaking, absent from Turing’s work. However, Turing does introduce the concept of an undecidable decision problem, proving that what he calls the circle-free problem is undecidable and subsequently also that what we call the symbol-printing problem, to decide if a given program will ever print a given symbol, is undecidable. This latter problem is easily seen to be computably equivalent to the halting problem and can arguably serve in diverse contexts and applications in place of the halting problem—they are easily translated to one another."
So I was basically correct, just wrong about a detail: it is the symbol-printing problem that is easily translated to the halting problem, not the circle-free problem. So I am going back to standing by my initial assessment: saying that Turing's paper was not about the halting problem because it doesn't actually use that exact phrase is like saying that the EPR paper was not about entanglement because it doesn't use that exact word.