Aiserman M., Gusev L., Rozonoer L., Smirnova l., Tal A. Logic, Automata, and Algorithms
Подождите немного. Документ загружается.
350
ELEMENTS
OF
MATHEMATICAL LOGIC
systems
E
which define general recursive functions
is
algorithmic-
ally
unsolvable. The set of general recursive functions turns out
to be countable, but not effectively
so.
Example
2.
The following problem turns out to be algorithmically
unsolvable:
it
is
required to find an algorithm for recognizing, for
any primitive recursive function
~(x,
y)
[or
for any primitive recur-
sive predicate
T(x,
y)]
whether
that
function has the property
or
in the
case
of
a
predicate, whether
(Vx)(xy)
T(x,
y)].
Since primitive recursive functions can be effectively and
dis-
tinctively labeled (numbered), the problem reduces to finding
a
computable function
+(r)
such that:
=O
if
r
is
the number of
a
primitive
+(r)
<
recursive function having the
1
property
(12.32).
,
>
0
in
all
other
cases.
This function proved not to be general recursive and, conse-
quently,
is
noncomputable.
Even
if
condition
(12.32)
is
somewhat weakened, the problem
is
still algorithmically unsolvable. Thus the following simple problem
is
algorithmically unsolvable: given
a
primitive recursive function
q(x,
g)
it
is
required to find, for any
x*,
whether the following con-
dition holds for that
x":
PY)
IT
(x**
Y)
=
01.
Yet
another algorithmically unsolvable problem
is
this: for any
primitive recursive predicate
P(y)
,
it
is
required to find whether
it
is
true that
In all
cases,
the
proof reduces toproving that the corresponding
recognition function
is
not general recursive.
One often proves the algorithmic unsolvability of
a
given prob-
lem by showing that it reduces to anotherproblem, whose algorith-
mic unsolvability has already been proved. Sometimes
it
suffices
to show that
a
narrower problem,
which
is
a
special
case
of the given
problem,
is
algorithmically unsolvable.
In Chapters
8
and
9,
we
used the method in proving algorithmic unsolvability of the
two
basic
problems of the theory of finite automata and sequential machines.
RECURSIVE REAL
NUMBERS
35
1
12.12.
RECURSIVE
REAL
NUMBERS
Recursive real numbers occur in
cons&ucCive
mathematics, an
approach which has developed from the desire to avoid getting en-
trapped in logical contradictions (antinomies). In
this
approach, a
proof
is
considered complete if, inaddition toestablishing a mathe-
matical fact, one
is
able to demonstrate that the corresponding
mathematical objects can
also
be computed.
The machinery of recursive functions plays
an
important role
in constructive mathematics: it
is
in terms of these functions that
the
algorithms for effective construction of required objects
are
usually defined.
Consider
a
typical constructive formulation of a frequent prac-
tical problem. In analysis one often comes across the statement
“for every small
E
>
0
there exists
a
number
A’
such that some
quantity (which
is
afunction ofn) becomes smaller than
E
for
n
>,
N.”
Now, what
is
the constructive variant of this statement? In order to
arrive at it,
we
require:
1.
A
more precise definition of what
we
understand by “every
small
E.”
To define such
E,
we may assume, for example,
E
=
;,
where
rn
is
a positive integer which maybe
as
large as
desired.
2.
An
effective method for determining
N
,
starting from
E
(that
is,
from
m).
Therefore, an effective formulation of the above statement
is:
“there
exists
a
general recursive function
v
(m)
such that some
quantity
which
is
a function of
n
becomes smaller thanmfor
n
>v(m)
.”
This kind of formulation can
be
related to convergence of
a
se-
quence of rational numbers. Let us
say
that a sequence of rational
numbers
a,,
a,,
a,,
...,
a,,
...
is
recursive
if
there exist general
recursive functions
a(n),
p(n)
[where
‘t
>,
11
such that
1
1
a
(4
-
P
(4
r(n)
*
a,
=
We
shall
say
that the
sequence converges recursively
(or
ef-
fectively)
if
there exists a-general recursive function
v
(m)
such that
for any arbitrarily large
m
>
0,
The number
r,
defined by this effectively convergent sequence,
is
called
a recursive real number.
It can be shown that the recursivity
of
r
(that
is,
the fact that
there
exists
a
sequence of rational numbers which, in
the
limit,
recursively approaches
Y)
does not imply that
Y
can be expanded
352 ELEMENTS OF MATHEMATICAL LOGIC
into a recursive decimal fraction. That is, the recursivity does not
imply
the
existence of a general recursive function
$(n)
<9
such
that
co
y9(k)
’=A
10k
However, there exists one special sequence whose recursive con-
vergence implies
the
possibility of recursive expansion of
r
in any
number systems.
This
is
the factorial expansion
k=O
where
u,
ti
-
1
for
large
n.
If
there exists
a
general recursive
function
x(n)
such that
a,
=
x(n),
this
series
always converges
re-
cursively and defines a recursive
real
number, which can
be
ex-
panded into
a
recursive fraction in any number system.
Let
us
also mention
here
that the setof recursive
real
numbers
is
not larger than
the
set
of general recursive functions; that
is,
this set
is
not larger than
a
countable set, whereas the set of
all
real numbers
is
a
continuum. In this sense, only
a
very small
frac-
tion
of
all
real
numbers
are
recursive.
To
summarize,
a
recursive
real
number
is
really
a
number
which may be computed
to
any degree of accuracy by means
of
an
algorithm.
All
numbers usually employed in mathematical analysis
(e,
IT,
fl,
and
so
on)
are
recursive
real
numbers.
12.13.
RECURSIVELY ENUMERABLE AND
R ECU RSlVE SETS
There
are
several equivalent formulations defining recursive
and recursively enumerable
sets
of
integers.
For
convenience,
we
shall assemble these definitions into
a
table:
Recursive
sets
of numbers
1
Recursively enumerable sets of
numbers
1A.
A set
is
said to be recursively enu-
merable
if
it
consists of values of some
general
recursive
function
if,
alterna-
tively,
if
there exists a general
recur-
sive function enumerating it, even ifthis
involves repetitions. The empty set
is
deemed to be recursivelyenumerable.
2A.
A
set
C
containing at least one
ele-
ment
is
recursively enumerable
if
and
only
if
the predicate
“veC”
can be ex-
pressed in the form
(<x)P(x,y).
where
P
(x,
y)
is
general recursive.
16.
A
set
C
is
said to be recursive if
there exists an algorithm for determining
whether a given number
y
belongs to
C.
26.
A
set
C
is
said toberecursiveif the
predicate
“yeC”
can be expressedinthe
form
P
(y),
where
P
is
general recursive.
36.
A
set
C
is
said to be recursive if both
the set and its complement
c
arerecur-
sively enumerable.
46.
An infinite set
C
is
recursive
if
and
only
if
it can be enumerated byageneral
recursive function without repetition and
in increasing order of its elements [that
is
if
q(O),
~(l),
q(2),
.
.
.
give the
ele-
ments
of
C
in increasing order].
RECURSIVELY ENUMERABLE AND RECURSIVE SETS
353
Now,
a
few
remarks regarding these definitions:
Note
on
U.
It
has
been proved that,
if
a
set can be enumerated
be
a
general recursive function with repetition, it can also be
enumerated without repetition (by another general recursive func-
tion).
Note
on
2%.
We
shall show that definition
2A
follows from
1A.
Let
C
be the
set
of values of
a
general recursive function
cp(x).
Then,
the
fact
that
a
number
y
belongs to
C
means
that
there
exists
an
x
such that
y
=
'9
(4,
(34
Is
=
'9
(41.
or
that
Equation
y
=
cp(x)
may
be
regarded
as
a
general recursive relation-
ship of equality between two general recursive functions
P(x,
Y)=lxl(x7 Y)=xz(x7 Y)l>
XI@?
Y)"Y,
X2(X.
Y)=Y(X).
where
Note
on
2B.
Definition
2B
is
merely
a
more exact version of
definition
1B.
Note
on
3B.
If condition
3B
is
satisfied, thenit follows that con-
dition
1B
is
also satisfied. Indeed, let
C
be enumerated by function
cpl
(x),
and
set
by the function
~(x).
To ascertain whether
a
given
number belongs to
C,
we
shall compute the parallel sequences
Since
y
belongs either to
C
or to
c,
sooner or
later
it
will
appear
either in row I or in row 11.
If
it
appears in row I, then
y
C
,
and
if
in row 11, then
y
E
c.
Thus, there
exists
an algorithm for deter-
mining whether any
y
belongs to
C.
Note
on
4B.
When condition
4B
holds,
there
also
exists
an
al-
gorithm for recognizing the membership of any
y
in set
C.
Indeed,
let us compute the sequence
q(0),
q(
I),
cp(2).
.
.
..
If,
at
some
n,
we
arrive
at
~(n)
>
y
,
then
there
is
no need to continue
the
computation,
and
we
may conclude that
y
E.
C;
if,
however,
we
find
rn
x
n
such that
cp(rn)
=
y,
then
y
EC.
We
shall give
a
few
examples of recursive
sets:
1)
The two-element set
(0,
I}
is
recursive by virtue of condi-
tion
1B
or
2B.
354
ELEMENTS
OF
MATHEMATICAL
LOGIC
2)
Any finite set
is
recursive by virtue
of
condition
1B
or
2B.
3)
The
set
of even numbers
{O,
2,
4,
6,
8,
.
.)
is
recursive.
Here
y
E
C
=
[ITS
(y,
2)
=
01,
and the
set
is
recursive by virtue of
2B;
or
q(x)
=
2x,
and the set
is
recursive by virtue of
4B.
Now, let us give examples of sets that
are
and sets that
are
not
recursively enumerable.
According to definition
2A,
the
set
of
all
y
for
which
(ax)P(x,
g)
at some general recursive
P(x,
g)
is
recursively enumerable. One
can
so
select
P
(x,
g)
that the set
{g}
will
be recursively enumerable,
but not recursive; its complement
{i)
will
be the set of those
y
for
which
(2x1
P
(x,
Y)
=
(v4
(x,
Y)
=
(vx)
Q
(x,
y)
(where
Q
is
a
general recursive predicate); this set
{i}
will
be
neither recursive nor recursively enumerable,
The set
of
Gb’del numbers
z
of
systems
E
which define
a
general
recursive function
is
neither recursive nor recursively enumerable.
In conclusion, let
us
point out that the comparison of
1A
and
4B,
as
well
as
the fact that any finite
set
is
both recursive and recur-
sively enumerable imply that any recursive
set
is
recursively
enumerable. The converse, however,
is
not true.
The concept of recursive real numbers and recursively enu-
merable sets
is
important in determining whether
a
machine “can
do” more than just realize
a
given algorithm.
For
we
have shown
above that any algorithm reduces to the computation of the values of
a
computable integer function.
Thus,
if
a
device generates an output
of
a
set of numbers and that set
is
not recursively enumerable, we
immediately know that the operation
of
this device cannot be repre-
sented
by
an algorithm; that is, this device ‘‘does more” than just
realize an algovithm
13
Turing
Machines
13.1.
DESCRIPTION AND EXAMPLES
OF
TURING MACHINES
In Chapter
12
we
showed that the fundamental, intuitively obvious
requirements to which any algorithm must conform
are
those of
determinacy, generality, and applicability (efficacy). In addition, the
result of an algorithmic procedure must be completely independent
of the person executingit. Theexecutor merely acts
like
a
machine:
there
is
no “creative” work involved here, because the executor
needs only
to
follow instructions. If
this
is
so,
then why not dele-
gate the execution of the algorithm to amachine? This chapter
will
present one
class
of machines capable
of
executingsuch tasks.
The above properties
of
an algorithm also pertain to
a
machine
executing this algorithm.
To
begin with,
such
a
machine must be
fully determinate, operating within the specified rules. Second, it
must allow the input of
a
variety of “initial data,” that
is,
of
a
variety of individual problems from
a
given class of problems.
Third, the specified operational rules for the machine and the
class
of problems
which
can
be
solvedmustbe matched in such
a
way
that
the result of machine operation will always be ‘‘readable’
’
(that is,
the machine
will
give
a
useful result).
There
are
many constants capable of executing algorithms. The
most graphic of these
is
the scheme proposedin
1936
by the English
mathematician Turing.
We
shall now describe one of the possible
variants
of
this machine.
The
basic
component of our Turing machine
is
an infinitely long
tape divided lengthwise into squares. The tape extends in only one
direction (to the right),
so
that
we
can meaningfully talk about
a
“leftmost” square. Each square may contain only one symbol
s;
from
a
finite
alphabet
[so,
.
.
.,
s,].
We
shall ascribe
a
special
sig-
nificance to the symbol
SO:
its
presence in
a
square shall denote
that the square
is
blank. In any tape, the number of nonblank squares
is
always finite (but
as
large
as
desired),
all
the other squares be-
ing blank.
355
356
ELEMENTS
OF
MATHEMATICAL LOGIC
The second component of the Turing machine
is
aread-erase-
recovd head. This
special device can move along the tape, either
to the left
or
to the right, one square at
a
time. Upon an external
command, the
head
can
erase
a
symbol present in the tape square
that happens to face the
head
at
a
given moment, and it can print
another one in
its
stead.
The external commandscausing these
ac-
tions
are
issued by a controller,
a
device
which
is
itself governed
by the signals generated by the head
(these
signals indicate the
presence of symbols
s,
in
a
given tape square). The controller
operates in discrete time
t
=
0,
1,
2,
.
.
.
,
and
it
may assume
a
finite
number
rn
+
1
of internal
states
40,
. .
.,
q,,,.
Its input consists of sym-
bols of
s,
read and generated by the head, while
its
output consists
of commands to the head (these commands indicate what symbol,
if
any, should be printed in
a
given tape square, as well
as
the direction
of
motion of the head).
For
example, assume that at time
t
the head
faces the
lth
square from the left, that this square contains the sym-
bol
s,,
and that the controller
is
in state
q3.
The head reads the sym-
bol
sz
andgenerates
a
signal correspondingtoit. In response to this,
the
controller generates a symbol
sk
whichcauses
the head to
erase
the old symbol
s,
and print
sk
on the tape. Then
the
controller pro-
duces one of the symbols
R,
L,
S
(‘‘right,” “left,” “stop”), in
compliance with which the head moves one square to the right
or
left
or
stays put. After this, the controller assumes
a
new state
qr,
which
is
uniquely determined by the previous state
q1
and the signal
s,.
After the entire operation has beencompleted(at time
t
+
l),
the
lth square contains
the
symbol
&,
the controller
is
in
state
q.,
and
the
head
is
situated opposite either the
(I
+
l)st, the
(I
-
l)st,
or
the
lth square (depending on whether the motion commandwas
R,
L,
or
S).
Thus, the controller
is
a
sequential machine
with
two
output
converters.
Its
inputs
are
symbols from
the
alphabet
{SO,
.
.
.,
sn},
received from the read-record head. Its states
are
symbols from
the alphabet
(4”.
.
.
.
,
q,,l}.
Its
first
output
is
a
signal commanding the
head
to print
a
symbol from the alphabet
(so,
.
. .
,
s,]
,
whereas
its
second output
is
a
signal commanding
a
shift of the head and belong-
ing to the alphabet
{R,
L,
s}.
Theoperation of this s-machine can
be specified by means of three tables-those for an automaton and
for
two
converters. However, it
is
customary to combine these into
one basic table. Thus the automaton Table
13.1,
the
first
converter
Table
13.2,
and the second converter Table
13.3
may
all
be com-
bined, in that order, into Table
13.4,
whichfully describes the opera-
tion of this Turing machine. Again,
if
the basic table of
a
Turing
machine
is
given, then
its
operation
is
uniquely specified.
DESCRIPTION AND EXAMPLES
OF TURING
MACHINES
357
Table
13.1
Table
13.2
Table
13.3
m,
40
40
Table
13.4
State of the controller
shall
denote the
rest
state
of the Turing
machine; that
is,
row
qfl
of the basic table has the following proper-
ties:
(1)
The first symbol in every square
of
this row
shall
always
be
qo
(never
qj
if
j
#
0);
(2)
The second symbol of each square
will
be
si,
the same symbol
as
in the respective
column
heading (never
sk
if
k
-A
i);
(3)
The third symbol of every square shall
be
the sym-
bol
S
(never
R
or
I,).
For
anillustration of row
qfl,
see
Tables
13.4
and
13.5.
Table
13.5
Now,
if
the controller
is
at any time
t
in state
qfl,
then whatever
the position of the head, andwhatever the symbol in the correspond-
ing tape square, the controlling device
will
remain in state
40,
the
head
will
not move, and the tape entries
will
remain the same
as
be-
fore.
To
simplify
the
basic table,
we
shall therefore omit row
qo
(see
Table
13.6).
For simplicity,
we
shall also assume that the alphabet
(si]
con-
sists
of
only
two
symbols; blank (that is,
0)
and nonblank (that
is,
1).
358
Time
0
1
ELEMENTS
OF
MATHEMATICAL LOGIC
~
Tape printout
41
(1
I
. . .
10701
,
.
.
. . .
lor01
.
.
.
Table 13.6 Table 13.7
Machine
A
Now let us discuss
a
few
simple Turing machines.
1)
Machine
A
(Table 13.7). This machine operates
as
follows.
Assume that at
t
=
0
,
the controller
is
in state
ql,
and the head
faces
a
nonblank square. The machine then “looks”
for
the
first
blank
square to the right, prints the symbol
1
in it, and stops.
If,
how-
ever, the head
faces
a
blank square
at
t
=
0,
then the machine prints
1
in that square, and stops (no motionof the head). Tables 13.8 and
13.9 illustrate
two
possible modes of operation
of
this machine.
(A
bar above
a
tape square indicates that the head
faces
that square
Table
13.8
Table 13.9
DESCRIPTION AND EXAMPLES
OF
TURING MACHINES
359
the symbols are known to remain un-
time considered (the head does not
changed throughout the operating
0
1
,
41
410L
qoo
L
Table 13.11
3)
Machine
C
(Table 13.12).
At
t
=O,
this machine may
face
either
a
blank or a nonblank square. The head then moves to the
right until it finds the first group of symbols
1
after a group
of
Table 13.12
Machine
C