Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: Can machine think? -------by Alan Turing(3)
发信站: 哈工大紫丁香 (2001年06月14日15:56:01 星期四), 站内信件

5 Universality of Digital Computers
The digital computers considered in the last section may be classified amongst
the 'discrete state machines' these are the machines which move by sudden jumps
or clicks from one quite definite state to another. These states are
sufficiently different for the possibility of confusion between them to be
ignored. Strictly speaking there are no such machines. Everything really moves
continuously. But there are many kinds of machine, which can profitably be
thought of as being discrete state machines. For instance in considering the
switches for a lighting system it is a convenient fiction that each switch must
be definitely on or definitely off. There must be intermediate positions, but
for most purposes we can forget about them. As an example of a discrete state
machine we might consider a wheel which clicks {p.440} round through 120?once a
second, but may be stopped by a lever which can be operated from outside; in
addition a lamp is to light in one of the positions of the wheel. This machine
could be described abstractly as follows. The internal state of the machine
(which is described by the position of the wheel) may be q1, q2 or q3. There is
an input signal i0 or i1 (position of lever). The internal state at any moment
is determined by the last state and input signal according to the table
        Last State
        q1 ….. q2….. q3
       i0q2….. q3….. q1
      Input .
       i1q1 ….. q2….. q3

The output signals, the only externally visible indication of the internal st
ate
(the light), are described by the table
      Stateq1 ….. q2….. q3
      Outputo0 ….. o0….. o1
This example is typical of discrete state machines. They can be described by
such tables provided they have only a finite number of possible states.
It will seem that given the initial state of the machine and the input signals
it is always possible to predict all future states. This is reminiscent of
Laplace's view that from the complete state of the universe at one moment of
time, as described by the positions and velocities of all particles, it should
be possible to predict all future states. The prediction which we are
considering is, however, rather nearer to practicability than that considered
 by
Laplace. The system of the 'universe as a whole' is such that quite small err
ors
in the initial conditions can have an overwhelming effect at a later time. The
displacement of a single electron by a billionth of a centimetre at one moment
might make the difference between a man being killed by an avalanche a year
later, or escaping. It is an essential property of the mechanical systems which
we have called 'discrete state machines' that this phenomenon does not occur.
Even when we consider the actual physical machines instead of the idealised
machines, reasonably accurate knowledge of the state at one moment yields
reasonably accurate knowledge any number of steps later.
{p.441} As we have mentioned, digital computers fall within the class of
discrete state machines. But the number of states of which such a machine is
capable is usually enormously large. For instance, the number for the machine
now working at Manchester it about 2165,000, i.e. about 1050,000. Compare this
with our example of the clicking wheel described above, which had three states.
It is not difficult to see why the number of states should be so immense. The
computer includes a store corresponding to the paper used by a human computer.
It must be possible to write into the store any one of the combinations of
symbols which might have been written on the paper. For simplicity suppose that
only digits from 0 to 9 are used as symbols. Variations in handwriting are
ignored. Suppose the computer is allowed 100 sheets of paper each containing 50
lines each with room for 30 digits. Then the number of states is 10100x50x30,
i.e. 10150,000. This is about the number of states of three Manchester machines
put together. The logarithm to the base two of the number of states is usually
called the 'storage capacity' of the machine. Thus the Manchester machine has a
storage capacity of about 165,000 and the wheel machine of our example about
1?. If two machines are put together their capacities must be added to obtain
the capacity of the resultant machine. This leads to the possibility of
statements such as 'The Manchester machine contains 64 magnetic tracks each w
ith
a capacity of 2560, eight electronic tubes with a capacity of 1280.
Miscellaneous storage amounts to about 300 making a total of 174,380.'
Given the table corresponding to a discrete state machine it is possible to
predict what it will do. There is no reason why this calculation should not be
carried out by means of a digital computer. Provided it could be carried out
sufficiently quickly the digital computer could mimic the behaviour of any
discrete state machine. The imitation game could then be played with the mach
ine
in question (as B) and the mimicking digital computer (as A) and the
interrogator would be unable to distinguish them. Of course the digital compu
ter
must have an adequate storage capacity as well as working sufficiently fast.
Moreover, it must be programmed afresh for each new machine which it is desired
to mimic.
This special property of digital computers, that they can mimic any discrete
state machine, is described by saying that they are universal machines. The
existence of machines with this property has the important consequence that,
considerations of speed apart, it is unnecessary to design various new machines
to do various computing processes. They can all be {p.442} done with one digi
tal
computer, suitably programmed for each case. It will be seen that as a
consequence of this all digital computers are in a sense equivalent.
We may now consider again the point raised at the end of ?. It was suggested
tentatively that the question, 'Can machines think?' should be replaced by 'Are
there imaginable digital computers which would do well in the imitation game?'
If we wish we can make this superficially more general and ask 'Are there
discrete state machines which would do well?' But in view of the universality
property we see that either of these questions is equivalent to this, 'Let us
fix our attention on one particular digital computer C. Is it true that by
modifying this computer to have an adequate storage, suitably increasing its
speed of action, and providing it with an appropriate programme, C can be made
to play satisfactorily the part of A in the imitation game, the part of B being
taken by a man?'

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]