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 );
Search WWH ::




Custom Search