clipka wrote:
> Darren New schrieb:
>> clipka wrote:
>>
>>  > as it requires an infinitely long memory tape
>>
>> No it doesn't. It only requires an unbounded memory tape. There's a 
>> huge difference.
> 
> There is a huge difference indeed, and that's why you're mistaken. A 
> loop of memory tape would also fit the bill of "unbounded";

Oh come on. An "unbounded" memory tape means one with an unbounded amount of 
storage when you're talking about Turing machines.

A Turing machine will never consume an infinite amount of tape, and hence 
does not need an infinite tape. It only needs a tape with unbounded amounts 
of storage.

> I do concede that there are definitions that /theoretically/ don't 
> require an infinitely long memory tape - but they would require that the 
> tape would be /infinitely extendable/ as needed, which boils down to the 
> same problem:

But it doesn't boil down to the same problem. Not at all. Not even a little. 
The original definition never said anything about infinitely long tapes, 
because Turing knew the difference between infinite amounts of storage and 
unbounded amounts of storage.

You can tell, because it's impossible to simulate on real computers 
processes that *do* need an infinite amount of tape.

> By generic definition, a touring machine would have to be 
> capable of accessing /unlimited/ (and not only unbounded) memory, which 
> is physically impossible to arrange for.

Yes. Unbounded amounts of storage, not infinite amounts of storage. It's not 
difficult to arrange for a Turing machine to access however much memory it 
needs.

In other words, you can't look at X amount of bytes and tell whether an 
arbitrary given Turing machine will need more or not. Some will, some won't. 
If it halts in N steps, it won't need more than N symbols on the tape.

> If the machine you're trying to rewire into a UTM is designed to read 
> its data sequentially from a single input tape, mangle it with the 
> content of a 5x5 bits working memory, and produce sequential output on 
> another device (and from the Wikipedia description it appears to me that 
> this is what we're talking about, at least roughly), then tough luck - 
> you're never going to turn this thing into anything close to a Turing 
> machine, let alone a universal one, unless you're rewiring more than 
> what was originally intended to be rewireable.

Sure. Whether Colossus was Turing complete isn't what I was arguing. Having 
the program in hard wiring doesn't make it impossible to be Turing complete. 
*That* is what I was arguing.

> I'm perfectly aware of that. But it is a misconception to think that the 
> architecture of a computing device must necessarily be akin to that of a 
> Turing machine.

Huh? When did I ever say anything close to that?

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.

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

Post a reply to this message