|
![](/i/fill.gif) |
Darren New schrieb:
> clipka wrote:
>> - Even its 1943 successor, "Colossus", was not Turing-complete, and
>> programmable only by re-wiring.
>
> Just to avoid confusion, everyone should be aware that Turing machines
> are programmable only by re-wiring. Those two clauses have nothing to do
> with each other. :-)
To the contrary, they have a /lot/ to do with each other.
While it is true that the theoretical construct known as a "Turing
machine" is "hard-wired" by definition, this is not necessarily the case
for a system /simulating/ such a machine. (Actually building a true
Turing machine is outright impossible, as it requires an infinitely long
memory tape, so a simulation is the closest you can get anyway.)
In fact, such a system to simulate a Turing machine may even be another
Turing machine, designed for the purpose of simulating any of a whole
/class/ of Turing machines, the exact details of which would be read
from the initial data on the tape. While the simulating Turing machine
would still by definition be hard-wired regarding its own operation, it
would be programmable regarding the simulated machine.
This can be pushed even so far as to design a Turing machine that would
be capable of simulating /any/ possible Turing machine (including itself
if required): A "Universal Turing machine". (Again, actually building
such a thing s impossible, but only for the same reason as is building
any other Turing machine.)
Now stating that a machine is "Turing-complete" is equivalent to saying
that it is capable of simulating not just /some/ Turing machine, but a
/Universal/ Turing machine - which by definition /is/ fully programmable
regarding the simulated Turing machine.
Therefore, a machine programmable only by re-wiring /cannot/, by
definition, be Turing-complete.
Post a reply to this message
|
![](/i/fill.gif) |