2 UNIVERSAL TURING-MACHINES WITH AT MOST 2 LEFT INSTRUCTIONS

Authors
MARGENSTERN M PAVLOTSKAIA L
Citation
M. Margenstern et L. Pavlotskaia, 2 UNIVERSAL TURING-MACHINES WITH AT MOST 2 LEFT INSTRUCTIONS, Comptes rendus de l'Academie des sciences. Serie 1, Mathematique, 320(11), 1995, pp. 1395-1400
Citations number
7
Categorie Soggetti
Mathematics, General",Mathematics
Journal title
Comptes rendus de l'Academie des sciences. Serie 1, Mathematique → ACNP
ISSN journal
07644442
Volume
320
Issue
11
Year of publication
1995
Pages
1395 - 1400
Database
ISI
SICI code
0764-4442(1995)320:11<1395:2UTWAM>2.0.ZU;2-T
Abstract
A universal Turing machine is constructed on alphabet {0, 1}, the prog ram of which contains precisely two instructions involving left moves. Another one is constructed on {0, 1, 2} with a single instruction inv olving a left move.