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