UDC 517.11

MATHEMATICS

Yu. Ya. Breitbart, V. A. Kosmidadi

ON TWO SUBCLASSES OF TURING MACHINES REDUCIBLE TO FINITE AUTOMATA

(Presented by Academician P. S. Novikov, 24 I 1969)

Two subclasses of Turing machines are considered—two-way automata and machines operating in a restricted mode. As is known, the truth sets of predicates computable on such Turing machines are sets representable in finite automata \((^{1-3})\). In the present note an estimate is given for the number of states of the corresponding finite automata.

Fix an input alphabet \(\Sigma\) of a machine. Let \(\mathfrak{T}_n\) be the class of machines \(T\) with input alphabet \(\Sigma\), having no more than \(n\) states and such that the truth set of the recursively enumerable predicates computable by them is representable in a finite automaton. Let \(A_T\) be the reduced automaton corresponding to the machine \(T\), and let \(|A_T|\) be the number of its states. Define the function \(\Phi(n)\):

\[ \Phi(n)=\max_{T\in\mathfrak{T}_n}|A_T|. \tag{1} \]

By the methods used in \((^4)\), the following can easily be obtained.

Theorem 1. For any general recursive function \(f(n)\) there exists a number \(n_0\) such that for all \(n>n_0\), \(f(n)<\Phi(n)\). Thus, the function \(\Phi(n)\) is not general recursive.

We introduce two subclasses of Turing machines.

We shall consider Turing machines with working alphabet \(\Xi \supseteq \Sigma\) and set of states \(Q\), whose operation is determined by the functions

\[ \varphi_1: Q\times \Xi \to Q,\qquad \varphi_2: Q\times \Xi \to \Xi,\qquad \varphi_3: Q\to \{R,L\}. \]

The machine, being in state \(q\in Q\) and reading from the tape the symbol \(\xi\in\Xi\), prints the symbol \(\xi'=\varphi_2(q,\xi)\), passes to the state \(q'=\varphi_1(q,\xi)\), and moves one step to the right if \(\varphi_3(q')=R\), or one step to the left if \(\varphi_3(q')=L\). Thus, the motion of the machine is determined only by the state into which the machine enters. The function \(\varphi_3\) partitions \(Q\) into two subsets \(Q=Q^R\cup Q^L\) such that \(Q^R=\{q:\varphi_3(q)=R\}\), \(Q^L=\{q:\varphi_3(q)=L\}\). Let \(|Q^R|=r\), \(|Q^L|=l\). Further, let the initial state of the machine \(q_0\) be such that \(q_0\in Q^R\). The machine computes a predicate in the following sense: before the start of operation, a word \(P\) in the alphabet \(\Sigma\) is written on the tape, to which the machine is applied. The machine stops if and only if its head leaves the portion of the tape initially occupied by the word \(P\); moreover, if the head leaves the tape portion on the right, and the machine is in a state from some subset \(F\subseteq Q^R\), then the computed predicate is true on the word \(P\).

The first subclass we consider is two-way automata \((^{1,2})\). These are Turing machines for which, for all \(q\in Q\) and \(\xi\in\Sigma\), \(\varphi_2(q,\xi)=\xi\), i.e., they are nonwriting and nonerasing machines. By analogy with (1), introduce the function \(\Phi_1(r,l)\).

Theorem 2. If \(|\Sigma|\ge 3\), \(l\ge 1\), then \(\Phi_1(r,l)=r^{\,l+1}+1\).

Suppose that the word \(P\) is written on the tape. Fix a boundary between two neighboring cells. While working on the word \(P\), the machine crosses this boundary for the first time in a state \(q^R \in Q^R\), for the second time in a state \(q^L \in Q^L\), and so on. The word thus obtained is the trace at the given boundary (or at the given point).

The second subclass we consider is Turing machines operating in a bounded mode \((^3)\), i.e., machines for which there exists a number \(c\) such that, if the machine halts on the word \(P\), then the length of the trace at any point of the tape is bounded by \(c\). By analogy with (1), define the function \(\Phi_2(r,l,c)\).

Theorem 3. For \(|\Sigma| \geq 2\),

\[ \left(r-\left[\frac{c-1}{2}\right]-3\right)^{\,l\left[\frac{c-1}{2}\right]} \ll \Phi_2(r,l,c) \ll (r+1)^{\frac{l\left[\frac{c+1}{2}\right]}{l-1}} . \]

Let \(\mathfrak{S}_n\) be the class of Turing machines operating in a bounded mode and having no more than \(n\) states. For \(T \in \mathfrak{S}_n\), denote by \(c_T\) the constant bounding the lengths of the traces of the machine \(T\), and define the function \(\Phi_3(n)\):

\[ \Phi_3(n)=\max_{T\in\mathfrak{S}_n} c_T; \]

using the method of \((^4)\), it is easy to obtain that Theorem 1 holds if in it, as \(\Phi(n)\), one takes the function \(\Phi_3(n)\).

Received
23 I 1969

REFERENCES

\(^1\) M. O. Rabin, D. Scott, Kiberneticheskii sbornik, vol. 4, 1962, p. 58.
\(^2\) J. C. Shepherdson, Kiberneticheskii sbornik, vol. 4, 1962, p. 92.
\(^3\) B. A. Trakhtenbrot, Algebra i logika, Seminar, 3, 1964, p. 33.
\(^4\) Rado, Bell System Technology J., 41, No. 3, 877 (1962).