Darren New schrieb:

>> 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.

What I mean is that at every computing device /can/ be reprogrammed by 
re-wiring; but note that this is no /must/: I can happily live without 
re-wiring my Intel i7 machine, knowing that it is /pre-wired/ to be 
Turing-complete already :-) (within memory constraints of course).

>> 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.

And here's where I need to repeat myself: There are machines you 
/cannot/ possibly hard-wire to be a UTM.

/If/ a machine can be hard-wired that way, then this /implies/ (and 
therefore also, in terms of logic, /requires/) that the device /can/ 
provide for a means to program it at a non-hardware level - because that 
is a key feature of /any/ UTM.

So I repeat again: If a device's hard-programming /can not/ provide for 
any means to program it at a non-hardware level (even with the most 
clever hard-wiring option), that /is/ contrary to being Turing complete.

 > 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.

Well, what this gives you is no more and no less than /a universal 
Turing machine/, which /by definition/ of a Turing machine is hard-wired.

And by virtue of being a UTM, it is automatically "soft-programmable" as 
well.


> 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.

A UTM is /always/ Turing complete by definition. And while it doesn't 
require its /own/ program to be modifiable without re-wiring, it 
/implies/ that the program /to simulate/ be modifiable without.

Therefore, to be Turing complete by definition /implies/ (and therefore, 
in terms of logic, /requires/) that the machine - whether it be an 
actual UTM or some other device capable of simulating a UTM - be 
re-programmable without re-wiring at /some/ level.

> I think it's just a confusion that you're mixing up too many levels at 
> once.

No, I'm pretty sure I'm not mixing them up. Though you may not be aware 
of the fact that my initial argument covers /all/ those levels.

 > 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.

There is, however, no way to build a UTM that, at /every/ level, can 
read program logic from ROM /only/.

It must be "soft-programmable" at /some/ level in order to qualify as 
Turing-complete.

Therefore, I repeat my initial argument: A machine that can /only/ be 
programmed by re-wiring (i.e. provides /no/ abstraction level whatsoever 
at which it can be programmed otherwise) /cannot/ be Turing complete.

Post a reply to this message