Information Technology Reference
In-Depth Information
auto-referential sentence, that is a form of a diagonal construction, related to Can-
tor's proof of non-enumerability of real numbers (and also to Russell's paradox). In
the proof sketched above the diagonal argument is implicit in the Turing's construc-
tion of the language
K
(directly suggested by Cantor's diagonal argument).
First-order logic connects arithmetic, computability, and formal language the-
ory [188, 204]. Many logical limitations are due to computational aspects, and at
same time, many limitations of calculi are of logical nature. Analogously, deduction
of consequences by means of a logical calculus is a special case of computation,
but at same time any computation can be represented in terms of suitable logical
deductions. Finally, any FOL (First-Order Logic) theory can be interpreted in mod-
els having natural numbers as domain. These facts show that arithmetic, logic, and
computation are fields strongly connected.
6.7
Register Machines
Register machines are computation systems strictly related to Turing machines.
They have a structure similar to the central unit of von Neumann's architecture, rep-
resenting the general schema of a stored-program electronic computers, designed
in the EDVAC (Electronic Digital Variables Automatic Computer) draft of 1945
[207, 194]. The constitutive element of EDVAC project is the electronic valve and
its analogy with the neuron, according to McCulloch and Pitts' formalization [9].
The document by von Neumann provides the constitutive principles of a universal
electronic computer; however, a systematic analysis of electronic circuits, in terms
of boolean operations, was developed afterwards, on the basis on researches of Emil
Post and Claude Shannon, in the years between 1930 and 1945. Register machines
are computationally universal: for any Turing machine
M
there exists a register ma-
chine performing the same computations of
M
(by a suitable encoding of data of
M
as natural numbers).
Consider the cells of a Turing machine tape and, instead of arrange them linearly,
associate to each of them an
address
expressed by a number or by a label. Moreover,
instead of put in these cells symbols, assume to put in them numbers (if any num-
ber can occur, then the size of cells is unbounded). In a register machine, instead of
moving along the cells, it is possible to apply a set of operations to the numbers con-
tained in a cell, called
register
, by specifying the cell address. A register machine
performs a computation according an internal
program
which is constituted by a
sequence of
instructions
. Each instruction has three components: i) an order num-
ber, ii) an operation referred to registers, and iii) the number (or two numbers where
only one is chosen) which has to be put in the (instruction) counter
C
. This num-
ber establishes the next instruction to execute. In fact, at each computation step, the
machine executes the instruction having the order number contained in the counter.
At the beginning of the computation, the counter contains the number of the first
instruction to be executed. When the counter
C
contains a number which is not the
number of an instruction of the program, then the computation stops. The instruc-
tions, with the related operations, are given in Table 6.16, where
R
i
,
R
j
denote two
