
## Ii. Descriptive And Procedural Models

Currently, the Semantic Web is perceived primarily as a data modeling environment where data is more "descriptive" rather than "procedural" in nature [17]. In other words, the triples in G define a model, not the rules by which that model should evolve. This article will explore the more procedural aspects of G. Figure 1 presents an taxonomy of the various types of triples contained in G, where edges have the semantic "composed of".

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

In its whole, G is composed of nothing but triples.

However, particular subsets of G are used to represent different aspects of the larger G model. Due to RDF,
RDFS, and OWL, G is composed of two main subnetworks: the ontological subnetwork and the instance subnetwork. While, in principle, anything can be modeled by a semantic network, most ontologies and instances are descriptive. However, there is nothing that prevents RDF from being used as a framework for denoting procedural models. That is, G can be used to model functions
(i.e. programs) and the machines that execute those functions.

This article will focus on the procedural aspects of G.

Ontological procedural models represent machine architectures (i.e. abstract machines) and the abstract functions for which they process. On the other hand, instantiated procedures are stored programs (i.e. functions, algorithms, etc.) that are explicitly encoded for virtual machines (i.e. instances of an abstract machine architecture) to execute. The next section will present a formal description of computing.

## Iii. Representing Computations In A One-Dimensional Tape

The classic notion of a computation is any process that can be explicitly represented by a formal algorithm. An algorithm is a sequence of executable, well-defined instructions [19]. This sequence of instructions is executed by some system, or machine. This machine may contain, internal to it, all the requirements necessary to render the results of the algorithm or, in other instances, may rely on some external storage medium to read in novel inputs and write novel outputs. If the former computing model is chosen, then the machine can only execute a single algorithm with no variation on its behavior because no new input is altering its deterministic path
(e.g. 1 + 2 = 3). However, if the latter model is chosen, the machine is general-purpose with respects to the particular "hard-wired" abstract algorithm. It is considered general-purpose because it can map any input to its respective output according to its abstract algorithm
(e.g. x + y = z).

This concept can be taken to its logical conclusion where a single machine can be engineered to perform any computing task. Paradoxically, that single machine executes one and only one algorithm. However, that particular algorithm is so generalized, that it can execute any number of other algorithms represented in the machine's external storage medium. This generalized algorithm can reach the "lowest common denominator" of computing and at that point, can even execute a representation of itself encoded in the storage medium. This machine is called a universal computing machine and is what is know today as the general-purpose computer.

This idea was demonstrated by Alan Turing in the 1930s and is the foundation of the computer sciences [8].

## A. Modeling Computations Using A Turing Machine

Perhaps the most common model used to represent computing is the Turing machine [20]. In the Turing machine model of computation, M is a machine with a single read/write head and D is a storage medium called a "tape" that can be read from and written to by M. A Turing machine can be formalized by the 5-tuple M = hQ, Γ, δ, q0, d0i, where

- Q is a set of machine states,
- Γ is a set of information symbols (e.g. 0,1),
- δ : Q × R → {W(γ), E} × {lf, rt} × Q is the transition/behavior function,
- q0 ∈ Q is the start state of the machine, - and d0 ∈ D is the start location of the machine head on D.
D is a one-dimensional n-length vector of symbols from Γ such that D ∈ Γ
n.

A Turing machine, M, will start at state q0 ∈ Q and cell d0 ∈ D. Depending on what γ ∈ Γ is read (R) at d0, M will use its δ function to determine: 1.) what γ ∈ Γ
to write (W) to d0 or whether to erase (E) the current symbol, 2.) whether to move its read/write head left (lf)