TwoOyts
Suffice Summer '06 
by
Zweibieren 
Physpics 
Our understanding of physics has reached to smaller and smaller elementary components. Discovery has moved from molecules to atoms and on to protons, neutrons, electrons, quarks, and possibly Planckscale strings. We may therefore ask, is there a simplest structure from which all others can be constructed? This paper suggests an alternative that appears to be the simplest possible, the twooyt Introduction strings are simple what is simplest? oyts in brief an noyt is a featureless object with n directed links to other noyts an noyt space is a connected graph of noyts an oytspace is not static, but changes constantly changes occur because rule engines are associated with some of the oyts a rule engine has a set of rules each rule is two graphs, a template and a successor the engine compares the graph rooted at its associated oyt. When a template matches, the matched graph is replaced with the successor graph. Literature finite state machines lisp sexpressions "pure" lisp mutates by copying and replacing oyt engines are "impure" Lisp the quivalent of rplaca and rplacd Conway's Game of Life Loop quantum gravity oyts can do curved space straightforwardly, but curved spacetime is harder Seth Lloyd  computing the universe ONAG numbers COGENT analytic and synthetic assignments to be distinguished from Nondeterministic automata these are machines that pursue multiple solution paths simultaneously quantum computing again, these machines follow multiple paths at once oyts follow a single computational history they are random in tha that path cannot be predicted nor can a computation be repeated so what good is it? the value of randomness can be seen in the invention of sex DNA provides for replicating the form but combining the variations from two parents [Seth Lloyd] Note that it sperfectly possible to design oyt computations that are deterministic. The trick is to devise oyt structures that force the choice of only one path at each point Formal Definition of an Oyt Space This section defines an oyt space, Ω, to be a directed graph G of oyts where some oyts have associated engines. An engine runs a set of rules chosen from among a set R. Each rule in R lists two oyt subgraphs, a template and a successor. Each engine continuously compares the subgraph rooted at its oyt to the templates in its rules. When the engine finds a rule whose template matches a subgraph, that subgraph is replaced with the rule's successor. The engine is then removed from Ω along with its associated oyt, but the successor graph may have new engines and they are started immediately. Figure 'oyt space concepts' illustrates this terminology. [Figure 'oyt space concepts'
about here]
Oyts are defined with the notations of setsw, tuples, and mappings. If this is new to you, a brief introduction is on the notation page. We begin with the general concept of a graph. A graph G is a tuple (O, M), where O is a set of objects, S
M is a mapping M:o→{o_{1}, o_{2}}, where o,o_{1},o_{2}∈S
(That the map produces an unordered set is appropriate for oyt graphs
because links and the oyts they lead to are indistinguishable.)M implies a set of paths on O, where a path is a sequence of objects, (o_{0}, o_{1}, o_{2}, ...) such that o_{i+1}∈M(o_{i}). A path may have a single object in it. A point, say p, is said to "have a path" to another, say q, if there is a path (p, o_{1}, o_{2}, ..., q). The graph G=(O,M) is connected if for every two points in O, there is some point that has paths to both. A path is acyclic if its objects can be renumbered so the indices of the path's origins and termini are monotonically increasing. (That is, no object has an edge leading to an object earlier in the path.) Let O be the set of oytswhere each oyt is a featureless, dimensionless nothing. If you have an oyt, you can tell nothing about it. However, if that oyt is in an oyt graph, you can ask the graph for the two oyts that your original links to. Let Λ be a unique, distinguishable objectthe empty destination. When O⊂O, the set O∪{Λ} is called a destination set. An oyt graph, G is a tuple (O, M), where O⊂O
M is a mapping M:o→{d_{1},
d_{2}},
where o∈O
and d_{1}, d_{2} ∈ O∪{Λ}
(O, M) is a connected graph
When d_{i} is an oyt, o is said to link to that oyt.
Where d_{i} is Λ, then that is
called an empty link. (Note:
This paper
discusses 2oyts. More general noyts
are defined simply by
amending M to map to sets with n
instances of d_{i}.)In examples, oyts graphs are drawn as little dots and arrows. It is sometimes useful to remember that these are not the oyt graph, but are just one way of representing it. There are many other ways to graph mappings. Later on we will be able to define "rule." A rule tells an "engine" one possible way to modify an oyt graph. For now it is sufficient to specify that: R
is the set of all rules.
An engine, E, is a tuple (F, q, a), where F⊂R
The mechanism q is the same in
all engines. The value a is
called the activation token.
The engine does nothing when a=silent. When a=running,
E applies the rules in F to
oyts in an oyt graph in the manner
described in the next section. q is a mechanism a∈{running, silent} E is the set of all engines. In many applications, most of the engines are the ∅ element in E. An oyt space, Ω, is a tuple (G, E, A), where G is an oyt graph (O, M)
When A maps o to e, engine e is said to
be associated with oyt o.E⊂E; all members of E have a=running A is a mapping A:o→e, where o∈O, e∈E To define R we need some more concepts. Each rule has a template and a successor which are both essentially oyt graphs, but each has some additional properties. The template uses edge references to refer to places in the successor. The concept of edge references is also used to specify that the template be acyclic. The successor has engines like an oyt space, but they are silent. In an oyt graph G composed as (O,M), an edge reference is a 2tuple of oyts (o_{1}, o_{2}) such that for some x, M maps o_{1}→{o_{2},o_{x}}. The first oyt, o_{1}, is called the origin of the edge reference and the second, o_{2}, is its terminus. The set of all edge references for G is denoted by U_{G}. An edge reference is on the verge in G if M maps its terminus, o_{2,} to (Λ,Λ). The set V_{G} is defined to be the set of all edge references to edges on the verge in G. By virtue of the definitions, V_{G}⊂U_{G}. Given an arbitrary oyt graph G composed as (O, M), let P denote the set O'∪{Λ}∪V_{G}. That is, the elements of P are a set of oyts (not those of G), the empty destination, and the set of edge references to the verge of G. Then a template graph for G is a tuple (O', Q, r), where O'⊂O
By this definition, a template graph is a tree and connects to G only
where its leaves are edge references into G. The distinguished oyt r is
the root of the
template. r∈O' Q: o→{p_{1}_{, }p_{2}}, o∈O', p_{i}∈P all paths designated by Q are acyclic for all x∈O', either x=r
or there is a path from r to x
A successor graph is an oyt space (H, E, A, r), where H is an oyt graph (O, M)
As with a template graph, r
is called the root of the successor graph. It is not Λ, so a template
cannot be replaced with Λ.E⊂E all members of E have a=silent A is a mapping A:o→e, where o∈O, e∈E r∈O of H A rule, R, is a tuple (t, s), where t
is a template graph for H of
s
Graph t is the rule's template and s is its successor. See Figure 'rule
illustration'.s is a successor graph [Figure 'rule illustration' here]
Operation When an oyt space is created, the activation tokens in its engine are set to running. Each engine scans the graph rooted at its associated oyt, o. It checks to see if any template matches the the graph rooted at o. When it finds one, the matched subgraph is replaced with the successor from the same rule. The associated oyt, o, is no longer part of its oyt graph, and the engine ceases operation. However, any engines in the successor graph are started up immediately. We want to describe more formally the operation of a running engine E as it processes the oyt graph beginning from the engine's associated oyt o. The mechanism q runs through the rules F of E, processing one rule R∈F at a time. It compares the template t of R to the subgraph emanating from o, and if a match is found, replaces that subgraph with a copy of the successor s of R. It is this last stepcomparison and replacementthat is described more formally here. Before doing the compare and replace operation, q makes a copy of t and s. If the comparison is successful, the copy of s will be incorporated into the oyt space. t is also copied so that any edge references are to edges in the copy of s, not those in the original s. The engines in the copy of s remain silent. The outer level is a function, compareAndReplace(o, t, s) having as arguments the associated oyt o, the copy of template t, and the copy of successor s. The heart of the compareAndReplace() is a recursive function try(j, v) which compares j, an oyt from the template, against v, and oyt from the subject oyt graph. The successor is not needed as an argument, because the edge references in t refer to it where necessary. As a side effect, try() creates a stack of mapping operations. After a successful match, compareAndReplace() applies these mapping operations to modify the oyt graph. Some of the operations link oyts in the copy of s to oyts in the existing oyt graph. Other operations change links in matched portion of the oyt graph so they link to Λ instead of continuing to link into the oyt graph. As we process an oyt, we need to refer to its pieces. The notation is in this form dissect o into {c, d}
which indicates that M maps o
to two values and variables c
and d will be made to refer
to those values. To process an edge reference, r, we need to refer to the
referenced pieces. Now r
refers to the edge from an origin oyt i
to a head oyt h, where h is mapped to {Λ,Λ}. The other
link from i is h's sibling and will be called sib. The notation isdissect r into i→{{Λ,Λ}, sib}
which analyzes r and sets
variables i and sib.
Similarly, a mapping to push
on the stack is written asi→{g, h}
which is a mapping from i to
the set {g, h}.compareAndReplace(o, t, s) dissect s into {c, d}
push o→{c, d} if try(t, o) change to silent the engines in the subgraph matched by t change M according to the stack change to running the activation token in every engine in s Function try(v, j) compares a template oyt v versus an oytspace oyt j. All it can test for is whether a link is (L) a link to an oyt, (Λ) a link to the empty destination, or (R) an edge reference into the successor. For j the cases are LL, LΛ, and ΛΛ. For v, the template oyt, edge references may exist, so there are three more cases: LR, ΛR, and RR. The function nodetype(o) describes the links of o by returning one of the six possible combinations of L, Λ, and R. Now we can write try(): try(j, v) function f = ActionTable[nodetype(v), nodetype(j)]
return f(j, v) The ActionTable is a 3x6 grid naming the functions to apply for each combination of nodetypes:
Now we need only write the eight functions appearing in ActionTable. In each, j is an oyt in the oyt graph and v is an oyt in the template. succeed(j, v) return true
fail(j, v) return false
tryone(j, v) // LΛ, LΛ dissect j into {a, Λ}
dissect v into {c, Λ} return try(a, c) tryboth(j, v) // LL, LL dissect j into {a, b}
dissect v into {c, d} if try(a, c) then if try(b, d) return true if try(b, c) then if try(a, d) return true return false bindtryone(j, v) // j is LΛ, v is LR dissect j into {a, Λ}
dissect v into {s, r} disect r into i→{{Λ,Λ}, sib} m = new mark; push m push i→{Λ, sib} // s≠Λ, so r matches Λ if try(a, s) return true pop m and all more recent items return false bindtryboth(j, v) // j is LL, v is LR dissect j into {a, b}
dissect v into {s, r} dissect r into i→{{Λ,Λ}, sib} m = new mark; push m push i→{a, sib} // to link to a from successor push j→{b, Λ} // to remove link from j to a if try(b, s) return true pop all items more recent than m push i→{b, sib} // to link to b from successor push j→{a, Λ} // to remove link from j to b if try(a, s) return true pop m and all more recent items return false bindone(j, v) // j is LΛ or ΛΛ v is ΛR dissect j into {a, Λ}
dissect v into {r, Λ} dissect r into i→{{Λ,Λ}, sib} m = new mark; push m push i→{a, sib} // to link from successor to a push j→{Λ, Λ} // to remove link from j to a return true bindboth(j, v) // v is RR dissect j into {a, b}
dissect v into {r_{1}, r_{2}} dissect r_{1} into i_{1}→{{Λ,Λ}, sib_{1}} dissect r_{2} into i_{2}→{{Λ,Λ}, sib_{2}} push i_{1}→{a, sib_{1}} push i_{2}→{a, sib_{2}} push j→{Λ,Λ} return true Q must be an acyclic graph because it is impossible to detect cycles in an oyt graph without modifying the graph; and an engine must be able to match the template against an oyt graph. Note: the oyt graph itself may have cycles and the template may run around such a cycle as many times as it likes. But the template must list all the elements around the cycle for each time it wants to loop around. See figure "matching cycles". [Figure "matching cycles" here] Example 1 circulating engine Example 2 expanding space Higher Level Structures oriented oyts  distinguishing the two links tagged oyts  distinguishing oyts from each other TwoOyts Suffice constructing a noyt from twooyts Tagged, oriented two oyts (toto) Simulation of a Turing Machine An oyt space can perform computation in this sense: We define a mapping from the initial problem to an oyt space, we define an engine set for the problem, and we define a mapping from a resulting oyt space back to the problem space. Given these definitions, we ce run the computation in the oyt space and observe that the result is identical that from running the computation on the corresponding Turing machine. Representing the tape, the state machine, and execution Therefore, twooyts suffice for computation Beyond Turing Machines Do oyt spaces have properties that a Turing machine does not. The answer is yes. Turing machines cannot demonstrate random behavior, while oyt spaces can. The fundamental source of this randomness is that the mechanism q cannot distinguish between the links from an oyt. So when it compares a subgraph to a template, the order of testing the two branches from each oyt is indeterminate. It is actually easy to define Turing machines so they have random behavior. Simply put in some rule that makes a random choice during its computation. I would like to argue that oyt spaces are inherently random, while randomness must be inserted into Turing machines on purpose. However, such an argument is almost as hard to make as is the fundamental argument that a machine generates random behavior. Emulating the Physical World physics posits many bizarre and unintuitive behaviors oyts can represent these as tutorial tool as a model of the physical world examples creating space out of nothing inflationary expansion curved space excess dimensions moving particles interaction of photons and electrons the manyworlds kerfluffle Open Questions limiting the number of inlinks simpler engines should multiple mexchanisms be allowed? are multiple engine types needed (that is, differing subsets of R) details of template matching: simultaneity ambiguity resolution first match vs best match vs random choice among all matches effects of simultaneous replacement on adjacent oyts does it make sense to talk about oyt forests there can be no connection between the trees engines are magic, like the internals of a string one way to make a universe more simply than with oyts would be to find a simpler mechanism replacement with an engine does not necessarily expunge the matched subgraph from the oyt graph can the mechanism find the parent of an oyt so that the successor could be Λ need the successor be connected? the result could be implicitly connected by virtue of the structural design could be done with flag and a pointer to an oyt instead of edge references here is no need for {Λ,Λ}, could be Λ ConclusionThis paper has described twooyts and a computation mechanism for them. The combination is sufficient to represent anything and to perform any computable function. Further work suggests that randomness is a natural addition to oyt computation, making them suitable for representing such random processes as the evolution of quantum processes. Indeed, it may be possible to represent the entire universe in tagged, oriented twooyts. 

references http://acm.uva.es/p/v2/251.html Nondeterministic Trellis Automata 
Copyright 2006, Zweibieren 
4 Aug 2006 09:07 PM

Page maintained by Zweibieren 