@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},
pages = {159--204},
year = {1997},
publisher = {EDP Sciences},
volume = {31},
number = {2},
mrnumber = {1462585},
zbl = {0878.68063},
language = {en},
url = {https://www.numdam.org/item/ITA_1997__31_2_159_0/}
}
TY - JOUR AU - Margenstern, Maurice TI - The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 1997 SP - 159 EP - 204 VL - 31 IS - 2 PB - EDP Sciences UR - https://www.numdam.org/item/ITA_1997__31_2_159_0/ LA - en ID - ITA_1997__31_2_159_0 ER -
%0 Journal Article %A Margenstern, Maurice %T The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1997 %P 159-204 %V 31 %N 2 %I EDP Sciences %U https://www.numdam.org/item/ITA_1997__31_2_159_0/ %G en %F 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) no. 2, pp. 159-204. https://www.numdam.org/item/ITA_1997__31_2_159_0/
1. , 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. , 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. | Zbl | MR
3. , 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. , 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. , Une machine de Turing universelle non-effaçante à exactement trois instructions gauches. C.R.A.S., Paris, 1995, 320, I, pp. 101-106. | Zbl | MR
6. , 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
7. and , Deux machines de Turing universelles à au plus deux instructions gauches. C.R.A.S., Paris, 1995, 320, I, pp. 1395-1400. | Zbl | MR
8. , Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, N.J., 1967. | Zbl | MR
9. , 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
10. , 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
11. , universal'nykh mashin T'juringa. Matematicheskie Issledovanija, 1982, 69 pp. 76-90, (Seven universal Turing machines) (in Russian). | Zbl | MR
12. , 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
13. , About Shannon's problem for Turing machines. Comput. Sci. J. Moldova, 1993 1 3(3), pp. 108-111.
14. , Small universal Turing machines, Theoretical Computer Science, 168-2, special issue on Universal Machines and Computations, 1996, pp. 215-240. | Zbl | MR
15. , A universal Turing machine with 21 states and 2 symbols, private communication, 1996.
16. , A universal Turing machine with two internal states., Ann. of Math. Studies, 1956, 34, pp. 157-165. | MR
17. , On computable real numbers, with an application to the Entscheidungsproblem., Proc. Lond. Math. Soc., 1936, ser. 2, 42, pp. 230-265. | Zbl
18. , variant to Turing's theory of Computing machines, J. Assoc. Comput. Mach., 1957, 4, 1, pp. 63-92.
19. , Zamechanie ob odnoj teoreme Khao Vana, Algebra i Logika, 1963, 2, 1, pp. 33-35, (Remark on a theorem of Hao Wang) (in Russian). | Zbl | MR






