 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8 Oct 2009 14:52:37 -0400, Jim Henderson <nos### [at] nospam com> wrote:
>
>The technical name is the "octothrope" IIRC.
>
That never really caught on, here.
>What do you call "*"?
>
Asterisk
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8-10-2009 15:58, clipka wrote:
> smc### [at] csccom schrieb:
>> When we introduced English to the world we did it at the point of a
>> gun and with gunboat diplomacy. The American method was more economic,
>> supplying cheap(ish) computer products and English language films.
>> Somehow that seems more acceptable to people at large.
>
> Interestingly, the USA /almost/ went for German as their national
> language (because they had difficulties agreeing on either English or
> French, AFAIK :-P)
In my recollection it was Dutch not German. Motivation a.o. that the
Dutch 'Acte van Verlatinghe' was a huge inspiration for the Declaration
of Independence anyway. IIRC the red, white and blue in the American
flag are also inspired by our national flag. yet, IANAH.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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:
>
>
>>The technical name is the "octothrope" IIRC.
>>
>>
> That never really caught on, here.
Nor here.
>>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.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Stephen wrote:
>> What do you call "*"?
> Asterisk
Nathan Hale
<character> An asterisk ("*", see also splat, ASCII).
Notionally, from "I regret that I have only one asterisk for
my country!" ("life to give" -> "ass to risk" -> "asterisk"),
a misquote of the famous remark uttered by Nathan Hale just
before he was hanged. Hale was a (failed) spy for the rebels
in the American War of Independence.
--
Tim Cook
http://empyrean.freesitespace.net
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8 Oct 2009 15:53:37 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>
>I've heard it called "Star", "Asterisk" and "Splat". I tend to use the
>first, but I kinda like the last.
Yes star dot star in computer/telephone speak. Asterisk when talking literature.
English is fun and easy :)
Splot! Away an boil yer heid :P
<bloody yanks, take a perfectly good language and marmalise it > :-)
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 08 Oct 2009 16:14:34 -0400, Tim Cook <z99### [at] gmailcom> wrote:
>Stephen wrote:
>>> What do you call "*"?
>> Asterisk
>
>Nathan Hale
>
> <character> An asterisk ("*", see also splat, ASCII).
> Notionally, from "I regret that I have only one asterisk for
> my country!" ("life to give" -> "ass to risk" -> "asterisk"),
> a misquote of the famous remark uttered by Nathan Hale just
> before he was hanged. Hale was a (failed) spy for the rebels
> in the American War of Independence.
LOL it's not from "asteriscum" latin for little star, then?
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 08 Oct 2009 21:43:45 +0200, andrel <a_l### [at] hotmailcom> wrote:
>> Interestingly, the USA /almost/ went for German as their national
>> language (because they had difficulties agreeing on either English or
>> French, AFAIK :-P)
>
>In my recollection it was Dutch not German. Motivation a.o. that the
>Dutch 'Acte van Verlatinghe' was a huge inspiration for the Declaration
>of Independence anyway. IIRC the red, white and blue in the American
>flag are also inspired by our national flag. yet, IANAH.
That's my memory too and it was a native Dutch speaker who cast the final vote.
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 08 Oct 2009 21:25:56 +0100, Stephen wrote:
> On 8 Oct 2009 15:53:37 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>
>
>>I've heard it called "Star", "Asterisk" and "Splat". I tend to use the
>>first, but I kinda like the last.
>
> Yes star dot star in computer/telephone speak. Asterisk when talking
> literature. English is fun and easy :)
:-)
> Splot! Away an boil yer heid :P
>
> <bloody yanks, take a perfectly good language and marmalise it > :-)
We made it efficient - got rid of all those extra vouweuls. ;-)
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8 Oct 2009 16:38:58 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>We made it efficient - got rid of all those extra vouweuls. ;-)
True! LMAO
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 08 Oct 2009 21:53:02 +0100, Stephen wrote:
> On 8 Oct 2009 16:38:58 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>
>>We made it efficient - got rid of all those extra vouweuls. ;-)
>
> True! LMAO
Though you may have noticed that I often tend to spell words the British
way. I realise that it's important to write to my intended audience. ;-)
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8 Oct 2009 17:02:51 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>Though you may have noticed that I often tend to spell words the British
>way. I realise that it's important to write to my intended audience. ;-)
And so it is :)
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 08 Oct 2009 22:12:36 +0100, Stephen wrote:
> On 8 Oct 2009 17:02:51 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>
>>Though you may have noticed that I often tend to spell words the British
>>way. I realise that it's important to write to my intended audience.
>>;-)
>
> And so it is :)
Which is why I don't use SMS much. ;-)
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
> clipka wrote:
>> where we'd replace some rarely-used characters with the German umlauts,
>
> I'm pretty sure this is why Americans call "#" the "pound sign." It's on
> the keyboard in the same place the Brits put their currency marker.
Indeed. As a matter of fact, just like the Germans used a variation of
the ASCII code, so did the British, using the "#" code point for their
currency sign.
I'm pretty sure the origin of calling "#" the "pound sign" was from
Americans being unaware that the Brits, when talking about that code
point, were actually talking about a totally different symbol.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 10/08/09 02:26, smc### [at] csccom wrote:
> When we introduced English to the world we did it at the point of a gun
> and with gunboat diplomacy. The American method was more economic,
> supplying cheap(ish) computer products and English language films.
> Somehow that seems more acceptable to people at large.
Umm... yeah. I can't fathom why people would rather watch a movie than
be riddled with bullets...
--
(((((((HYPNOTIC)))))))(((((((TAGLINE)))))))
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
> clipka 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. :-)
To the contrary, they have a /lot/ to do with each other.
While it is true that the theoretical construct known as a "Turing
machine" is "hard-wired" by definition, this is not necessarily the case
for a system /simulating/ such a machine. (Actually building a true
Turing machine is outright impossible, as it requires an infinitely long
memory tape, so a simulation is the closest you can get anyway.)
In fact, such a system to simulate a Turing machine may even be another
Turing machine, designed for the purpose of simulating any of a whole
/class/ of Turing machines, the exact details of which would be read
from the initial data on the tape. While the simulating Turing machine
would still by definition be hard-wired regarding its own operation, it
would be programmable regarding the simulated machine.
This can be pushed even so far as to design a Turing machine that would
be capable of simulating /any/ possible Turing machine (including itself
if required): A "Universal Turing machine". (Again, actually building
such a thing s impossible, but only for the same reason as is building
any other Turing machine.)
Now stating that a machine is "Turing-complete" is equivalent to saying
that it is capable of simulating not just /some/ Turing machine, but a
/Universal/ Turing machine - which by definition /is/ fully programmable
regarding the simulated Turing machine.
Therefore, a machine programmable only by re-wiring /cannot/, by
definition, be Turing-complete.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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.
> 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.
> Now stating that a machine is "Turing-complete" is equivalent to saying
that it is capable of simulating not just /some/ Turing machine, but a
/Universal/ Turing machine
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.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Thu, 08 Oct 2009 17:31:45 -0500, Neeum Zawan <m.n### [at] ieeeorg> wrote:
>On 10/08/09 02:26, smc### [at] csccom wrote:
>> When we introduced English to the world we did it at the point of a gun
>> and with gunboat diplomacy. The American method was more economic,
>> supplying cheap(ish) computer products and English language films.
>> Somehow that seems more acceptable to people at large.
>
> Umm... yeah. I can't fathom why people would rather watch a movie than
>be riddled with bullets...
I wrote that badly and reversed the meaning. :(
To rephrase what I wrote. Violence has been with us since time immemorial and
seems a natural, if reprehensible, way of doing things. Conversely after the
economic benefits of buying cheep imports have faded and people awaken to find
that own industries have declined. A greater resentment is often found. They
don't say "it is our fault for not supporting our own industries" but "Damn
Americans forcing their way of life on us and there is nothing we can do about
it, not even rebel"
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8 Oct 2009 17:20:53 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>On Thu, 08 Oct 2009 22:12:36 +0100, Stephen wrote:
>
>> On 8 Oct 2009 17:02:51 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>>
>>>Though you may have noticed that I often tend to spell words the British
>>>way. I realise that it's important to write to my intended audience.
>>>;-)
>>
>> And so it is :)
>
>Which is why I don't use SMS much. ;-)
>
Old f*rt! ;)
Me too :)
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 10/09/09 00:15, Stephen wrote:
> To rephrase what I wrote. Violence has been with us since time immemorial and
> seems a natural, if reprehensible, way of doing things. Conversely after the
> economic benefits of buying cheep imports have faded and people awaken to find
> that own industries have declined. A greater resentment is often found. They
> don't say "it is our fault for not supporting our own industries" but "Damn
> Americans forcing their way of life on us and there is nothing we can do about
> it, not even rebel"
Yes, but do they not realize the irony? By whining, they're acting very
American!
<dodges tomato>
--
(((((((HYPNOTIC)))))))(((((((TAGLINE)))))))
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 09 Oct 2009 00:39:25 -0500, Neeum Zawan <m.n### [at] ieeeorg> wrote:
>On 10/09/09 00:15, Stephen wrote:
>> To rephrase what I wrote. Violence has been with us since time immemorial and
>> seems a natural, if reprehensible, way of doing things. Conversely after the
>> economic benefits of buying cheep imports have faded and people awaken to find
>> that own industries have declined. A greater resentment is often found. They
>> don't say "it is our fault for not supporting our own industries" but "Damn
>> Americans forcing their way of life on us and there is nothing we can do about
>> it, not even rebel"
>
> Yes, but do they not realize the irony? By whining, they're acting very
>American!
>
Whatever happened to the American frontier spirit?
><dodges tomato>
Bio warfare?
--
Regards
Stephen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 10/09/09 02:33, Stephen wrote:
> Whatever happened to the American frontier spirit?
It ceased being profitable.
--
"I solved my drinking problem. I joined Alcoholics Anonymous. I still
drink, but I use a different name"
-- Rodney Dangerfield
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 09 Oct 2009 06:22:20 +0100, Stephen wrote:
> On 8 Oct 2009 17:20:53 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>
>>On Thu, 08 Oct 2009 22:12:36 +0100, Stephen wrote:
>>
>>> On 8 Oct 2009 17:02:51 -0400, Jim Henderson <nos### [at] nospamcom> wrote:
>>>
>>>>Though you may have noticed that I often tend to spell words the
>>>>British way. I realise that it's important to write to my intended
>>>>audience. ;-)
>>>
>>> And so it is :)
>>
>>Which is why I don't use SMS much. ;-)
>>
>>
> Old f*rt! ;)
>
> Me too :)
Even the rare occasion I do, it's to my stepson who also writes complete
sentences. :-)
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> 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.
Fair enough. I was just disputing the version of that without the "none of
the hard wiring options implements a capability for soft programming" part,
which is how you seemed to be phrasing it at the start.
>> 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.
Yes. Clearly, it needs to have enough hard-wiring operations to be able to
operate on arbitrary memory and so on. A differential engine isn't going to
be Turing complete.
> 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.
> 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. If you have enough
read/write storage and a state machine, you're Turing complete. It doesn't
even take a big state machine. (Something like 3 states with 5 symbols, or 5
states of 3 colors, or something like that.)
> 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.
Yes.
> To simulate a UTM, you need to simulate this aspect as well,
Yes.
> therefore being Turing complete /requires/
> the ability to be re-programmable without re-wiring (at least in /some/
> wiring configuration).
Certainly not every hard-wired program is Turing complete, if that's what
you're implying. A hard-wired program to divide two numbers in memory isn't
going to give you a Turing complete machine. 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.
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.
I think it's just a confusion that you're mixing up too many levels at once.
A Universal Turing Machine doesn't change its hard-wiring to simulate other
Turing machines. It gets fed the descriptions of hardware via its inputs,
but the UTM itself has exactly one program it runs. Put it this way: there's
nothing that prevents you from building a UTM whose program logic can only
be read from ROM and not RAM.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> 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.
Given the mathematical definition of the memory tape in a TM, this
interpretation makes no sense. Everyone says "unbounded tape" because that
implies "unbounded amount of storage" given how the tape is defined. (I.e.,
it's defined as having one end as well as operations to move left and right.)
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> There. Arrange for *that* to access however much memory it needs. It is
> /not/ physically possible.
BTW, this has nothing to do with whether you can have a hard-wired UTM. All
this means is that no real physical computer or simulated computer can ever
actually be a Turing machine at all. But we knew that. :-)
--
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:
>> 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).
>> 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.
/If/ a machine can be hard-wired that way, then this /implies/ (and
therefore also, in terms of logic, /requires/) that the device /can/
provide for a means to program it at a non-hardware level - because that
is a key feature of /any/ UTM.
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.
> 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.
And by virtue of being a UTM, it is automatically "soft-programmable" as
well.
> 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.
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.
> I think it's just a confusion that you're mixing up too many levels at
> once.
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.
> A Universal Turing Machine doesn't change its hard-wiring to
> simulate other Turing machines. It gets fed the descriptions of hardware
> via its inputs, but the UTM itself has exactly one program it runs. Put
> it this way: there's nothing that prevents you from building a UTM whose
> program logic can only be read from ROM and not RAM.
There is, however, no way to build a UTM that, at /every/ level, can
read program logic from ROM /only/.
It must be "soft-programmable" at /some/ level in order to qualify as
Turing-complete.
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.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
> clipka wrote:
>> 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.
>
> Given the mathematical definition of the memory tape in a TM, this
> interpretation makes no sense. Everyone says "unbounded tape" because
> that implies "unbounded amount of storage" given how the tape is
> defined. (I.e., it's defined as having one end as well as operations to
> move left and right.)
Erm... do you /really/ know what you're talking about?
Whenever a Turing machine's tape is defined as having /any/ end at all,
then it is defined as having /two/ ends, /both/ of which will be
automatically extended as needed.
But I prefer to stick to Turing's own description:
"...an infinite memory capacity obtained in the form of an /infinite
tape/..." (Turing 1948, p. 61)
There. Emphasis added. Any further questions?
(Yes, there /are/ variations on the theme that use a tape which is
bounded in /one/ direction only; these are, however, not classic generic
Turing machines.)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Erm... do you /really/ know what you're talking about?
Yes.
> Whenever a Turing machine's tape is defined as having /any/ end at all,
> then it is defined as having /two/ ends, /both/ of which will be
> automatically extended as needed.
There are lots of definitions of Turing machines. Some have one end, some
have no ends. They're all equivalent, mathematically.
> But I prefer to stick to Turing's own description:
>
> "...an infinite memory capacity obtained in the form of an /infinite
> tape/..." (Turing 1948, p. 61)
>
>
> There. Emphasis added. Any further questions?
Well, he's wrong. :-)
> (Yes, there /are/ variations on the theme that use a tape which is
> bounded in /one/ direction only; these are, however, not classic generic
> Turing machines.)
Whatever.
No Turing machine has or needs an infinite tape, unless you want to
initialize an infinite length of tape with some pattern of symbols.
Do you understand why Turing machines have an unbounded tape while (say)
linear cellular automata have infinite tapes?
No matter how long a Turing machine runs, it cannot access an infinite
amount of tape. Therefore, the tape needn't be infinite, merely unbounded,
and that's a *huge* difference.
--
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:
> 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".
It does, when the context implies that "hardwired" means that an option
to re-program /without/ re-wiring does /not/ exist, regardless how you
wire it.
> 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.
If "you /need/ to change wiring to program something" (emphasis added),
then it /does/ keep it from being turing complete.
If the machine is capable of being wired to be Turing complete
(accepting "soft-programming"), then you possibly don't /need/ to change
wiring, as it /may/ happen to already be wired just the way you need.
>> 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.)
This is the /only/ sense in which the term "soft-programmable" can be
interpreted without becoming pure nonsense - whether it is a UTM or any
other computing device - so I'm taking this interpetation for granted.
It doesn't matter whether the UTM is just /isomorphic/ to some TM it
simulates: The system as a whole runs a /program/, part of which is
stored on the tape.
> 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.
And it is exactly /this/ statement I'm arguing against. It is a
statement about a computer with a certain /requirement/ regarding
programming. If a computer /has/ that requirement (and not just an
/option/ to that effect), it /does/ mean it isn't Turing complete, and
therefore your statement is simply false.
>> 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.
As mentioned before, in that sense there is /only/ programming through
re-wiring, and therefore in that sense it doesn't make sense to even
/mention/ such a property for any computing device.
I therefore argue that this low-level perspective is pure nonsense in
this discussion.
>> 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.
I'm not going to that level, because I'm not a mathematician, and
therefore leave its definition to common sense.
> 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.
No, it's not automatically going to be: It depends on the "wiring"; for
instance, a Turing machine constituting a Busy Beaver will never be
Turing complete, despite /being/ a Turing machine (which should qualify
as "anything remotely close" in this sense I guess).
I cannot help but note that for someone demanding from /me/ precise
mathematical definitions, you're surprisingly lax in your own wording.
> It takes less than 30 states and one read/write cycle
> on one symbol of a tape-like memory to qualify.
To avoid confusion, I take the "one symbol" to mean "one symbol plus the
empty-cell symbol" (which I as a layman would consider a total of two
symbols).
> 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.
Just one instruction at what abstraction level? CPU? Or "bytecode" (or
"soft-programming" to stick to my original term) interpreted by jumping
around in the ROM?
(And again: No, just the mentioned abilities does not /necessarily/ make
your machine Turing complete. It only enables you to simulate /some/
Turing machine(s) - only the proper ROM content would make it Turing
complete, so your ability to /make/ the machine Turing complete would
depend on what part of the ROM you could re-program - or "re-wire", if
you like.)
> I think we're agreeing, but I think you're ascribing to me at least one
> position I never took.
It may be a position you never /intended/ to take, but you persistently
keep taking by your choice of words, so it's hard for me to tell.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
>> Whenever a Turing machine's tape is defined as having /any/ end at
>> all, then it is defined as having /two/ ends, /both/ of which will be
>> automatically extended as needed.
>
> There are lots of definitions of Turing machines. Some have one end,
> some have no ends. They're all equivalent, mathematically.
How can they be equivalent if the resulting pattern on the tape /must/
necessarily be different for some Turing machines (namely those that
also access tape to the left of the starting position)?
They may be /isomorphic/, but still they're different.
I've never heard of "single-ended tape" Turing machines except as a
special case.
>> "...an infinite memory capacity obtained in the form of an /infinite
>> tape/..." (Turing 1948, p. 61)
>>
>>
>> There. Emphasis added. Any further questions?
>
> Well, he's wrong. :-)
I will not agree with that statement of yours. To me he's right, as he
happens to have invented the concept.
> Whatever.
>
> No Turing machine has or needs an infinite tape, unless you want to
> initialize an infinite length of tape with some pattern of symbols.
Whatever, too.
It is irrelevant whether a Turing machine uses an /infinite/ tape, or
just has its tape /extended/ as needed: Unless you know that the machine
halts and/or enters an infinite loop, there is no way whatsoever to
build a real, reliable TM, because you cannot guarantee that you will be
able to provide for all the tape it may ever need.
And no, I'm not accepting the argument that you can slow down the
machine as its tape grows. That's about the same nonsense argument as
for the race between Achilleus and the Turtle back in ancient Greece: It
cannot theoretically be refuted, but it's plain good old nonsense
practically.
> No matter how long a Turing machine runs, it cannot access an infinite
> amount of tape. Therefore, the tape needn't be infinite, merely
> unbounded, and that's a *huge* difference.
However huge that difference may be theoretically, I can't think how
this is of any practical importance for a generic Turing machine with
yet-unknown properties (most particularly a UTM, for that matter).
I also fail to see any theoretical difference between an infinite tape,
and a tape being grown automatically as needed.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Darren New schrieb:
>
>> 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".
>
> It does, when the context implies that "hardwired" means that an option
> to re-program /without/ re-wiring does /not/ exist, regardless how you
> wire it.
You understand that Turing machines are hard-wired, right? You can't
reprogram them without rewiring them?
> If "you /need/ to change wiring to program something" (emphasis added),
> then it /does/ keep it from being turing complete.
I suspose it's arguing over what "programming" means, now.
> If the machine is capable of being wired to be Turing complete
> (accepting "soft-programming"), then you possibly don't /need/ to change
> wiring, as it /may/ happen to already be wired just the way you need.
If you're talking about real machines with real I/O and such, then no, maybe
you want to rewire it anyway.
>>> 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.)
>
> This is the /only/ sense in which the term "soft-programmable" can be
> interpreted without becoming pure nonsense - whether it is a UTM or any
> other computing device - so I'm taking this interpetation for granted.
>
> It doesn't matter whether the UTM is just /isomorphic/ to some TM it
> simulates: The system as a whole runs a /program/, part of which is
> stored on the tape.
Yes, but the output of that program might not appear anywhere on the tape.
If I take a Turing machine to add two numbers together from the tape and
write the result on the tape, there's nothing that says a UTM running that
program will read two numbers off the tape and write the result on the tape.
>> 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.
>
> And it is exactly /this/ statement I'm arguing against. It is a
> statement about a computer with a certain /requirement/ regarding
> programming. If a computer /has/ that requirement (and not just an
> /option/ to that effect), it /does/ mean it isn't Turing complete, and
> therefore your statement is simply false.
Alright, so you're arguing over the word "is". Fair enough. You're saying
that your statement "has to be rewired" is to be interpreted as logically
implying it's incapable of being rewired into a universal machine.
I don't agree that most people interested in the subject would interpret
your sentence that way, but if you do, sure, you've defined your statement
to mean that, so there ya go.
I would have said "if it can't be rewired into a universal machine, then you
have to rewire it for every calculation."
>> 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.
>
> As mentioned before, in that sense there is /only/ programming through
> re-wiring, and therefore in that sense it doesn't make sense to even
> /mention/ such a property for any computing device.
But the whole magic of the property is that you *can* build such an
interpreter. Before the UTM was invented, it wasn't anyways clear to anyone
that such a thing was possible. Nobody knew that the rules of arithmetic
were adequate to express the rules of arithmetic.
> I therefore argue that this low-level perspective is pure nonsense in
> this discussion.
I disagree.
>>> 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.
>
> I'm not going to that level, because I'm not a mathematician, and
> therefore leave its definition to common sense.
Well, that's exactly what Turing did, which is why he's still world famous. :-)
>> 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.
>
> No, it's not automatically going to be: It depends on the "wiring"; for
> instance, a Turing machine constituting a Busy Beaver will never be
> Turing complete, despite /being/ a Turing machine (which should qualify
> as "anything remotely close" in this sense I guess).
Fair enough. Obviously I meant to say if you have something remotely close
to being a turing machine which you can rewire the state machine of.
> I cannot help but note that for someone demanding from /me/ precise
> mathematical definitions, you're surprisingly lax in your own wording.
You're taking this way too seriously. You can win.
> > It takes less than 30 states and one read/write cycle
>> on one symbol of a tape-like memory to qualify.
>
> To avoid confusion, I take the "one symbol" to mean "one symbol plus the
> empty-cell symbol" (which I as a layman would consider a total of two
> symbols).
No. One symbol is what's stored on one position the tape, which may be more
than one bit. I think the minimum turing machine is 28 states and 3 baud or
something.
>> 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.
>
> Just one instruction at what abstraction level? CPU?
CPU. I.e., the hardware only interprets one opcode.
> Or "bytecode" (or
> "soft-programming" to stick to my original term) interpreted by jumping
> around in the ROM?
> (And again: No, just the mentioned abilities does not /necessarily/ make
> your machine Turing complete. It only enables you to simulate /some/
> Turing machine(s) - only the proper ROM content would make it Turing
> complete, so your ability to /make/ the machine Turing complete would
> depend on what part of the ROM you could re-program - or "re-wire", if
> you like.)
There's no ROM. There's just one instruction reading data out of the memory.
>> I think we're agreeing, but I think you're ascribing to me at least
>> one position I never took.
>
> It may be a position you never /intended/ to take, but you persistently
> keep taking by your choice of words, so it's hard for me to tell.
You're making ambiguous statements (as am I, by the very nature of language)
which we're interpreting differently, is all.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> They may be /isomorphic/, but still they're different.
That would be "equivalent" then.
> I've never heard of "single-ended tape" Turing machines except as a
> special case.
It's not too common, because it's unnecessary, and it adds no power to the
descriptive system. Normally if you try to go left from the first position,
that's a halting state.
>>> There. Emphasis added. Any further questions?
>>
>> Well, he's wrong. :-)
>
> I will not agree with that statement of yours. To me he's right, as he
> happens to have invented the concept.
Feel free. Math doesn't care whether you agree or not.
> It is irrelevant whether a Turing machine uses an /infinite/ tape, or
> just has its tape /extended/ as needed:
No, really, it truly and deeply isn't the same thing.
Look, I'm going to build a cellular automata. It's going to have one rule.
"Look at all positions to the right of the cell. If anywhere in there there
are exactly 20 black cells with at least one white cell on either side, make
this cell black."
That's an infinite tape description. You *cannot* even *begin* to simulate
that on *any* computer. It's more than what a TM can compute.
> Unless you know that the machine
> halts and/or enters an infinite loop, there is no way whatsoever to
> build a real, reliable TM, because you cannot guarantee that you will be
> able to provide for all the tape it may ever need.
Here's a pseudo-Turing machine:
"State one: write a 1 to every odd-numbered tape entry, then go to state 2"
"State two: write a 2 to every even-numbered tape entry, then halt."
That halts in 3 steps or less (depending how you count). Code that up in a
Turing machine with merely bounded tape.
> cannot theoretically be refuted, but it's plain good old nonsense
> practically.
Not really. You build more and more tape as time goes on. But again, of
course, you're arguing that real physical computers can't run forever. Yes,
sure, granted. But irrelevant.
>> No matter how long a Turing machine runs, it cannot access an infinite
>> amount of tape. Therefore, the tape needn't be infinite, merely
>> unbounded, and that's a *huge* difference.
>
> However huge that difference may be theoretically, I can't think how
> this is of any practical importance for a generic Turing machine with
> yet-unknown properties (most particularly a UTM, for that matter).
See above. We have abstractions which *are* infinite and which you *cannot*
calculate with a turing machine.
> I also fail to see any theoretical difference between an infinite tape,
> and a tape being grown automatically as needed.
See above. A UTM cannot quantify over the contents of the tape. This puts
whole boatloads of things that can be described outside the realm of
"calculation".
--
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:
>> As mentioned before, in that sense there is /only/ programming through
>> re-wiring, and therefore in that sense it doesn't make sense to even
>> /mention/ such a property for any computing device.
>
> But the whole magic of the property is that you *can* build such an
> interpreter. Before the UTM was invented, it wasn't anyways clear to
> anyone that such a thing was possible. Nobody knew that the rules of
> arithmetic were adequate to express the rules of arithmetic.
True. Yet in 2009, people are taking it for granted by now, so if a
contemporary Wikipedia article claims that Colossus could be
re-programmed "partially (by re-wiring)", then I find it difficult to
imagine that this is to be interpreted anything other than as "partially
(by re-wiring /only/, providing no other option)".
/That/ was the initial starting point of the discussion we're now having.
So in this sense, say: Can a computing machine that is programmable /by
re-wiring only/ ever be Turing complete?
I categorically say no, as there is obviously no way to feed such a
machine with data isomorphic to some generic initial tape content for a
UTM, and have it generate output data isomorphic to what the UTM would
produce.
Unless, of course, you'd consider human "re-wiring operators" as being
part of the machine, and their orders as being part of the input data,
but I guess we agree that this is not normally the scope of how we'd
define a computing device.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New schrieb:
>> It is irrelevant whether a Turing machine uses an /infinite/ tape, or
>> just has its tape /extended/ as needed:
>
> No, really, it truly and deeply isn't the same thing.
>
> Look, I'm going to build a cellular automata. It's going to have one rule.
>
> "Look at all positions to the right of the cell. If anywhere in there
> there are exactly 20 black cells with at least one white cell on either
> side, make this cell black."
>
> That's an infinite tape description. You *cannot* even *begin* to
> simulate that on *any* computer. It's more than what a TM can compute.
Provided that you have a "homogenous" initial state except for a "local
anomaly" (as is the case for a TM), I'm pretty sure that you cannot only
/begin/ to simulate that, but even /continue/ to do so, with no more or
less memory requirements than for a TM.
I reckon that if the whole smash /starts/ with a local anomaly, some
repeating pattern to the "left" and some (possibly different) repeating
pattern to the "right", the next step will again leave a local anomaly
with a pattern to the left and right, except that the patterns may have
a significantly longer period, and the local anomaly may have grown.
So "all" you have to do is simulate the local anomaly, as well as the
repeating pattern.
Even if you "duplicate" the anomaly at regular intervals, all this will
do is change the repeating pattern.
Thus, I still see no fundamental difference.
Sure, I do see why an actual /implementation/ (as opposed to mere
simulation) of such a machine would be infeasible for /different/
reasons than a TM, but I wouldn't attribute this to the /tape/ being
infinite vs. just "unbounded", but rather the rules in this case
allowing to /access/ an infinitely large number of cells in a /single/ step.
> > Unless you know that the machine
>> halts and/or enters an infinite loop, there is no way whatsoever to
>> build a real, reliable TM, because you cannot guarantee that you will
>> be able to provide for all the tape it may ever need.
>
> Here's a pseudo-Turing machine:
>
> "State one: write a 1 to every odd-numbered tape entry, then go to state 2"
> "State two: write a 2 to every even-numbered tape entry, then halt."
>
> That halts in 3 steps or less (depending how you count). Code that up in
> a Turing machine with merely bounded tape.
See above for how I'd try to approach this. If it has any repeating
pattern, you don't need infinite storage to represent it.
> See above. We have abstractions which *are* infinite and which you
> *cannot* calculate with a turing machine.
You still haven't managed to come up with any, from what I see.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> so if a contemporary Wikipedia article claims that Colossus could be re-programmed
"partially (by re-wiring)", then I find it difficult to imagine that this is to be
interpreted anything other than as "partially (by re-wiring /only/, providing no other
option)".
Um, I don't?
> So in this sense, say: Can a computing machine that is programmable /by
> re-wiring only/ ever be Turing complete?
What about a real physical implementation of a Turing machine, where
rewiring it gives you different Turing machines?
True, you have to get the data onto the tape initially, but since that
wouldn't be part of the "program" per se, I don't see where that's addressed.
> but I guess we agree that this is not normally the scope of how we'd
> define a computing device.
Not *now*, no. Back in Turing's day, that's exactly what it was. :-)
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> but I wouldn't attribute this to the /tape/ being
> infinite vs. just "unbounded", but rather the rules in this case
> allowing to /access/ an infinitely large number of cells in a /single/
> step.
But *that* is *exactly* the difference between an infinite tape and an
unbounded one. An tape doesn't have to be infinite if you can't access an
infinite number of cells in a finite number of steps. That's exactly 100%
the entire point of the distinction.
> You still haven't managed to come up with any, from what I see.
I'll leave you to look it up in the textbooks, then, if you can't
extrapolate from that to a machine impossible to simulate.
--
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:
>> So in this sense, say: Can a computing machine that is programmable
>> /by re-wiring only/ ever be Turing complete?
>
> What about a real physical implementation of a Turing machine, where
> rewiring it gives you different Turing machines?
As I already mentioned, this would require interpreting the "re-wiring
operator" to be considered as part of the Turing machine itself (and the
instructions you give to them as part of the input data), which I would
really hesitate to agree with.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Darren New schrieb:
>
>>> So in this sense, say: Can a computing machine that is programmable
>>> /by re-wiring only/ ever be Turing complete?
>>
>> What about a real physical implementation of a Turing machine, where
>> rewiring it gives you different Turing machines?
>
> As I already mentioned, this would require interpreting the "re-wiring
> operator" to be considered as part of the Turing machine itself (and the
> instructions you give to them as part of the input data), which I would
> really hesitate to agree with.
I think you're just using "by re-wiring only" to mean "cannot be wired into
a UTM." Which is fine, but an odd kind of interpretation. I don't know the
details of Colossus as such, but it doesn't take a whole lot of wiring to
make a machine that's capable of being a UTM.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
