[tromp]

> to show that if a machine is non-circular, then it is possible to produce an equivalent machine by using a halting state which is entered after the machine prints its final "symbol of the first kind".

This looks rather impossible to me. Yet you claim

> And that seems like it should not be hard

Could you elaborate how to do so?

[lisper]

The key is the assumption that the machine is non-circular. So there must be a state in which it prints its last symbol (can we agree to drop the "of the first kind" qualification?). After that, it never prints another symbol, so you can just replace whatever it does after that with a halting state.

But I see the problem with this now that I've written it out. The future behavior of the machine also depends on the state of the tape so you can't "just replace" all the future behavior because you don't know which entry into the state that prints the last symbol will be the one that actually prints the last symbol. So that doesn't work.

Still, going meta, there are only two possibilities here: either the undecidability of the HP is equivalent to the undecidability of circularity (i.e. that either result follows from the other) or it isn't. If it isn't then that would be Big News, and if it is, then it's just a question of how easy or hard it is to prove this. If it's hard, then someone should get the credit for being the first, and since I've never heard anyone get the credit I conclude that it's probably easy notwithstanding that my intuition about how to do it turns out to be wrong.

[tromp]

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

[lisper]

It turns out I was not as wrong as I thought. From the opening of the paper:

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

[lisper]

Thanks.

BTW, hats off to you for the subtlety of your pedantry. You made me realize that I was wrong by asking just the right question. Socrates would be proud.