clipka wrote:
> 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).

Sure. If you want your Intel to run a different instruction set, you need to 
rewire it. If the instruction set is powerful enough for your needs, you 
don't need to do that.

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

I understand that and I agree. My sole point originally was to say that it's 
not a logical implication that "hardwired" implies "not turing complete".

If you go back to what I originally 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. :-)
"""

You can see that I'm saying that just because you need to change wiring to 
program something doesn't keep it from being turing complete. The converse 
isn't addressed.

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

Yes. But it's not just the hard wiring that causes it, but rather the 
structure of the machine interpreting the "hard wires".

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

Yes.

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

Sort of, yes.  (Sort of in the sense that a UTM interpreting its tape is 
isomorphic to the actual turing machine being interpreted, but not identical 
to it.)

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

Yes.

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

Yes. Now here's the "some level" part: It takes something external to the TM 
to decide what the bits of the tape *mean*.  The UTM's tape is isomorpic to 
the TM being simulated, but that's not quite the same as running the TM's 
program.

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

I think you're arguing against a statement I haven't made.  I was simply 
pointing out to whoever might not know it that just because a computer needs 
to be physically modified to run a different program doesn't mean it isn't 
Turing complete.

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

That *is* what a Turing machine does. There's no code on the tape that 
executes. That's the whole *point* of defining a UTM - that there is a 
program that can simulate running any other TM hardware program.

The point is that even if you only *execute* from ROM, you *can* calculate 
every function you *could* calculate by rewiring the machine, *if* your ROM 
has the right program in it.

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

Great. Now define the words you put in quotes precisely and mathematically.

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

Well.... The barrier to being Turing complete is amazingly low. If you have 
anything remotely close to a Turing machine, then it's going to be Turing 
compatible. It takes less than 30 states and one read/write cycle on one 
symbol of a tape-like memory to qualify.

Sure, if you have a differential engine that only calculates one function, 
it's only going to calculate one function. But it's not like the machine has 
to have an "abstraction level" built in. Normal manipulation of plain old 
integer data will do the trick.

But if you can write to and read from memory, make a decision, and branch to 
a different place in the ROM based on that memory, you're Turing complete. 
Heck, you can be Turing complete if you have just one instruction.


I think we're agreeing, but I think you're ascribing to me at least one 
position I never took. Also, I think while you're technically correct with 
the above statement, it's also worded in a way as to be a tautology as well 
as far more restrictive in reality than the statement makes it sound.

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

Post a reply to this message