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