Translation of Lecerf '63

In 1963, Yves Lecerf demonstrated formally for the first time that reversible Turing machines can simulate arbitrary Turing machines, and used this fact to show the undecidability of a problem in the theory of monoids. Unfortunately, he wrote his paper in French. (What a maroon!) With the help of the AltaVista Translation Service, I have translated this paper into English.

WARNING: I didn't get permission from anyone from anyone before typing in the paper or putting it on the web, and so this whole effort probably represents a violation of some international copyright law or another. However, I figure that probably nobody who really cares will notice, and anyway it's probably easier to obtain forgiveness than permission. In any case, the following is provided for personal educational purposes ONLY. So if you want to get rich off the theory of monoids, go somewhere else.

WARNING: The quality of the machine translation was poor, and in a number of places I had to guess as to the precise meaning of the text. In a few instances I was not able to tell for certain whether the meaning that I guessed was consistent with what the author had in mind. For the most part though, I was able to understand the content of the document, and I believe that the majority of the English is, at least, consistent with the intended meaning of the mathematics.

Anyway, any native French speakers and/or experts on group theory who would like to suggest corrections to the translation, please feel free to email me.


Michael Frank
Last modified: Mon Jun 21 14:34:29 EDT