Turing-complete primitive blind automata

Let $N$ be the set of natural numbers, $S$ be the set of finite binary sequences, and

$Q = [N \rightarrow N] \times [N \rightarrow N],$

where $[N \rightarrow N]$ is the set of all computable functions on natural numbers.

Then, let us consider the family of primitive blind automata

$A_p = (Q, \{p\}, Q, \delta, \delta)$

parameterized by a pair $p \in S \times S, \quad$ whose transition function is defined as follows:

$δ(f_0, f_1, x_1 \dots x_m, y_1 \dots y_n) = (f_0, f'_1), \quad$ where

$f'_1(k) = f_{y_n}(\dots f_{y_1}(1) \dots), \quad$ when $k = f_{x_m}(\dots f_{x_1}(1) \dots);$

$f'_1(k) = f_1(k), \quad$ when $k \neq f_{x_m}(\dots f_{x_1}(1) \dots).$

Are there Turing-complete primitive blind automata?

We are looking for $p$ of minimal length that makes $A_p$ Turing-complete.

Remarks

The input alphabet is a set of one element. The output is the current state. Let us notice that for any pair $p \in S \times S, \quad$ there are states of $A_p$ that do not change during transition. Thus, one option of halt is to reach a dead-end state. In other words, the computation stops when the current state is a fixed point for the transition function. Such automata are Turing-complete iff there is a way to encode any recursive function into an initial state, for example in the form of lambda terms or interaction nets by Lafont. The encoding has to be an algorithm that eventually halts for any lambda term or any equivalent structure.

Each state $q = (f_0, f_1)$ of a primitive blind automaton can also be described itself as an automaton

$M_{f_0, f_1} = (N, \{0, 1\}, N, \phi_{f_0, f_1}, \phi_{f_0, f_1}), \quad$ where $\phi_{f_0, f_1}(n, b) = f_b(n).$

Alternatively, each state $(f_0, f_1)$ can be thought of as an infinite directed graph with exactly two arrows from each node, the arrows being labeled $0$ and $1. \quad$ The node corresponding to the natural number 1 is considered as the root node of the graph. During transition, the first binary sequence in $p$ represents a path (from the root node) to the node whose arrow labeled $1$ is changed to point to the node through the path corresponding to the second binary sequence in $p.$

For example, let $q = (f_0, f_1)$ and $p = (10, 011). \quad$ Then, in the graph $q′ = \delta(q, p)$ the arrow labeled $1$ from the node $f_0(f_1(1))$ points to the node $f_1(f_1(f_0(1))), \quad$ and this arrow is the only difference between the graphs $q$ and $q'.$

So far, we have found $(1111, 11010)$ as a possible candidate for a universal primitive blind automaton. For this pair of binary sequences, the states not necessary leading to a dead-end state break into the following three types.

1. When $f_1(f_1(1)) = 1.$
2. When $f_1(f_1(f_1(1))) = 1.$
3. When $f_1(f_1(f_1(f_1(1)))) = 1.$

In a state of type (2), a node $f_1(1) \neq 1$ changes; let us call it "writing". In turn, (1) and (3) change the root node; let us call them "next". (1) and (2) leave a node whose arrow labeled 1 points to the root node, while (3) leaves a linked list of three nodes ending with the root node. Thus, a rewriting scenario is possible for an arbitrary node $n. \quad$ Namely, there is a state that leads to "writing" $n, \quad$ switching "next" to some other node $x \neq n, \quad$ switching back to $n$, and "writing" $n$ again with another value.

Although the question about universality of $A_{1111, 11010}$ still remains open, we found that if the first binary sequence in the pair is shorter than $1111, \quad$ then there will not be any rewriting scenarios for an arbitrary node.

• I'm not sure I understand the question, i.e. what it would mean that this model is Turing-complete: -what it the input of such an automaton ? -when does the computation stops ? -what is the output ? – Denis Mar 15 '13 at 14:42
• The input alphabet is a set of one element. The output is the current state. The computation stops when the current state is a fixed point for the transition function. Such automata are Turing-complete iff there is a way to encode recursive functions into its initial states. – Anton Salikhmetov Mar 15 '13 at 15:12
• It would help if you explain what is primitive blind automaton "in words" rather than in symbols. This is the first time I see it and I cannot understand how it works. – Mark Sapir Mar 15 '13 at 23:01
• Each state (f_0, f_1) can be thought of as a directed graph with exactly two arrows from each node, the arrows being labeled 0 and 1. One node is considered as the root node of the graph. During transition, the first binary sequence in p represents a path (from the root node) to the node whose arrow labeled 1 is changed to point to the node through the path corresponding to the second binary sequence in p. – Anton Salikhmetov Mar 16 '13 at 4:38
• I see, so the problem is whether you can construct a universal machine this way using only one transition. At least now I understand what the problem is. I doubt this is universal (because a Turing machine with one command, and other similar devices, like groups with one defining relation, are not universal), but this is not a very strong doubt. The question is interesting. – Mark Sapir Mar 17 '13 at 0:34

Probably I also don't understand the question but then by universality you mean that Q can change or that p can change? I think both cases are easy to be seen to be universal but I must misunderstand something.

In the first, pick p=(1,11) and let the integers correspond to the steps of your favorite Turing-machine such that you take some computable injection from (x-tape content, s-machine state, h-position of head) to the integers. In this case Q will be also nice, you don't even need the 0's.

If Q is fixed, then proceed similar as before, except now encode (T-description of TM,x,s,h) into the integers and p will have some form like (00001,000011) where the first k zeros take us to the start conditions of the k-th TM.

I also suggest that you try posting your problem on https://cstheory.stackexchange.com/ instead of MO.

• The suggested structure for an initial state of $A_{1, 11}$ is unfortunately not an encoding for recursive functions due to the halting problem. The encoding has to be an algorithm that eventually halts for any lambda term. – Anton Salikhmetov Mar 17 '13 at 10:53
• Well, I told you I probably don't understand the question... – domotorp Mar 17 '13 at 17:35
• With the current definition of primitive blind automata, one computable function $f_1$ can indeed simulate a universal Turing machine having its tapes enumerated. Thus, $A_{1, 111}$ is Turing-complete with encoding being one edge $f_1(1) = x$ where $x$ corresponds to the initial tape of the Turing machine for a given recursive function. As we are looking for initial states $(f_0, f_1)$ that would be simple in some sense, we need to rethink the definition and come up with a more precise version of our question. – Anton Salikhmetov Mar 19 '13 at 7:59

The construction is similar to that of Schönhage's Storage Modification Machine (SMM) model.