ON THE OPTIMAL NUMBER OF INSTRUCTIONS FOR UNIVERSAL TURING MACHINES CONNECTED WITH A FINITE AUTOMATON
Maurice Margenstern, LIOUDMILA PAVLOTSKAÏA · International Journal of Algebra and Computation · 2003
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.