@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}, publisher = {EDP-Sciences}, volume = {31}, number = {2}, year = {1997}, mrnumber = {1462585}, zbl = {0878.68063}, language = {en}, url = {http://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 - http://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 http://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. http://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. | MR | Zbl
,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. | MR | Zbl
,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. Deux machines de Turing universelles à au plus deux instructions gauches. C.R.A.S., Paris, 1995, 320, I, pp. 1395-1400. | MR | Zbl
and ,8. Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, N.J., 1967. | MR | Zbl
,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). | MR | Zbl
,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. | MR | Zbl
,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). | MR | Zbl
,