The laterality problem for non-erasing Turing machines on {0,1} is completely solved
Margenstern, Maurice
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997), p. 159-204 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1997-01-01
@article{ITA_1997__31_2_159_0,
     author = {Margenstern, Maurice},
     title = {The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {31},
     year = {1997},
     pages = {159-204},
     mrnumber = {1462585},
     zbl = {0878.68063},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1997__31_2_159_0}
}

Margenstern, Maurice. The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997) pp. 159-204. http://gdmltest.u-ga.fr/item/ITA_1997__31_2_159_0/

1. M. Margenstern, Sur la frontière entre machines de Turing à arrêt décidable et machines de Turing universelles. Rapport de recherche LITP N° 92.83, (Institut Blaise Pascal), 1992.

2. M. Margenstern, Turing machines: on the frontier between a decidable halting problem and universality. Lecture Notes in Computer Science, 710, pp. 375-385, in Proceedings of FCT'93, 1993. | MR 1260506 | Zbl 0794.68047

3. M. Margenstern, Décidabilité du problème de l'arrêt pour les machines de Turing non-effaçante sur {0,1} et à deux instructions gauches. Rapport de recherche LITP N° 94.03 (Institut Blaise Pascal), 1994.

4. M. Margenstern, Une machine de Turing universelle sur {0,1}, non-effaçante et à trois instructions gauches. Rapport de recherche LITP N° 94.08 (Institut Blaise Pascal), 1994.

5. M. Margenstern, Une machine de Turing universelle non-effaçante à exactement trois instructions gauches. C.R.A.S., Paris, 1995, 320, I, pp. 101-106. | MR 1320840 | Zbl 0834.68024

6. M. Margenstern, Non-erasing Turing machines: a new frontier between a decidable halting problem and universality. Lecture Notes in Computer Science, 1995, 911, pp. 386-397, in Proceedings of LATIN'95). | MR 1292457

7. M. Margenstern and L. Pavlotskaya, Deux machines de Turing universelles à au plus deux instructions gauches. C.R.A.S., Paris, 1995, 320, I, pp. 1395-1400. | MR 1338293 | Zbl 0834.68025

8. M. L. Minsky, Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, N.J., 1967. | MR 356580 | Zbl 0195.02402

9. L. Pavlotskaya, Razreshimost' problemy ostanovki dlja nekotorykh klassov mashin T'juringa. Matematicheskie Zametki, Ijun' 1973, 13, (6), pp. 899-909, pp. 899-909. (transl. Solvability of the halting problem for certain classes of Turing machines, Notes of the Acad. Sci. USSR, Nov. 1973, 13, (6), pp. 537-541. | Zbl 0284.02017

10. L. Pavlotskaya, Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T'juring, Avtomaty i mashiny, 1978, pp. 91-118 (Sufficient conditions for halting problem decidability of Turing machines) (in Russian). | Zbl 0426.68025

11. Ju.V. Rogozhin, universal'nykh mashin T'juringa. Matematicheskie Issledovanija, 1982, 69 pp. 76-90, (Seven universal Turing machines) (in Russian). | MR 711781 | Zbl 0515.03020

12. Ju.V. Rogozhin, Universal'naja mashina T'juringa s 10 sostojanijami i 3 simvolami. Matematicheskie Issledovanija, 1992, 69, pp. 76-90, (A universal Turing machine with 10 states and 3 symbols) (in Russian). | Zbl 0515.03020

13. Ju.V. Rogozhin, About Shannon's problem for Turing machines. Comput. Sci. J. Moldova, 1993 1 3(3), pp. 108-111.

14. Ju. V. Rogozhin, Small universal Turing machines, Theoretical Computer Science, 168-2, special issue on Universal Machines and Computations, 1996, pp. 215-240. | MR 1422956 | Zbl 0874.68106

15. Ju. V. Rogozhin, A universal Turing machine with 21 states and 2 symbols, private communication, 1996.

16. C. E. Shannon, A universal Turing machine with two internal states., Ann. of Math. Studies, 1956, 34, pp. 157-165. | MR 79548

17. A. M. Turing, On computable real numbers, with an application to the Entscheidungsproblem., Proc. Lond. Math. Soc., 1936, ser. 2, 42, pp. 230-265. | Zbl 0016.09701

18. H. A. Wang, variant to Turing's theory of Computing machines, J. Assoc. Comput. Mach., 1957, 4, 1, pp. 63-92.

19. G. P. Zykin, Zamechanie ob odnoj teoreme Khao Vana, Algebra i Logika, 1963, 2, 1, pp. 33-35, (Remark on a theorem of Hao Wang) (in Russian). | MR 155748 | Zbl 0171.27302