An Analysis of Turing's "The Word Problem in Semi-Groups with Cancellation"
William W. Boone · Annals of Mathematics · 1958
A. An exact construction for 0 It would seem worth while to supply such a construction here so as to help the reader. In part for the sake of brevity we perhaps depart in certain nonessentials from the construction intended by Turing. Let 1I be a Universal Turing Machine with infinite tape (i.e., without analogue of Post's symbol, h [3]); in fact, like the usual Universal Machine except for having both left and and right facing I.C.'s (4i and ri); for which it is recursively unsolvable to determine for an arbitrary initial C.C. (which we may assume, for elegance, does not contain s3) whether or not a C.C. is generated in which s3 occurs, and whose entries are of the form