Two-Oyts Suffice

Two-Oyts Suffice
Summer '06

by Zweibieren Two full steins of beer

Abstract: A two-oyt is an object with two links, each connecting to nothing, or to a two-oyt. This paper will show that two-oyts alone suffice to represent anything. There are natural representations for objects having any number of dimensions and non-euclidean geometries. When associated with a simple computational mechanism, oyts suffice to represent any computation.

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 Planck-scale 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 two-oyt

Introduction
     strings are simple
     what is simplest?

oyts in brief
     an n-oyt is a featureless object
            with n directed links to other n-oyts
     an n-oyt space is a connected graph of n-oyts
     an oyt-space 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 s-expressions
         "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 space-time is harder
    Seth Lloyd - computing the universe
    ONAG numbers
    COGENT analytic and synthetic assignments

to be distinguished from
Non-deterministic 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₁, o₂},

where o,o₁,o₂∈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₀, o₁, o₂, ...) 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₁, o₂, ..., 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 oyts--where 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 object--the 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₁, d₂},

where o∈O and d₁, d₂ ∈ 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 2-oyts. More general n-oyts 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
q is a mechanism
a∈{running, silent}

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.

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)
E⊂E; all members of E have a=running
A is a mapping A:o→e, where o∈O, e∈E

When A maps o to e, engine e is said to be associated with oyt o.

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 2-tuple of oyts (o₁, o₂) such that for some x, M maps o₁→{o₂,o_x}. The first oyt, o₁, is called the origin of the edge reference and the second, o₂, 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
r∈O'
Q: o→{p₁_,p₂}, 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

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.

A successor graph is an oyt space (H, E, A, r), where

H is an oyt graph (O, M)
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

As with a template graph, r is called the root of the successor graph. It is not Λ, so a template cannot be replaced with Λ.

A rule, R, is a tuple (t, s), where

t is a template graph for H of s
s is a successor graph

Graph t is the rule's template and s is its successor. See Figure 'rule illustration'.

[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 step--comparison and replacement--that 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 is

dissect r into i→{{Λ,Λ}, sib}

which analyzes r and sets variables i and sib. Similarly, a mapping to push on the stack is written as

i→{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 oyt-space 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:

Action Table		j, oyt from subject
Action Table		LL	LΛ	ΛΛ
	LL	tryboth	fail	fail
	LΛ	fail	tryone	fail
	ΛΛ	fail	fail	succeed
	LR	bindtryboth	bindtryone	fail
	ΛR	fail	bindone	bindone
	RR	bindboth	bindboth	bindboth

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₁, r₂}
dissect r₁ into i₁→{{Λ,Λ}, sib₁}
dissect r₂ into i₂→{{Λ,Λ}, sib₂}
push i₁→{a, sib₁}
push i₂→{a, sib₂}
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

Two-Oyts Suffice
     constructing a n-oyt from two-oyts

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, two-oyts 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 many-worlds kerfluffle

Open Questions
     limiting the number of in-links
     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 Λ

Conclusion

This paper has described two-oyts 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 two-oyts.

references

http://acm.uva.es/p/v2/251.html
Non-deterministic Trellis Automata

4 Aug 2006 09:07 PM

Page maintained by Zweibieren two steins of beer