Comment by lisper | Hacker News Reader

Comment by lisper | Hacker News Reader

This is ridiculous academic click-bait. Here is a quote from Turing's 1936 paper:

"If a computing machine never writes down more than a finite number of symbols of the first kind [i.e. 0 or 1], it will be called circular. Otherwise it is said to be circle-free."

He then goes on to prove that "circularity" as he has defined it is undecidable.

So no, he never defines "halting", he just talks about whether or not a machine ever prints a finite number of 1's and 0's. Showing that these questions are equivalent is an elementary exercise.

He also proves that "there can be no machine £ which, when supplied with the S.D of an arbitrary machine AV, will determine vhether AV ever prints a given symbol (0 say)." Which, again, is trivially equivalent to the question of whether or not the machine ever enters a particular privileged state.

Saying that Turing's paper was not about the halting problem because it doesn't use the word "halt" is like saying that the EPR paper was not about entanglement because it doesn't use the word "entangled".

> So no, he never defines "halting", he just talks about whether or not a machine ever prints a finite number of 1's and 0's. Showing that these questions are equivalent is an elementary exercise.

I think it's subtler than that. Circular programs in Turing's language are those that return to some exact earlier state and thus go into an infinite loop. So circular programs by definition do not halt. But circle-free programs can either halt or not halt!

> Circular programs in Turing's language are those that return to some exact earlier state

No, they aren't. They are programs that print a finite number of "symbols of the first kind" i.e. 0s and 1s. They can print an infinite number of other symbols.

You might want to check out this branch of the discussion:

https://news.ycombinator.com/item?id=40855382

> Showing that these questions are equivalent is an elementary exercise.

Do you mean that there's a simple computable mapping f from TMs as Turing defined them to TMs which can halt such that machine m prints finitely many 0s/1s iff f(m) halts?

No. In fact, my guess is that you can prove there is no such function. But (and I confess I have not thought this all the way through so I might be wrong) while producing such a mapping would be sufficient to carry out the equivalence proof (if it were possible, which I suspect it is not) it is not necessary. All that is necessary (I think) is 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". And that seems like it should not be hard, though I concede I may have overstated my case by calling it trivial.

(You also have to prove the opposite, that a machine with a halting state can be converted into a Turing-style TM, but that really is obviously trivial.)

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

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.

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

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.

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.

That point is discussed in the paper: circle-freeness is Pi^0_2 in the arithmetic hierarchy, so there isn't a reduction to halting (Sigma^0_1) in the usual sense of a mapping between inputs. And in fact, Turing's paper does do a construction like you describe to show that yet another problem ("symbol-printing") is undecidable, and that one is much more similar to halting than circle-freeness. Again, this subtlety is discussed in the paper.

I think you were a bit quick in dismissing the OP paper based only on its title.

Yes, I think you might be right about that. FWIW, it's 4AM here and I am not firing on all cylinders. I live in the U.S. and politics is weighing heavily on my mind tonight.

I think you'd want the reverse, which is indeed elementary: if f halts then you get a circle-free TM, but if f does not halt then you get a non-circle-free TM. This can be done by

  f(); while(1) output_digit(0);

or any number of other simple constructions. This is because a circle-free TM always reaches a certain pre-defined event (output_digit), much like a halting TM. But a non-circle-free TM might forever fail to make progress, in a way that you can't necessarily tell if it's stuck or will eventually output another digit, much like a non-halting TM.

Edited to add: also Turing proved that the symbol-printing problem is undecidable, as the authors of this paper describe: will a Turing machine ever print a certain symbol? If you name the symbol in question "HALT" then this is almost identical to the halting problem, and easily reducible in either direction.

Reply on news.ycombinator.com