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
Is this your account?

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.
May
7
 revised Schönhage’s SMM with only one instruction
deleted 1 characters in body
May
7
 revised Schönhage’s SMM with only one instruction
deleted 8 characters in body
May
7
 asked Schönhage’s SMM with only one instruction
May
6
 answered Turing-complete primitive blind automata
May
6
 accepted Universality of blind graph rewriting
May
6
 answered Universality of blind graph rewriting
May
6
 comment Turing-complete primitive blind automata
en.wikipedia.org/wiki/Pointer_machine - looks like my contruction is (nearly) the same as Schönhage's Storage Modification Machine (SMM) model.
Apr
22
 comment Behavior of a one-point-changing operation on functions
It can be any function on natural numbers.
Apr
22
 asked Behavior of a one-point-changing operation on functions
Apr
9
 revised Hypothesis: interaction-based model for maximum consistent theories
edited title
Apr
9
 asked Hypothesis: interaction-based model for maximum consistent theories
Apr
9
 asked Is it possible to implement η-reduction in interaction nets?
Apr
7
 asked Optimal Reduction in Interaction Calculus
Mar
26
 asked Turing-complete primitive interaction systems
Mar
19
 comment Turing-complete primitive blind automata
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.
Mar
19
 awarded ● Supporter
Mar
18
 revised Turing-complete primitive blind automata
added 156 characters in body
Mar
18
 comment Turing-complete primitive blind automata
The 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.
Mar
17
 revised Turing-complete primitive blind automata
added 90 characters in body
Mar
17
 revised Turing-complete primitive blind automata
edited tags
Mar
17
 revised Turing-complete primitive blind automata
added 107 characters in body
Mar
17
 comment Turing-complete primitive blind automata
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.
Mar
17
 revised Turing-complete primitive blind automata
added 10 characters in body
Mar
17
 revised Turing-complete primitive blind automata
added 11 characters in body; deleted 2 characters in body
Mar
17
 revised Turing-complete primitive blind automata
added 6 characters in body; deleted 2 characters in body
Mar
17
 revised Turing-complete primitive blind automata
added 1239 characters in body
Mar
17
 comment Turing-complete primitive blind automata
So 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.
Mar
17
 awarded ● Commentator
Mar
17
 comment Turing-complete primitive blind automata
Let 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.
Mar
16
 comment Turing-complete primitive blind automata
Yes, 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.
Mar
16
 revised Turing-complete primitive blind automata
added 256 characters in body
Mar
16
 comment Turing-complete primitive blind automata
The 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.
Mar
16
 revised Turing-complete primitive blind automata
deleted 9 characters in body
Mar
16
 comment Turing-complete primitive blind automata
Yes, 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.
Mar
16
 revised Turing-complete primitive blind automata
added 338 characters in body
Mar
16
 comment Turing-complete primitive blind automata
Let $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))))$.
Mar
16
 revised Turing-complete primitive blind automata
added 1 characters in body
Mar
16
 revised Turing-complete primitive blind automata
added 730 characters in body
Mar
16
 comment Turing-complete primitive blind automata
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.
Mar
15
 revised Turing-complete primitive blind automata
added 3 characters in body
Mar
15
 revised Turing-complete primitive blind automata
deleted 10 characters in body
Mar
15
 comment Turing-complete primitive blind automata
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.
Mar
15
 asked Turing-complete primitive blind automata
Jan
13
 awarded ● Scholar
Jan
13
 comment Algebraic structure generated by primitive graph operations
The mentioned paper is very interesting and close to what I am looking for. Thank you very much.