Database Reference
In-Depth Information
where
z
S
M
and
λ
is
the abstraction operator (i.e., currying) of the
λ
-calculus such that
λIn
∗
E
(z)(st)
∈
INP
is the input value taken by
MI
in this current state
st
∈
=
I
E
(z, st)
,
(i, st),
j,f(st)
∈→
P
∈
if
(i,f,j)
P,
(i, st),(j, st)
∈→
P
if
(i,t,j,k)
∈
P
and
t(sk)
=
1
,
(i, st),(k, st)
∈→
P
if
(i,t,j,k)
∈
P
and
t(sk)
=
0
;
2.
In
S
(x)
=
(
0
, In
M
(x))
;
3.
Out
S
(i, st)
=
Out
M
(st)
;
4.
Stop
S
:
S
P
→{
}
=
0
,
1
is a total stop-criteria function such that
Stop
S
(i, st)
0if
i
is not an address of any instruction of P.
Given any global program input value
z
(j, In
∗
E
(z
k
)(st))
={
z
k
|
∈→
P
}∪{
z
0
}
,
z
0
∈
INP
0
, the result of a computation is
Res
M
(z)
=
Out
S
◦
(
→
P
)
Stop
S
◦
In
S
(z
0
)
, where
(
→
P
with respect to the
Stop
S
.Thesetofall
MI
-computable functions is defined by
F(
MI
)
→
P
)
Stop
S
denotes the iteration of
={
Res
M
|
P
is a program of
MI
}
.
L
P
to provide “com-
putational completeness”, i.e., it should be capable of computing all computable
functions. The machine able to execute such programs has to be universal: the class
of all computable functions on such machines has to be equal to
F
μ
(the class of all
μ
-recursive, partial recursive functions, defined inductively by Kleene (1936)). The
Turing machine is the most well-known universal machine (
M
U
). Some of other
abstract models for universal machines resemble modern computers more closely
in their details. The Register machine
RM
of Minsky (1961) is a good example for
such a consideration, and hence will be generalized by an input-extension for our
purposes:
It is desirable for a general-purpose programming language
Definition 38
A input-extended register machine
RMI
is a 6-tuple
RMI
=
(S
U
, Oper
U
, Te s t
U
, In
U
, In
EU
, Out
U
),
where
•
S
U
is a set of memory-states of
n
2 registers
x
=
(x
1
,x
2
,...,x
n
)
;
Oper
U
=
1
≤
i
≤
n
{
•
a
i
,s
i
}
, with
a
i
(x
1
,...,x
i
,...,x
n
)
=
(x
1
,...,x
i
+
1
,...,x
n
)
(x
1
,...,x
i
,...,x
n
)
if
x
i
=
0
;
and
s
i
(x
1
,...,x
i
,...,x
n
)
=
1
,...,x
n
)
if
x
i
>
0
;
(x
1
,...,x
i
−
•
Te s t
U
={
t
i
|
i
=
1
,
2
,...,n
}
such that
t
i
(x
1
,...,x
i
,...,x
n
)
=
1iff
x
i
=
0;
•
In
U
is an initial-input function
In
U
:
INP
0
→
S
U
, where
INP
0
is a set of all
initial-input values;
•
In
EU
is an (partial) input function
In
EU
:
INP
×
S
U
→
S
U
, where
INP
is a set of
all input values
z
∈
INP
,
z
={
z
1
,...,z
k
}
,1
≤
k
≤
n
, and
In
EU
(z,x)
=
y
, where
y
i
=
x
i
or
y
i
∈{
z
1
,...,z
k
}
,1
≤
i
≤
n
(i.e., it changes a subset of registers by the
input value
z
);