Re: [sl4] Alan Turing's results are profound

From: John K Clark (johnkclark@fastmail.fm)
Date: Wed Oct 14 2009 - 09:59:17 MDT


On Wed, 14 Oct 2009 "Robin Lee Powell" <rlpowell@digitalkingdom.org>
said:

> I will not actually reproduce the math here; that would be rude
> to the authors, at the very least, and copyright violation.

As he has demonstrated numerous times the last thing in the world Robin
Lee Powell would want to be is rude, but until this second I had no idea
he was such a big fan of copyright law. There for a minute I thought
that maybe the reason he didn't explain the math was that it was totally
incomprehensible to him and might as well have been written in Chinese.
But no, that's not the reason at all, it's the copyright thing. Yes, I'm
sure that's the explanation, it's the copyright thing.

> Run the algorithm for at most N+1 steps. At every step, mark
> the state off in your enumeration. Stop when:
     
> You reach a state (of both the FSM and memory) that Obviously if a computer
> has a finite memory it would be possible in seen before. Since the Turing machine formalism is
> entirely deterministic, the algorithm is in an infinite loop through this state, and you're done:
> does not halt.

I've got to admit that makes a lot of sense, but it seems oddly
familiar, where did I see that before? Oh yes, now I remember, I said it
myself several posts ago:

"Obviously if a computer has a finite memory it would be possible in
theory to keep a record of every state the machine goes into, and if you
found that a state was repeated then you'd know for sure that the
machine was in a infinite loop. But the trouble is that the machine
needed to do all that checking would have to be much larger than the
original machine, and that larger machine would have no way to know if
it was itself in a infinite loop unless it was watched over by an even
larger machine."

> Stop When:
> The algorithm runs out of memory.

Again I can't disagree with that, but for some reason I am again
overcome by a strong feeling of Deja View. I wonder what the cause could
be. Maybe it was the post I sent sever posts before the previous one I
quoted when I said:

"So let's see, if you have a small memory you can prove that a computer
will halt when it runs out of memory. Wow what a profound result! I can
confidently predict that if you loaded Windows Vista into the original
ENIAC from 1946 that machine will halt too."

You quote the authors (I guess text is not covered by copyright law,
just mathematics) as saying
"the abovementioned proof is not novel in theoretical computer science."
You also quote them as saying "Unfortunately, N will ordinarily be such
a huge number that this result is only theoretical, it does not lead to
a practical algorithm". But then, bizarrely, you say "Which was the
point many of us have been trying to make".

What the hell are you talking about? What's this "many of us" crap? It's
the point I was trying to make but nobody agreed with me, that Turing
was profound and this stuff about finite memory machines is vacuous,
hell even the authors of the paper seem to think so. Since your short
term memory is so bad I will repeat something I quoted a few paragraphs
back that comes from one of my posts I sent about a dozen hours ago:

"Obviously if a computer has a finite memory it would be possible in
theory to keep a record of every state the machine goes into, and if you
found that a state was repeated then you'd know for sure that the
machine was in a infinite loop. But the trouble is that the machine
needed to do all that checking would have to be much larger than the
original machine, and that larger machine would have no way to know if
it was itself in a infinite loop unless it was watched over by an even
larger machine."

That is almost exactly what the paper said, and the authors of this
"paper" admit that it has no practical value and that they are saying
nothing new, so it is a bit of a mystery why they bothered to write it
in the first place, however there is no mystery why it is just online
and not published in a real science journal. But you read (skimmed more
likely) this piece of fluff and triumphantly announce "It does, in fact,
prove that the halting problem is only undecidable for infinite
computers" and then try to peddle the idea that some difficult problems
could be solved if only the computer had LESS memory. Should I start
pulling memory cards out of my computer now?

>And, of course, none of this has anything to do whatsoever with goal systems

Except that whenever you say "always do X, no exceptions" and X happens
to be one of the infinite number of programs that produce infinite loops
then your mighty AI turns into a useless lump of metal and silicon.
Turing wins again.

 John K Clark

-- 
  John K Clark
  johnkclark@fastmail.fm
-- 
http://www.fastmail.fm - Choose from over 50 domains or use your own


This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:05 MDT