The laterality problem for non-erasing Turing machines on { 0 , 1 } is completely solved

Maurice Margenstern

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1997)

  • Volume: 31, Issue: 2, page 159-204
  • ISSN: 0988-3754

How to cite

top

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 31.2 (1997): 159-204. <http://eudml.org/doc/92557>.

@article{Margenstern1997,
author = {Margenstern, Maurice},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Turing machine; decidability},
language = {eng},
number = {2},
pages = {159-204},
publisher = {EDP-Sciences},
title = {The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved},
url = {http://eudml.org/doc/92557},
volume = {31},
year = {1997},
}

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
PB - EDP-Sciences
VL - 31
IS - 2
SP - 159
EP - 204
LA - eng
KW - Turing machine; decidability
UR - http://eudml.org/doc/92557
ER -

References

top
  1. 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. 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. Zbl0794.68047MR1260506
  3. 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. 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. 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. Zbl0834.68024MR1320840
  6. 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). MR1292457
  7. 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. Zbl0834.68025MR1338293
  8. 8. M. L. MINSKY, Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, N.J., 1967. Zbl0195.02402MR356580
  9. 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. Zbl0284.02017
  10. 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). Zbl0426.68025
  11. 11. Ju.V. ROGOZHIN, universal'nykh mashin T'juringa. Matematicheskie Issledovanija, 1982, 69 pp. 76-90, (Seven universal Turing machines) (in Russian). Zbl0515.03020MR711781
  12. 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). Zbl0515.03020
  13. 13. Ju.V. ROGOZHIN, About Shannon's problem for Turing machines. Comput. Sci. J. Moldova, 1993 1 3(3), pp. 108-111. 
  14. 14. Ju. V. ROGOZHIN, Small universal Turing machines, Theoretical Computer Science, 168-2, special issue on Universal Machines and Computations, 1996, pp. 215-240. Zbl0874.68106MR1422956
  15. 15. Ju. V. ROGOZHIN, A universal Turing machine with 21 states and 2 symbols, private communication, 1996. 
  16. 16. C. E. SHANNON, A universal Turing machine with two internal states., Ann. of Math. Studies, 1956, 34, pp. 157-165. MR79548
  17. 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. Zbl0016.09701
  18. 18. H. A. WANG, variant to Turing's theory of Computing machines, J. Assoc. Comput. Mach., 1957, 4, 1, pp. 63-92. 
  19. 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). Zbl0171.27302MR155748

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.