We present a variant with no control states of the Turing machine model of computation in which, at each computation step, the operation to be performed next is determined by the symbol currently scanned and by a bounded-length suffix of the sequence of the operations already executed on the tape. We show that our variant is Turing complete, i.e., it can simulate any (standard) Turing machine. (In fact, we shall provide a strong simulation which replicates the same tape configurations assumed by the simulated Turing machine, without using any additional tape symbol.) As a consequence, we argue that in order to perform general computation tasks, Turing machines do not need to memorize in their control states events arbitrarily far back in the past.
The notion of control states of a Turing machine (TM) is strictly related to that of temporal memory, i.e., the ability to remember events occurred in the past.1 In fact, TMs can remember actions performed in the past (i.e., the operations executed on the tape and/or the symbols read off from it) by encoding the information related to such actions within their control states. Since TMs have only finitely many control states, for each TM there is a fixed bound on the amount of information that can be encoded within control states, and hence a bound on the number of past actions that it can remember. However, despite this quantitative limitation, there is conceptually no limit on how “old” the actions Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
V. Biló, A. Caruso (Eds.): ICTCS 2016, Proceedings of the 17th Italian Conference on Theoretical Computer Science, 73100 Lecce, Italy, September 7–9 2016, pp. 36–48 published in CEUR Workshop Proceedins Vol-1720 at http://ceur-ws.org/Vol-1720 1 In this paper, by a Turing machine we mean a deterministic two-way single-tape Turing machine with the instructions represented by quadruples, as described in [2]. remembered by control states can be, i.e., remembered actions can be arbitrarily old. To clarify this point, consider for instance the case of a TM that recognizes the strings η, over a 2-symbol alphabet {a, b}, whose leftmost and rightmost symbols are different. When the machine reads the rightmost symbol of η, it needs only to remember which was the leftmost symbol. Thus, only two control states suffice for this purpose: one to remember that the leftmost symbol of η was ‘a’ and one to remember that it was, instead, ‘b’. Notice, however, that the number of actions that the machine can perform between the reading of the leftmost and of the rightmost symbols of η can be arbitrarily large, depending on the length of η, and therefore, when the TM reads the rightmost symbol of η, the previous reading of the leftmost symbol turns out to be arbitrarily old.
The capability to remember subsequences of arbitrarily old actions is a peculiarity of TMs and, more generally, of any other device which uses control states (e.g., finite automata). The main aim of this paper is to investigate to what extent this property of TMs is demanded for performing general computations. To this end, we introduce a stateless variant of TMs (namely, with no control states or, equivalently, with only one control state), named Stateless Bounded Temporal Memory Turing Machines (SBTMs).2 From a purely mechanical point of view, SBTMs behave identically to standard TMs. However, at each computation step, the operation to be performed next on the tape by the scanning head of a SBTM (i.e., printing a symbol onto the scanned cell, or moving to the right or to the left of the current position) is determined by a suffix of the sequence of the operations already executed (including the symbols read by the head after these operations and, therefore, also the symbol currently scanned),3 whose length cannot exceed a bound depending solely on the particular machine.
We shall prove that SBTMs are Turing complete, i.e., they can simulate any standard TM. In fact, we shall see that for each TM M one can construct a SBTM V which faithfully simulates M, in the sense that (i) V does not use any additional symbol other than those used by M, (ii) on any input η, V halts if and only if so does M, and (iii) when, on input η, V and M halt, they reach the same tape configuration, while scanning the same cell. As a consequence, we shall also show that the above mentioned ability of TMs to remember within their control states subsequences of arbitrarily old actions is not strictly required for performing general computation tasks (see Section 3.1 for a more precise statement of this fact). The latter property entails in particular a bound on the amount of sequential data items needed to be memorized during computations, which is a relevant topic, e.g., in the field of Streaming Algorithms [5].
Some Turing complete variants of stateless TMs have already been proposed in the literature; however, these act quite differently from ours. This is the case, for instance, for the stateless TM studied in [1], named JTM. The head of a JTM 2 Notice that restricting to one the number of control states in TMs results in a decreased computational power (see [6]). 3 In fact, since SBTMs are devoid of the additional component of the set of control states, the only way for these devices to be aware if something happened in the past, is to trace back their own computations. spans a window of three consecutive tape cells and can thus read/write blocks of three symbols in a single move. However, motion to the left/right of the current head position can occur only by one cell at a time. It turns out that JTMs are Turing complete. Stateless variants of several computational devices other than TMs have also been investigated in the literature, mainly stateless automata such as stateless restarting automata [3], stateless multihead automata [4], stateless pushdown automata [7], etc. However, these devices, even in their original form, have lower computational power than TMs.
The paper is organized as follows. Below we briefly review some notations and terminology which will be used in the rest of the paper. Then, in Section 2, we provide the definition of SBTMs and their semantics. Subsequently, in Section 3, we prove the Turing completeness of SBTMs, based on a simple encoding of the states of a TM, and also discuss other similar encodings. Then, in Section 3.1, we introduce a class of TMs with bounded temporal memory and prove its Turing completeness (based on the Turing completeness of SBTMs), thereby showing the independence of the computational power of TMs from the property of remembering subsequences of arbitrarily old actions within their control states. Finally, we draw our conclusions in Section 4.
Basic notations and definitions. Both in the case of TMs and SBTMs, we shall assume that tape symbols are drawn from the set of symbols S := {s0, s1, s2, . . .}, where s0 is the blank. Often we shall write s0 as . Additionally, we shall use the symbols in the set A := {x, y, } to denote certain active operations (as will be specified in the next section).
Throughout the paper, by a string we shall always mean a finite sequence of symbols belonging to the set S ∪ A . In particular, for every B ⊆ S ∪ A , the set of all strings whose symbols belong to B will be denoted by B∗. We shall write ε for the empty string and |α| for the length of the string α. Notice that we do not distinguish between a symbol and the string of length 1 consisting only of that symbol. The concatenation of two strings α and β is denoted by α . β or, more simply, by αβ. For every string α and each n > 0, αn denotes the string of length n|α| consisting of the concatenation of n copies of α; thus, in particular, we put α0 := ε. A string α is a suffix (resp., prefix) of a string β, and in such a case we write α w β (resp., α v β), if β = γα (resp., β = αγ), for some string γ; α is a factor of β, if β = λαρ, for some strings λ and ρ.
Given a nonempty string α, we denote with Head(α) (resp., Last(α)) the leftmost (resp., rightmost) symbol of α, and denote with Init(α) (resp., Tail(α)) the string of length |α| − 1 obtained by deleting the rightmost (resp., leftmost) symbol of α; we also put Head(ε) := Last(ε) := and Init(ε) := Tail(ε) := ε. 2
SBTMs and their semantics Informal description. A SBTM is equipped with the very same hardware components as a TM (see [2]), namely, a linear tape, infinite in both directions, divided into cells, with a head that at any given instant of time is positioned over a particular cell (the scanned cell), and a finite control box that determines the operations that the head performs on the tape. As for TMs, such operations are of the following four types: (a) reading the symbol in the scanned cell, (b) printing a symbol onto the scanned cell, (c) moving to the left by one cell, and (d) moving to the right by one cell. However, only the operations of type (b), (c), and (d)–the active operations–are actually determined by the control box, since the read operation takes place automatically after each active operation and at the very beginning of each computation by a SBTM (see next).
Before a SBTM begins its computation with a string η as input, the symbols of η are placed (from left to right) in consecutive cells of the tape (the input cells), one symbol per cell, whereas the remaining cells of the tape are left “empty”, i.e., they contain a special blank symbol; the head is positioned over (i.e., scans) the initial cell, namely, the cell immediately to the left of the input cell containing the first (i.e., leftmost) symbol of η. This is the initial configuration for a SBTM with input η. Then, starting from an initial configuration, SBTMs execute their computation steps at discrete instants of time, beginning at time i = 0. Each computation step, but the initial one, consists of the execution of an active operation, of one of the types (b), (c), or (d), immediately followed by a read operation from the cell being scanned by the head. In particular, for i > 0, the active operation O performed at Stepi is determined by the control box of the SBTM as a function of a suffix S of the sequence of the computation steps executed up to Stepi−1 (included). In this case, we say that the SBTM has executed the computation rule (or c-rule) S _ O. Concerning Step0, it is also convenient to regard it as consisting of the execution of an active operation followed by a read operation, as the remaining steps. Thus, we think of Step0 as consisting of the initial activation of the SBTM-control box–the zero operation–immediately followed by a read operation (of the blank symbol contained in the initial cell). After executing a computation step, a SBTM proceeds to the next step, and so on, until it possibly halts; this happens when none of the c-rules S _ O of the SBTM can be executed, for any suffix S of the sequence of computation steps executed up to then. Any finite sequence of consecutively executed computation steps constitutes a (computation) trace of the SBTM, whereas a complete trace is a trace starting at the initial computation Step0. The computation history of a SBTM V is the whole sequence of configurations assumed by the tape of V (namely, tape inscriptions along with head position) during the execution of the computation steps of V.
From the above description, it emerges that a SBTM is essentially a (finite) collection of c-rules. In particular, a deterministic SBTM is a suffix-free collection of c-rules, namely a collection of c-rules containing no two distinct c-rules S0 _ O0 and S00 _ O00 such that S0 is a suffix of S00.4 (Thus, intuitively, at any given computation step, the active operation O that the head of a deterministic SBTM can perform, if any, is uniquely determined by the previous computation steps.) 4 In this paper we are interested only in deterministic SBTMs. Formal definition. To formally define SBTMs, we need a convenient representation of c-rules and their components (i.e., traces and active operations). If we represent the zero operation with the symbol , the left and right head motions with the symbols x and y, respectively, and, for x ∈ S , we represent the operation of printing x onto the scanned cell with the very same symbol x, then every trace T can be handily represented as a string (in the alphabet S ∪ A ) as follows. First of all, we designate each computation step S by a 2-symbol string ox, where o ∈ S ∪ A is the symbol denoting the active operation O performed by S (as explained earlier) and x is the symbol subsequently read from the tape by step S, immediately after the execution of O. Then a trace T can be represented with the string resulting from concatenating the 2-symbol strings representing the computation steps in T , in the same order in which they occur in it. For instance, let T consist of the two computation steps S1 and S2, where: (i) S1 consists of moving the head one cell to the right and then reading the symbol from the tape; and (ii) S2 consists of printing s1 onto the scanned cell and then reading the same symbol s1. Then, T is represented by the string y s1s1. Observe also that any complete trace of a SBTM, i.e., a trace starting at the initial Step0, is represented by a string with prefix . Finally, we represent a c-rule S _ O as the ordered pair (σ, o), where σ is the string representing the trace S (as described above), and o is the symbol denoting the active operation O.
At this point, a SBTM could be formally defined simply as the set of the ordered pairs (σ, o) representing its c-rules S _ O. However, such an approach would require particular care to avoid circularity, since the notion of traces of SBTMs is defined in terms of the very same notion of c-rules which we want to define. For the sake of minimality, we shall circumvent this circularity problem by simply admitting, among the ordered pairs representing ‘genuine’ c-rules, even those pairs (σ, o) in which the string σ could possibly represent no valid trace. Thus we give the following definitions.
Definition 1. A c-rule is an ordered pair (σ, o), also written as σ _ o, where σ is any string in the alphabet S ∪ A and o ∈ S ∪ {x, y}. A set of c-rules is suffix-free, if it contains no two distinct c-rules σ0 _ o0 and σ00 _ o00 such that σ0 w σ00.
Definition 2. A (deterministic) SBTM is any finite, suffix-free set of c-rules. The alphabet of a SBTM V is the set SV of all the tape symbols, but the blank , occurring in any of its c-rules. 2.1
Let V be a SBTM. Suppose that V is ran with some given input string η ∈ (SV)∗. For any time instant i > 0, we denote with TiV(η) the (string representing the) complete trace of V from Step0 up to Stepi, and with CiV(η) the tape configuration reached at the end of Stepi. Letting C be the cell scanned by the head at the end of Stepi, we represent CiV(η) as the triple (λ, s, ρ) in which: (a) λ is the string consisting of the symbols contained, at the end of Stepi, in the (possibly empty) portion of the tape to the left of C from the leftmost cell that has been scanned in any of the computation steps up to Stepi; (b) s is the symbol contained in C at the end of Stepi; and (c) ρ is the string consisting of the symbols contained, at the end of Stepi, in the (possibly empty) portion of the tape to the right of C up to the rightmost cell that either has been scanned in any of the computation steps up to Stepi or is an input cell.
We say that a trace TiV(η) is terminal (relative to V), if there is no c-rule σ _ o in V such that σ is a suffix of TiV(η).
The formal definitions of CiV(η) and TiV(η), for i > 0, are provided recursively as follows. Initially, for i = 0, we put
C0V(η) := (ε, , η) and
T0V(η) := .
For i > 0, let CiV−1(η) := (λ, s, ρ). Then, if TiV−1(η) is terminal, we put CiV(η) := CiV−1(η) and TiV(η) := TiV−1(η). Otherwise, let σ _ o be the c-rule of V such that σ is a suffix of TiV−1(η).5 Then we put recursively: CiV(η) / TiV(η) := (λ, o, ρ) / TiV−1(η)oo,
(Init(λ), Last(λ), s . ρ) / TiV−1(η)xLast(λ), (λ . s, Head(ρ), Tail(ρ)) / TiV−1(η)yHead(ρ), if o ∈ S if o = x if o = y .
The sequence C0V(η), C1V(η), C2V(η), . . . is the computation history of V with input η. We say that V with input η halts, and produce as output a string ω ∈ (SV)∗ (and write V(η) ↓ ω), if, for some i > 0, we have that TiV(η) is terminal and ω is the string obtained from λsρ by deleting all occurrences of the symbol , where (λ, s, ρ) := CiV(η).
As in the case of TMs, SBTMs can be used in three different modalities: (a) to compute partial functions, (b) as string generators, and (c) as language acceptors. Specifically, given a SBTM V, we say that: (a) V computes a (partial) string function f over (SV)∗, if, for all η, ω ∈ (SV)∗, V(η) ↓ ω iff ω = f (η) . (b) V generates a string ω ∈ (SV)∗, if V(ε) ↓ ω.
Finally, in order to use SBTMs as language acceptors, we must first define
what we mean for a SBTM to accept/reject its input. Since SBTMs have no
control states, a possibility could be the following one. We extend the definition
of a SBTM by including two new distinguished symbols, say the symbols y (for
“Yes”) and n (for “No”), such that for no c-rule σ _ o in the SBTM it is the
case that y or n occurs in σ (but possibly we can have that o = y or o = n).6
Then we say that
5 Observe that, according to Definition 2 there is in fact exactly one such c-rule σ _ o.
6 Thus, if the SBTM prints y or n then it halts.
(c) a SBTM V accepts (resp., rejects) an input string η ∈ (SV \ {y, n})∗, if there
is a time instant i > 0 such that Last(TiV(η)) = y (resp., Last(TiV(η)) = n).
Example 1. Let us consider the SBTM V, consisting of the following c-rules
(
_
(
y
(
Turing completeness of SBTMs We prove the Turing completeness of SBTMs by constructing for every TM M a SBTM hMi such that M and hMi are equivalent in the following strong sense, namely, for each input string η: (a) M halts iff hMi halts; and (b) when M and hMi halt, they do with the same tape configuration, i.e., with the same tape content and the same head position.7 (In fact, we shall see informally that the computations of M and hMi are synchronized in an even stronger way.)
To begin with, let us review some useful notations and concepts pertaining to TMs. We assume that the control states that any TM M can assume belong to the set Q = {q0, q1, q2, . . .}, where q0 is bound to denote the initial state of M. Turing machine’s instructions are represented as quadruples of the form (q, x, o, p), where 7 In Section 3.1 we will see, as well, how to construct, for each SBTM V, an equivalent TM h|V|i which simulates V. q, p ∈ Q, x ∈ S , and o ∈ S ∪ {x, y}, whose meaning is that when a TM is in state q while reading the symbol x, the head performs the active operation represented by o, and then the TM enters state p (see [2]). A (deterministic) TM is then formally defined as a finite set of quadruples of the above type, no two of which begin with the same state-symbol pair (q, x), and such that at least one quadruple begins with q0. For every TM M := {(qi, xi, oi, pi) : 0 6 i 6 n}, where n > 0, we put: QM := {qi, pi : 0 6 i 6 n} and
SM := { } ∪ ({xi, oi : 0 6 i 6 n} \ {x, y}) .
Thus, QM and SM are the set of states and the tape alphabet of M, respectively. We say that a TM M activates a state-symbol pair (q, x) ∈ QM × SM when M reads the symbol x from the tape while in state q.8
Let M be a given TM and SM its tape alphabet. Also, let m be the smallest positive index such that SM ⊆ {s0, s1, . . . , sm}. For simplicity, we shall write sm as s (hence, s 6= ). In addition, for x ∈ S , let the 2-symbol string xx be denoted by x .9 The SBTM hMi intended to simulate the TM M will encode each state
L M qi of M with the trace LsML Mi+2LsM, consisting of a sequence of (i + 4) printing steps which uniquely characterizes qi. The simulation proceeds in such a way that when M activates the state-symbol pair (qi, x), (i) the string LsML Mi+2LsMLxM turns out to be a suffix of the current complete trace of hMi and, additionally, (ii) M and hMi have the same tape configuration.
The first state-symbol pair activated by M is (q0, ). Thus we put into hMi the following block S0 of c-rules: _ s,
LsM _ ,
,
LsML M2 _ s,
.
The c-rules in S0 have the effect to generate the complete trace s 2 s L ML M2LsML M (while leaving the tape as in its initial configuration), whose suffix LsML M L ML M correctly encodes the activation of the pair (q0, ). Notice that the block S0 is independent of the specific TM M.
Next, for each instruction I := (qi, x, o, qj ) in M we define a corresponding simulating block hIi of c-rules for hMi. We distinguish the following cases: Case o = y, with y ∈ S : In this case hIi consists of the following c-rules:
i+2LsMLxM _ s , i+2LsMLxMLsML M j+2 _ s ,
i+2 s x s k L ML ML ML M _
, for 0 6 k 6 j + 1 j+2 s
L M _ y . [Comment: Assuming recursively that the current complete trace T of the simulating computation of hMi has the suffix LsML Mi+2LsMLxM (corresponding to the 8 Note that, since a TM initially scans the blank preceding the leftmost symbol of its input string (see [2]), the pair (q0, ) is always activated by every TM at the very beginning of each of its computations. 9 Thus, LxM represents the computation step consisting of printing the symbol x and then reading the same symbol x (just printed) from the tape. activation of the pair (qi, x)), on a tape configuration C in which the head scans a cell C with the symbol x, the above block of c-rules has the effect of: (i) appending the new suffix LsML Mj+2LsMLyM to T ; and (ii) returning a tape configuration C0 in which the head scans the cell C, now containing the symbol y, and that otherwise is identical to C. Notice that the suffix LsML Mj+2LsMLyM encodes the pair state-symbol (qj, y), which is the next pair to be activated by M.] Case o ∈ {x, y}: In this case hIi consists of the c-rule LsML Mi+2LsMLxM _ o, plus the blocks hIiz, for each z ∈ SM, consisting of the following c-rules:
j+2
_ s ,
[Comment: For z ∈ SM, let us put hIiz+ := hIiz ∪ LsML Mi+2LsMLxM _ o . For simplicity, let us suppose that o = x (we can reason similarly in the case in which o = y). Assuming recursively that the current complete trace T of the simulating computation of hMi has the suffix LsML Mi+2LsMLxM (corresponding to the activation of the pair (qi, x)), on a tape configuration C in which the head scans a cell C and the cell L on the left of C contains the tape symbol z ∈ SM, the subblock hIiz+ of hIi has the effect of: (i) appending to T the new suffix hoezaLdsMsLcaMnjs+2thLseMLczeMl;l Lanadn(dii)thraettuortnhienrgwiasenieswidteanpteiccaol ntfiogCu.raNtoiotniceCt0hinatwthheichsutffihxe LsML Mj+2LsMLzM of the prolongated trace of hMi encodes the pair state-symbol (qj, z), which is the next pair to be activated by M.]
Finally, we put:
hMi := S0 ∪ SI ∈ M hIi , completing the formal definition of hMi.
It can easily be verified that the set of c-rules hMi just given is suffix-tree (and, therefore, correctly defines a SBTM according to Definition 2). Indeed, observe that, for each c-rule σi+_2 os ixn t,hfeorsestomSe i > 0 and x ∈ SM, such that, I∈M hIi, the string σ starts with a prefix π of the f_ormo0LisnMLSM L ML M for each c-rule σ0 I∈M hIi: (i) π is not a factor of Tail(σ0); and (ii) if π v σ0 and |σ| = |σ0|, then σ = σ0 and o = o0. Also, observe that each c-rule σ _ o in S0 is such that Head(σ) = , and that does not occur in any c-rule in SI∈M hIi. Notice also that, apart from the trivial case in which SM = { } (in which case we have s = s1 ∈/ SM), the c-rules of hMi use only tape symbols in the alphabet SM of M. Finally, we observe that the above comments to the definitions of the blocks hIi of c-rules, for each instruction I ∈ M, could be easily translated into a formal proof of the fact that hMi correctly simulates M in the strong sense described at the beginning of the section.
Complexity of various encodings. As discussed above, the main idea behind the construction of hMi is to simulate the activation by M of each state-symbol pair (qi, x) by means of the trace LsML Mi+2LsMLxM of hMi, where LsML Mi+2LsM encodes the state qi. This approach can be generalized as follows. First of all, we associate to each state qi of M a suitable codeword c(qi) in the alphabet {LsM, L M} (in which each of the two strings LsM and L M is temporarily regarded as a single symbol) and then simulate the activation of any pair (qi, x) by means of the trace c(qi) . LxM. The case c(qi) := LsML Mi+2LsM corresponds to the approach adopted in the proof sketched above. For each choice of the particular encoding c of the states of M, the definitions of the sets S0 and hIi, for I ∈ M, provided before, generalize straightforwardly, thus obtaining the corresponding sets of c-rules Sc0 and hIic, for I ∈ M (details are omitted for brevity). Clearly, we are interested only in encodings c which are admissible, in the sense that the resulting set of c-rules hMic := Sc0 ∪ [ hIic
I ∈ M is suffix-free. For instance, a family of admissible encodings is provided by the functions ch, for h > 2, such that ch(qi) := LsML Mi+hLsM. Again, for h = 2 we obtain the encoding c2 adopted in our previous proof. If we assume that QM = {q0, q1, . . . , qk−1}, for some k > 1 (in which case we say that M is tight), each of the encodings ch generates a SBTM hMich whose longest c-rule has linear length in the number k of the states of M. More in general, for each TM T and SBTM V, let us define the sizes kTk and kVk by putting: kTk := |QT| and
kVk := max{|σ| : σ _ o ∈ V, for some o ∈ S ∪ {x, y}} (where |QT| denotes the cardinality of QT). Then, using the asymptotic notation Θ, we have that khMich k = Θ(kMk), for each h > 2. This indeed follows from the facts that (A) for each encoding c, khMick = Θ(max({|c(q)| : q ∈ QM})), and (B) |ch(qi)| = 2 · (2 + i + h), for h > 2. Notice, however, that more “compact” admissible encodings c can be devised such that khMick = Θ(log kMk). Indeed, let ζ0, ζ1, ζ2, . . . be the list in quasi-lexicographic order10 of the nonempty strings ζ in the alphabet {LsM, L M} such that ζ contains no two consecutive occurrences of LsM, and consider the encoding f such that f(qi) := LsM2L MζiL MLsM2, for each i > 0. By reasoning much as we did for hMi, it can be shown that hMif is suffix-free, i.e., f is admissible.11 Concerning the size of hMif , we show next that it is logarithmic in the size of M, provided that M is tight. To begin with, it can easily be verified that, for each n > 0, the number of strings of length n in the alphabet {LsM, L M} containing no two consecutive LsM’s is exactly Fn+2, where Fn is the nth Fibonacci number.12 Exploiting the identity Pn j=1 Fj = Fn+2 − 1 10 Hence, the strings ζi’s are firstly ordered by their length and then lexicographically, 11 wieNnnhocwetoerhdetiicnwhhga.ltt.g,oh(.iegqf.iTw)wMe:e=rMceLomsnMocv2oveζneniLttfsairMoio2nnmsatlutlfhyr(neqasiis)nsoustuthmtreuetc“ottshiyboamentbnILoo:lt=”Ma<Ld(qmL0Ms,iMsss.su,isxrbr,2loequa.3nn)F,ddoiwrgn,h(gqceo3ζr)nei,s=xitdh∈eesrSr2teh.seuTlcthaiensnge, ssiontcheaζt0 t=heLseMt ahnIidgζc3o=ntaLinMsLstMh,ewce-rhualevse Lgs(Mq20L) =MLsLMs3M2_L sMLanMd LsM2L MLsM5L L MMLsLM3 M_LsMx3,, plainly implying that hMig is not suffix-free. 12 Thus, F0 = 0, F1 = 1, and Fk+2 = Fk + Fk+1, for k > 0. (for n > 0), we have
F|ζi|+3 − 3 = |ζi|−1 X Fj+2 6 i < j=1 |ζi| X Fj+2 = F|ζi|+4 − 3 j=1 for each i > 2. Given that Fn = Θ(φn) (in fact Fφnn → √15 ), where φ := 1+2√5 ≈ 1.618 is the golden ratio, the latter inequalities imply |ζi| = Θ(logφ i). Hence we have |f(qi)| = Θ(logφ i), which yields, by (A) above and by the tightness of M, khMif k = Θ(logφ kMk) , proving that the size of hMif is logarithmic in the size of M, when M is tight. 3.1
The intuitive considerations of Section 1 concerning the independence of the computational power of TMs from the property of these devices to remember subsequences of arbitrarily old actions within their control states can be made more precise by using a notion of trace of TMs identical to that of SBTM’s trace introduced earlier. More precisely, a trace of a TM M is a sequence of consecutive computation steps of M, where a computation step consists in the execution of an active operation of the scanning head on the tape (i.e., printing a symbol or a left/right motion) followed by the subsequent reading of the symbol contained in the newly scanned cell, as in the case of SBTMs.
Next, suppose that a TM M performs an active operation O on its tape, during a given computation step S. Then, letting T be the complete trace of M consisting of the whole sequence of computation steps preceding S, it can be readily verified that O is uniquely determined by T ; i.e., there is a function, ΥM, which maps each complete trace T to the particular active operation O := ΥM(T ) to be performed next. Now, let us define the class of TMs with bounded temporal memory. Specifically, the class consists of all TMs M for which there is a constant `M (depending on M) such that the (active) operations to be performed next on the tape can be determined only by suffixes of the complete traces of M consisting of at most `M consecutive computation steps; i.e., more formally, the function ΥM is such that ΥM(T 0) = ΥM(T 00), for any two complete traces T 0 and T 00 which share a common suffix of `M computation steps. Intuitively, TMs in the class do not care of (or forget) actions strictly older than `M computation steps. Then, the question arises whether the computational power of TMs decreases when we restrict to the class above. As will be outlined below, given any SBTM V, an equivalent TM h|V|i can be constructed such that h|V|i ∈ ; therefore, since SBTMs are Turing complete, it follows that every TM M is equivalent to some TM T ∈ (e.g., T := h|hMi|i). Hence the answer to the above question is that the class is, in fact, Turing complete.
The basic idea of the construction of the TM h|V|i, for a given SBTM V, is to use the control states of h|V|i to store in turn the strings θ of length 2` − 1, with ` := kV2 k , such that θ . x represents the last ` computation steps of the current (complete) trace of h|V|i, where x is the symbol currently scanned by the head of h|V|i. When h|V|i assumes a state q, while reading the symbol x from the tape, the particular operation O that h|V|i has to perform next is determined by the c-rule σ . x _ o of V such that σ is a suffix of the string θ stored within q, i.e, O is the operation represented by o. Formally, the construction of h|V|i goes as follows. Let θ0, θ1, θ2, . . . be any listing of the strings in the alphabet B := SV ∪{ , , x, y}, where θ0 = , and let Q : B∗ −→ {q0, q1, q2, . . .} be the function such that, for each i > 0: if |θi| < 2`, then Q(θi) = qi; otherwise, if |θi| > 2`, then Q(θi) = Q(θi), where θi is the suffix of θi of length 2` − 1.13 Then, we let h|V|i be the Turing machine whose instructions are all the quadruples (Q(θ), x, o, Q(θxo)) such that σ . x _ o ∈ V and σ w θ, where θ ∈ B∗, x ∈ SV ∪ { }, and o ∈ SV ∪ { , x, y}. It can be verified that h|V|i is indeed a TM equivalent to V and that h|V|i ∈ (details are omitted for brevity). 4
Conclusions We have presented a variant of the Turing machine model of computation with no control states, named SBTM. In each computation step, the operation performed by the head is determined by the symbol currently scanned and by a suffix of bounded length of the sequence of the computation steps previously executed. We have shown that SBTMs are Turing complete, namely they are computationally as powerful as standard Turing machines. In addition, based on the Turing completeness of SBTMs, we have also shown that the computational power of TMs is independent of their ability to remember subsequences of arbitrarily old actions within their control states.
We plan to investigate further computational properties of SBTMs and, in particular, properties related to the following notion of string complexity which naturally arises in this context: given a string η, the SBTM-complexity of η is defined as the size of a minimum sized SBTM V such that: (i) the alphabet of V consists precisely of the symbols occurring in η; and (ii) V generates η. Acknowledgments This work has been partially supported by the FIR project COMPACT: “Computazione affidabile su testi firmati” (code D84C46) and by project PRISMA PON04a2_A, funded by the Italian Ministry of University and Research within the PON 2007-2013 “Smart cities and communities” framework. 13 Note that Q( ) = q0.