|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |