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"; however, it 
doesn't do for a true Turing machine.

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


> 
>> Therefore, a machine programmable only by re-wiring /cannot/, by 
>> definition, be Turing-complete.
> 
> I don't think that's right. Wire up the computer to be a UTM, and it's 
> Turing complete.
 >
 > Unless you are unable to wire up Colossus in such a way that it can
 > interpret arbitrary Turing machine programs, it it Turing complete.
 > I.e., Colossus would be the "simulating" Universal Turing Machine on
 > which you could interpret any other Turing machine.

Question is whether Colossus, from its design, had any similarity with a 
Turing machine at all.

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.

> Any real machine capable of simulating an arbitrary Turing machine is 
> Turing complete. The only limitation would be whether Colossus had 
> enough wires to do the job, really. But you could conceive of a machine 
> with hard wires that simulates a Turing machine.
 >
> Indeed, you're using one.

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.

Post a reply to this message