Database Reference
In-Depth Information
6
Categorial RDB Machines
6.1
Relational Algebra Programs and Computation Systems
The theory of computation has combined a number of elements drawn from quite
different areas: mathematics, linguistics, biology, electrical engineering and, of
course, computer science. Turing attempted to precisely formalize the first
abstract
model of computation
by using the notion of an effective procedure, or algorithm.
His approach was to identify the fundamental, primitive operations involved in the
process to solve some problem, and to define an
abstract machine
capable of per-
forming those operations according to a clearly specifiable
program
. It is not possi-
ble to prove that a particular mathematical definition is a correct formulation of an
intuitive idea like that of computation; but it is possible to compare one mathemati-
cal definition with another (as it will be done in what follows). Turing machines are
not the only abstract models of computation. A number of other researchers have
attempted to capture in a mathematical definition the nature of computation. More
general definitions [
1
] for these concepts are as follows:
A
computation machine
M
(D. Scott, 1967) is a four-tuple
M
=
(S
M
, Oper, Te s t, In
M
, Out
M
),
where:
1.
S
M
is a set of memory-states;
2.
Oper
is a set of operators (functions)
f
:
S
M
→
S
M
(elementary operations of
machine);
3.
Te s t
is a set of test-functions
f
:
S
M
→{
0
,
1
}
;
4.
In
M
is an input function
In
M
:
INP
0
→
S
M
, where
INP
0
is a set of all input
values;
5.
Out
M
is an output function
Out
M
:
S
M
→
OUT
, where
OUT
is a set of all output
values.
A
program
P for a machine
M
is a finite set of instructions, where two different
instructions have two different addresses. The syntax of each instruction is either:
1. A triple
(i,f,j)
, where
i
is its address,
j
is the address of the next instruction
and
f
∈
Oper
;or
