MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

# Anton Salikhmetov

 61 Reputation 314 views

## Registered User

 Name Anton Salikhmetov Member for 1 year Seen 2 days ago Website Location Helsinki, Finland Age 26
I am a software engineer with deep knowledge of IEEE 1003.1 in both formal and practical aspects, currently researching the simplest automata for optimal reduction of lambda expressions.
 May7 revised Schönhage’s SMM with only one instructiondeleted 1 characters in body May7 revised Schönhage’s SMM with only one instructiondeleted 8 characters in body May7 asked Schönhage’s SMM with only one instruction May6 answered Turing-complete primitive blind automata May6 accepted Universality of blind graph rewriting May6 answered Universality of blind graph rewriting May6 comment Turing-complete primitive blind automataen.wikipedia.org/wiki/Pointer_machine - looks like my contruction is (nearly) the same as Schönhage's Storage Modification Machine (SMM) model. Apr22 comment Behavior of a one-point-changing operation on functionsIt can be any function on natural numbers. Apr22 asked Behavior of a one-point-changing operation on functions Apr9 revised Hypothesis: interaction-based model for maximum consistent theoriesedited title Apr9 asked Hypothesis: interaction-based model for maximum consistent theories Apr9 asked Is it possible to implement η-reduction in interaction nets? Apr7 asked Optimal Reduction in Interaction Calculus Mar26 asked Turing-complete primitive interaction systems Mar19 comment Turing-complete primitive blind automataWith 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. Mar19 awarded ● Supporter Mar18 revised Turing-complete primitive blind automataadded 156 characters in body Mar18 comment Turing-complete primitive blind automataThe question about universality of $A_{1111, 11010}$ still remains open. What we found is that if the first binary sequence in the pair is shorter than $1111, \quad$ there will not be any rewriting scenarios for an arbitrary node. Mar17 revised Turing-complete primitive blind automataadded 90 characters in body Mar17 revised Turing-complete primitive blind automataedited tags Mar17 revised Turing-complete primitive blind automataadded 107 characters in body Mar17 comment Turing-complete primitive blind automataThe 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. Mar17 revised Turing-complete primitive blind automataadded 10 characters in body Mar17 revised Turing-complete primitive blind automataadded 11 characters in body; deleted 2 characters in body Mar17 revised Turing-complete primitive blind automataadded 6 characters in body; deleted 2 characters in body Mar17 revised Turing-complete primitive blind automataadded 1239 characters in body Mar17 comment Turing-complete primitive blind automataSo far, we managed to find a pair $(1111, 11010)$ as a candidate of the minimal length. For this pair, the possible states not necessarily leading to a dead-end state break into three types: 1) $f_1(f_1(1)) = 1$, 2) $f_1(f_1(f_1(1))) = 1$, and 3) $f_1(f_1(f_1(f_1(1)))) = 1$. In a state of type (2), a node $f_1(1)$ changes; let us call it "write". 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 the three nodes. We have rewriting scenarios for an arbitrary node. Mar17 awarded ● Commentator Mar17 comment Turing-complete primitive blind automataLet us notice that for any pair of binary sequences, there are graphs that do not change during transion. Thus, one option of halt is to reach a dead-end state. Alternatively, if we simulate some TRS, for instance lambda calculus or interaction nets, we can instead dedicate to outside world to check if the current state corresponds to a normal form. Mar16 comment Turing-complete primitive blind automataYes, I think such representation can indeed be seen equivalent for the definition of primitive blind automata, except that the input alphabet is only one pair of binary sequences. For a finite set of pairs, we already have constructed a Turing-complete machine that simulates directed interaction combinators by Lafont, the input being one fixed repeating sequence of total about hundred pairs. Mar16 revised Turing-complete primitive blind automataadded 256 characters in body Mar16 comment Turing-complete primitive blind automataThe graph corresponding to a state $q = (f_0, f_1) \in (N \rightarrow N) \times (N \rightarrow N)$ of a primitive blind automaton has infinite number of vertices, and infinite number of arrows. I assume that implies that the state cannot be described as a finite-state machine. Mar16 revised Turing-complete primitive blind automatadeleted 9 characters in body Mar16 comment Turing-complete primitive blind automataYes, the original definition does indeed imply that in the suggested graph interpretation of the primitive blind automata, the root node is always the natural number 1. Mar16 revised Turing-complete primitive blind automataadded 338 characters in body Mar16 comment Turing-complete primitive blind automataLet $A = (f_0, f_1) \in (N \rightarrow N) \times (N \rightarrow N)$ and $p = (101, 0111)$. We consider natural number 1 as the root node. Then, in the graph $A' = \delta(A, p)$ the arrow labeled 1 from the node $f_1(f_0(f_1(1)))$ points to the node $f_1(f_1(f_1(f_0(1))))$. Mar16 revised Turing-complete primitive blind automataadded 1 characters in body Mar16 revised Turing-complete primitive blind automataadded 730 characters in body Mar16 comment Turing-complete primitive blind automataEach 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. Mar15 revised Turing-complete primitive blind automataadded 3 characters in body Mar15 revised Turing-complete primitive blind automatadeleted 10 characters in body Mar15 comment Turing-complete primitive blind automataThe 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. Mar15 asked Turing-complete primitive blind automata Jan13 awarded ● Scholar Jan13 comment Algebraic structure generated by primitive graph operationsThe mentioned paper is very interesting and close to what I am looking for. Thank you very much.