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

> Programmable computers? A German invention.

Needing to rewire something doesn't make it non-programmable. It just makes 
it non-von Neumann.

-- 
   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 10:03:07 -0700, Darren New <dne### [at] sanrrcom> wrote:

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

I've often wondered why Americans call "#" the pound sign and was going to ask
you but since my name is Stephen :P I looked it up. Interesting. It seems a
coincidence that on the US keyboard it is in the same place as "£" on the UK
k/board. So another internet myth is born. :)
I know # as hash and generally pronounce it as number.

http://en.wikipedia.org/wiki/Number_sign#Usage_in_North_America

How is @ used nowadays? I believe it should only be used like 5lb @ 2/- a lb (or
5# @ 2c/pound) not "I will meet you @ the pub".
-- 

Regards
     Stephen

Post a reply to this message

Stephen wrote:
> How is @ used nowadays? I believe it should only be used like 5lb @ 2/- a lb (or
> 5# @ 2c/pound) not "I will meet you @ the pub".

Yes, unless you're speaking SMS or 1337.

-- 
   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 16:30:12 +0100, Invisible <voi### [at] devnull> wrote:

>Hehe... When I was at school, one of the teachers paid something like 
>£200 for a large beige "electronic typewriter". It has a blocky LCD, a 
>trivial wordprocessor program in ROM, and when you press a button, it 
>types the whole lot out onto paper using the integrated dot-matrix (!!) 
>printer.
>
>It was the very height of technology. I mean, sure you can't actually 
>save your work, only print it. But it's so much better than a typewriter 
>because you can edit before you print!

Was that a "Starwriter"? If so my father had one and it passed to me then to my
brother. It was only a bit of an improvement on an electric typewriter but a big
step for man on the manual ones.
-- 

Regards
     Stephen

Post a reply to this message

On Thu, 08 Oct 2009 10:37:48 -0700, Darren New <dne### [at] sanrrcom> wrote:

>Stephen wrote:
>> How is @ used nowadays? I believe it should only be used like 5lb @ 2/- a lb (or
>> 5# @ 2c/pound) not "I will meet you @ the pub".
>
>Yes, unless you're speaking SMS or 1337.

I have seen it creep into modern usage. Shame!
-- 

Regards
     Stephen

Post a reply to this message

On 8-10-2009 10:57, Invisible wrote:
>>> Well, THAT explains why the hell I can't even say his name out loud, 
>>> never mind spell it. :-P
>>
>> as for pronunciation try dike-strah.
> 
> Interesting. DJ seemed to think the K was silent.

well, then he was wrong in that respect.

> 
>>> Apparently he was quite clever though. I only know about him because 
>>> he apparently invented an algorithm for turning a series of 
>>> expression tokens into an actual expression tree...
>>
>> You should also know him because I mentioned him a few times here. He 
>> did a lot of work in concurrent programming (e.g. the P and V 
>> operation). IIRC he (or his team) implemented the first interrupt 
>> routines. He did a lot on designing programs from specification. Many 
>> of the algorithms he is most commonly known for were originally just 
>> examples of how to derive a program from a specification. You need 
>> more proof that thinking about your algorithm and documenting it might 
>> lead to new insights?
> 
> Actually, now I think about it, I do vaguely recall looking him up on 
> Wikipedia. Wasn't he one of those Ivory Tower theorists who thought that 
> you can actually specify what a program is supposed to do 
> mathematically, 

he was, sort of.

> and then formally prove that the program you wrote does it?

not really, because that would imply that you write the program first 
and then prove it. In fact it goes hand in hand.

With respect to the sort of above: he did a lot of very practical things 
that have seriously influenced a lot of people and a lot of hardware. So 
he was not only an Ivory tower guy. However, some of his work has that 
feeling. My opinion about that is that he made a very big mistake early 
on in defining his programming language (viz. guarded commands): he 
introduced the assignment. The talk I sometimes give about his work is 
therefore called: 'The assignment considered harmful'.

I am sure I said it before, if you want to improve your understanding of 
programming read 'A Discipline of Programming' and/or 'Selected Writings 
on Computing: A Personal Perspective'. The latter is a collection of his 
EWD papers.

Post a reply to this message

On Thu, 08 Oct 2009 18:33:44 +0100, Stephen wrote:

> On Thu, 08 Oct 2009 10:03:07 -0700, Darren New <dne### [at] sanrrcom> wrote:
> 
>>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.
> 
> I've often wondered why Americans call "#" the pound sign and was going
> to ask you but since my name is Stephen :P I looked it up. Interesting.

The technical name is the "octothrope" IIRC.

What do you call "*"?

Jim

Post a reply to this message

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.

>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