{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T13:18:28Z","timestamp":1675257508716},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2003,4]]},"abstract":"<jats:p> In this paper, a new computation system is defined by coupling a finite automaton with a deterministic Turing machine with one head and one tape that is infinite in one direction only. In a first part of the paper, it is shown that there is a Turing machine with five instructions for which it is possible to devise a finite automaton such that the resulting computation is able to simulate any Turing machine. In a second part of the paper it is shown that if the Turing machine has at most four instructions, whatever the finite automaton is, the halting of the resulting computation is always decidable. <\/jats:p>","DOI":"10.1142\/s0218196703001262","type":"journal-article","created":{"date-parts":[[2003,4,17]],"date-time":"2003-04-17T06:15:25Z","timestamp":1050560125000},"page":"133-202","source":"Crossref","is-referenced-by-count":11,"title":["ON THE OPTIMAL NUMBER OF INSTRUCTIONS FOR UNIVERSAL TURING MACHINES CONNECTED WITH A FINITE AUTOMATON"],"prefix":"10.1142","volume":"13","author":[{"given":"MAURICE","family":"MARGENSTERN","sequence":"first","affiliation":[{"name":"LITA, EA 3097, UFR MIM,  Universit\u00e9 de Metz, Ile du Saulcy, 57045 Metz Cedex, France"}]},{"given":"LIOUDMILA","family":"PAVLOTSKA\u00cfA","sequence":"additional","affiliation":[{"name":"Moscow Power Engineering Institute, Russia"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","author":"Margenstern M.","journal-title":"LITP\/IBP Res. Rep."},{"key":"rf7","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1051\/ita\/1997310201591","volume":"31","author":"Margenstern M.","journal-title":"Theoret. Inf. Appl."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00102-4"},{"key":"rf10","author":"Margenstern M.","journal-title":"LITP\/IBP Res. Rep."},{"key":"rf11","first-page":"1395","volume":"320","author":"Margenstern M.","journal-title":"C.R.A.S., Paris"},{"key":"rf14","volume-title":"Computation: Finite and Infinite Machines","author":"Minsky M. L.","year":"1967"},{"key":"rf15","first-page":"899","volume":"13","author":"Pavlotskaya L. M.","journal-title":"Matematicheskie Zametki"},{"key":"rf16","first-page":"52","volume":"27","author":"Pavlotskaya L. M.","journal-title":"Diskretnyj analiz, Sbornik trudov instituta matematiki SO AN SSSR"},{"key":"rf17","first-page":"168","author":"Pavlotskaya L. M.","journal-title":"Proc. MCU'95, LITP\/IBP Res. Rep."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00079-5"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196703001262","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:56:09Z","timestamp":1565114169000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196703001262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":10,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,4]]}},"alternative-id":["10.1142\/S0218196703001262"],"URL":"https:\/\/doi.org\/10.1142\/s0218196703001262","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}