

![0_image_1.png](0_image_1.png)

It is no large conceptual leap to actually encode SPARQL queries in RDF and therefore, in G. In fact, the semantic network data structure is an ideal medium for many types of information encodings due to its generalized network nature that naturally supports the expression of trees, lists, graphs, tables, etc. The next subsection will discuss such stored programs.

## B. The Stored Program Model

In the stored program model, S
∗is a universal machine that reads its parameter specification from G and writes its algorithm's output to G. Thus, the specification of the δ-function of any S is encoded in G.

One such example of the stored program model is the Semantic Web Rule Language (SWRL). SWRL is a Horn-clause based query/assertion language similar to SPARQL [11]. For example, in the "my friend is your friend" query/assertion

## Hasfriend(?X1, ?X2) ∧ Hasfriend(?X2, ?X3) → Hasfriend(?X1, ?X3)

if ?x1 has a friend ?x2 and ?x2 has a friend ?x3, then ?x1 and ?x3 are asserted to be friends. Interestingly, SWRL
query/assertions can be represented in RDF and thus, can be explicitly encoded in G. The benefit of this is that there can exist a generalized SWRL machine denoted S
∗
that can point to any particular S in G. This idea is depicted in Figure 6, where S
∗is a universal SWRL machine, S is a particular SWRL query/assertion, and GS
is the result of the execution of S. However, note that D
is the computational workspace for S
∗, not G.

While SWRL S
∗is Turing complete [2], it is impractical to represent arithmetic and loop-based algorithms in SWRL. This means that there exists algorithms for which SWRL S
∗can not easily emulate. As a remedy to this problem, two Turing complete S
∗ machines were developed: the stack-based Ripple [17] and the RAMbased r-Fhat [15]. For Ripple and r-Fhat, like SWRL,
their respective programs are encoded in G. However, both Ripple and r-Fhat maintain their respective universal machine data structures in D for computing local

![0_image_0.png](0_image_0.png)

operations and thus, do not completely use G as their computing workspace.

In the stored program model, there not only exists descriptive data in G, but also procedural data. In many cases, there also exists an ontology Sˆ that defines the structure of that procedural data. In general, if a subset of G obeys Sˆ, then it is computable by S
∗. The next subsection will discuss full machine virtualization and the explicit representation of S
∗ ⊂ G.

## C. The Virtualized Machine Model

The previous section discussed the explicit encoding of stored programs in G. However, there is nothing preventing the stored program from being a computing machine.

In this model, a virtual machine is encoded in G along with the programs that the virtual machine executes. In order to represent a virtual machine in G is it necessary to support a write/delete interface to G since the machine evolution and its effect on G is the computation.

Currently, the only example of a virtualized machine encoded in G is the Fhat RVM (RDF virtual machine)
[15]. A Fhat processor, denoted S
∗1exists internal to G.

Another process S
∗external to G is a general-purpose machine that reads S
∗1from G as if it were any other program. However, S
∗1is not only a program, but is another machine that is executing an algorithm, S, in another area of G, GS∗1 . The virtualized machine model is depicted in Figure 7.

![0_image_2.png](0_image_2.png)

There is nothing that prevents the S that S
∗1is executing from being another S
∗. For example, imagine