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.
- When $f_1(f_1(1)) = 1.$
- When $f_1(f_1(f_1(1))) = 1.$
- 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.