clipka wrote:
> Darren New schrieb:
> 
>> Having the program in hard wiring doesn't make it impossible to be 
>> Turing complete. *That* is what I was arguing.
> 
> If a machine can only be programmed by hard wiring, and none of the hard 
> wiring options implements a capability for soft programming, then it 
> /is/ impossible to be Turing complete. That is what /I/ was arguing.

Fair enough. I was just disputing the version of that without the "none of 
the hard wiring options implements a capability for soft programming" part, 
which is how you seemed to be phrasing it at the start.

>> All I asserted was that "reprogramming requires rewiring" is 
>> orthogonal to "is not Turing complete."  At *some* level of 
>> abstraction, every computer requires rewiring in order to reprogram it.
> 
> You did, as a matter of fact, assert that Colossus could have been 
> hard-wired into a UTM, provided it had enough cables to re-wire.

Yes. Clearly, it needs to have enough hard-wiring operations to be able to 
operate on arbitrary memory and so on. A differential engine isn't going to 
be Turing complete.

> Aside from that: Yes, any soft-programmable machine - including (but not 
> limited to) any such Turing machine - does have a hard-wired programming 
> at its core, so /any/ computing device can be reprogrammed by re-wiring.

That's not what I meant. I meant that at some level of detail, *every* 
computing device must be reprogrammed by re-wiring. If you want a different 
instruction set, you need to change the CPU. If your CPU is microcoded, you 
need to change the CPU to use a different type of microcode. Etc.

> However, if a device's hard-programming does not (and cannot) provide 
> for any means to program it at a non-hardware level, that /is/ contrary 
> to being Turing complete:

All you need is to hard-wire the machine to be a UTM. If you have enough 
read/write storage and a state machine, you're Turing complete. It doesn't 
even take a big state machine. (Something like 3 states with 5 symbols, or 5 
states of 3 colors, or something like that.)

> a UTM, by definition, reads the details of the 
> Turing machine to simulate (viz: the program) from its tape, i.e. the 
> program is part of the data it works on. 

Yes.

> To simulate a UTM, you need to simulate this aspect as well, 

Yes.

> therefore being Turing complete /requires/ 
> the ability to be re-programmable without re-wiring (at least in /some/ 
> wiring configuration).

Certainly not every hard-wired program is Turing complete, if that's what 
you're implying. A hard-wired program to divide two numbers in memory isn't 
going to give you a Turing complete machine. If you hard-wire the machine to 
read the TM state table off the start of the input and follow the rules in 
it, then you have a hard-wired universal turing machine.

Being Turing complete doesn't require the UTM to change its program without 
rewiring, any more than having microcode requires the ability to rewire the 
CPU at runtime.

I think it's just a confusion that you're mixing up too many levels at once. 
A Universal Turing Machine doesn't change its hard-wiring to simulate other 
Turing machines. It gets fed the descriptions of hardware via its inputs, 
but the UTM itself has exactly one program it runs. Put it this way: there's 
nothing that prevents you from building a UTM whose program logic can only 
be read from ROM and not RAM.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message