|
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Stephen schrieb:
> Bio warfare?
LOL!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 09 Oct 2009 23:22:02 -0300, Nicolas Alvarez wrote:
> Jim Henderson wrote:
>> On Thu, 08 Oct 2009 20:30:26 +0100, Stephen wrote:
>>> On 8 Oct 2009 14:52:37 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>>>>What do you call "*"?
>>>>
>>> Asterisk
>>
>> I've heard it called "Star", "Asterisk" and "Splat". I tend to use the
>> first, but I kinda like the last.
>
> http://www.codinghorror.com/blog/archives/001133.html
Handy - thanks!
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka <ano### [at] anonymousorg> 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"; however, it
> doesn't do for a true Turing machine.
A loop of memory tape does not, in fact, provide an unbounded amount
of memory. It provides a finite, fixed amount of memory, hence very
definitely not unbounded.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> A loop of memory tape does not, in fact, provide an unbounded amount
> of memory. It provides a finite, fixed amount of memory, hence very
> definitely not unbounded.
>
I think he was comparing it to an "unbounded space", which means a space
without edges. It's possible to have an unbounded finite space, like the
surface of a sphere. But that's not what it means in Turing machine
conversations, where the tape is clearly linear.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
> 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.
Consider a Turing machine that does not halt, but keeps advancing on the
tape.
There. Arrange for *that* to access however much memory it needs. It is
/not/ physically possible.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
> Having the program in hard wiring doesn't make it impossible to be
> Turing complete. *That* is what I was arguing.
If a machine can only be programmed by hard wiring, and none of the hard
wiring options implements a capability for soft programming, then it
/is/ 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.
You did, as a matter of fact, assert that Colossus could have been
hard-wired into a UTM, provided it had enough cables to re-wire.
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.
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: a UTM, by definition, reads the details of the
Turing machine to simulate (viz: the program) from its tape, i.e. the
program is part of the data it works on. To simulate a UTM, you need to
simulate this aspect as well, therefore being Turing complete /requires/
the ability to be re-programmable without re-wiring (at least in /some/
wiring configuration).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp schrieb:
> clipka <ano### [at] anonymousorg> 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"; however, it
>> doesn't do for a true Turing machine.
>
> A loop of memory tape does not, in fact, provide an unbounded amount
> of memory. It provides a finite, fixed amount of memory, hence very
> definitely not unbounded.
Note that there is a difference between an "unbounded amount of memory",
and an "unbounded memory tape": In the former case we're talking about
an absence of limit in quantity, in the latter we're talking about a
topological property.
Note that I'm interpreting the grammatical construct "unbounded memory
tape" to read "unbounded thing called a memory tape", not "tape
constituting an unbounded [amount of] memory"; your interpretation may
differ.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Darren New schrieb:
>
>> 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.
>
> Consider a Turing machine that does not halt, but keeps advancing on the
> tape.
>
> There. Arrange for *that* to access however much memory it needs. It is
> /not/ physically possible.
Yes. That doesn't make it infinite. You can arrange for that by making the
speed of the machine 1/2^N where N is the number of slots filled in the tape.
You can't do that with something that needs an infinite amount of tape.
Sure, I was unclear. You can't arrange for *every* machine to have as much
tape as it needs. But you *can* arrange for *some* machines to have as much
tape as they need, which is *not* the case for a programming paradigm that
requires an infinite amount of storage. Most of the practically interesting
machines do *not* consume unlimited amounts of memory before they halt.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|