model can be used for writing triples that bind symbols in a list-like fashion. In other words, a semantic network can simulate a one-dimensional tape. In this model, the semantic Turing machine utilizes only G for its workspace computations and the semantic Turing machine is analogous in terms of its component parts to the classic Turing machine. The δ-function to increment a unary number by 1 is

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

where the URI bit1 is the subject of the triple whose object is the first bit of the unary number. While it is possible to perform low-level arithmetic calculations in G, constructing such a machine is impractical. Unlike a physical M where the laws of physics are the computing substrate, Ss are embedded in a substrate that was engineered for computing–the general-purpose processor. Thus, an S can rely on its local processor for arithmetic computations and for the construction of new URIs and literals. What was presented previous was only to demonstrate that G can be used as a universal computing "tape". However, how much of computing is represented in G is implementation specific, but the more a computation is represented in G, the more the Semantic Web can be made to behave like a general-purpose computer.

Finally, it is possible to represent the previous two δfunctions in G such that some S
∗external to G is able to simulate the behavior of these respective S machines. In this sense, S
∗is a universal semantic Turing machine and any S ⊂ G that obeys the Sˆ ontology can be executed by S
∗. The next section will discuss moving computations into G to ultimately arrive at a general-purpose computer embedded in G–a semantic virtual machine.

## V. The Semantic Web As A General-Purpose Computer

The current state of the Semantic Web is such that machines (i.e. processes) exist external to G and manipulate G by reading, writing, and deleting triples to and from it. In many cases, G does not encode stored programs in the Turing sense. Those processes that manipulate G use some other D-medium (e.g. local memory)
for their respective calculations. However, by leveraging external D-mediums that are not G, there exist multiple machines (i.e. software programs) that do very specific computing tasks. This is analogous to having different physical Ms for each desired computing task. On the other hand, when G is leveraged as the sole substrate for encoding information, then it is possible to not only use G for stored programs, but also to use G to represent a universal computing machine [15]. The benefit of this latter model is that the Semantic Web becomes a universal computing platform, where any number of universal computing machines exist external to G executing the state evolution of those G encoded machines. At this stage, G is a massive computer distributed across servers world-wide.

The remainder of this section will present the various levels of machine encodings currently realized by the Semantic Web community. The first is the "external program" level where S machines are external processes whose stored programs are represented in some other Dmedium. The second level is the "stored program" level where S machines are external process whose stored programs are represented in G. The final level is called the
"virtualized machine" level where S machines are internal processes represented in G whose stored programs are also represented in G.

## A. The External Program Model

In the external program model, the Semantic Web is considered a database. The machines (i.e. programs) developed for G exist external to G and only use G for reading descriptive data (and possibly writing descriptive data). This is analogous to the physical manifestation of an algorithm in the Turing model of computing. While it is possible for S to be completely configurable and thus, not "hard coded", this δ-function is stored in a separate D-medium where G ∩ D = ∅. Therefore, with respects to G as a general computing platform, this model is the farthest removed from this vision.

One such example of the external program model is the SPARQL query language [14]. The SPARQL query language is a Horn-based [10] query language that supports semantic searching in G. For instance, the following example SPARQL query

## Select ?X Where { Marko Isa ?X . }

will bind ?x to all URIs that are the object of a triple that has marko as the subject and isA as the predicate. While a universal SPARQL machine, denoted S
∗, can execute any SPARQL-proper query, these queries (i.e. programs)
are not explicitly represented in G, but instead in some D. Thus, with respects to G, each SPARQL query is analogous to a unique S. Furthermore, the output from any S is encoded in D (more specifically DS). In this sense, G is only used as the input parameter to S, not as a computational "workspace". This computing model is diagrammed in Figure 5, where S
∗is the universal SPARQL machine, S is a particular SPARQL query, and