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