On Jan 25, 2010, at 10:47 PM, Rob Freeman wrote: (01)
> On Mon, Jan 25, 2010 at 12:02 PM, Christopher Menzel
> <cmenzel@xxxxxxxx> wrote:
>> On Jan 23, 2010, at 9:46 PM, Rob Freeman wrote:
>>
>>> Why anyone would characterize undecidability as a "limit of
>>> computation", I don't know.
>>
>> That's quite clear. Let me help: A problem is undecidable if it
>> cannot be solved by any
>> computer, even in theory. So the existence of undecidable problems
>> (like the halting
>> problem) shows that there are limits to the problems that computers
>> can solve; you
>> know, limits to computation or, better, to computability.
>
> This is perhaps the center of the issue. That decidability expresses
> only a "limit of computation" is also the only "substantive claim" you
> have made.
>
> Your argument is that I don't know what I am talking about because I
> don't see the problem this way. (02)
I believe that Chris' point was more that you are using technical
language in a nonstandard way. He is using "decideable", etc. in the
way that these words are used in textbooks, technical meetings,
research groups, etc.., whereas you seem to be using them in a
different sense. (03)
I take it that you feel that you are speaking from a different, er,
perspective? Put another way, you are talking about a different topic.
It would be helpful, therefore, if you could use a different
terminology, or at least flag your non-standard uses of the usual
terminology. In another forum, a similar difficulty arose over the
word "representation", and we now routinely use there such locutions
as tag:representation, awww:representation, etc., to clarify our
intended meanings. (04)
>
> My question was of course rhetorical. I wanted people to think about
> the problem from the opposite perspective. (05)
I for one am not yet sure what this other perspective is, however.
>
> The idea undecidability expresses a "limit of computation" only makes
> sense from the point of view of a theory within which a "decision" is
> valid. Without a theory, you cannot have "decidability". (06)
Im not sure what you mean by 'theory' here, but the notion of
undecideability seems fairly well-defined already. But perhaps
rf:undecideability has a different meaning. (07)
>
> Looked at from the other perspective, from the point of view of the
> computation, (08)
"point of view of the computation" ?? Can a computation be said to
have a point of view? If you mean, using the ideas of computation
theory, that is exactly what the standard notion does. (09)
> it is the idea of theory which is limited. From this
> perspective "undecidability" becomes what Wolfram calls "computational
> irreducibility".
>
> For instance the halting problem might be seen as the "theory" that a
> program either halts or it doesn't. (010)
No, that is simply a tautology. (011)
> Well, Turing tells us that in
> general this is unknowable, in finite time. (012)
Not exactly. Many programs' halting is completely knowable. The program (013)
begin
L: goto L;
end (014)
does not halt, for example, and this is knowable. Turing's result is
that there is no *single* program which can determine the termination
of *all* programs. (015)
> That's just a fact about
> the world. (016)
True. (017)
> Does this then mean computation has failed? No (018)
Um... did anyone every say that it meant that? It does mean that
computation has certain limits on what it can do. I don't myself think
they are very important or significant limits, but they do have some
philosophical implications that some folk have found important. Some
people for example have argued that this shows that computers can
never match human abilities, but these arguments are flawed [1] (019)
> , the way to
> understand this is not to say that computation is unable to provide an
> answer, the way to understand it is to say that the question
> halting/not halting may not make sense. (020)
Oh, but it *does* make sense. As a matter of fact, it is true of every
program either that it halts or that it does not halt. This is another
fact about the world. (021)
> Absolute knowledge of halting
> or not halting is not a valid theory of the world. (022)
Universal *knowledge* , at least computably defined, is not possible.
But for every program, either it halts or it does not. In fact, it
does not follow from Turing even that this is impossible to determine;
only that there is no *single* method which works for all programs.
But there may be an infinite sequence of halt-detection methods, such
that for any program P at all, there is a method in the sequence which
determines the halting of P. But there cannot be a single program that
generates this sequence. (023)
>
> It is a bit like quantum mechanics. QM "fails" to tell us whether we
> should think of light as a wave or a particle. (024)
It (well, the Copenhagen interpretation) tells us that we *must* think
of every physical thing on *both* ways. (025)
> But is this a "limit of
> quantum mechanics" (by analogy with the "limit of computation")? No, (026)
Again, did anyone ever suggest it was? Or that these might be analogous? (027)
> we just have to come to terms with the reality light is both. What is
> wrong is the question itself. The either/or wave or particle theory is
> not a valid model of the world (in general.)
>
>> See ya. I'm done trying to help.
>
> Thanks for participating. At least you are willing to express the
> traditional point of view, which helps put the solution in context. (028)
So far, I havn't seen any other point of view expressed, nor do I know
what the solution is, not what it is supposed to be a solution to, ie
what the problem is supposed to be. (029)
Pat Hayes (030)
[1] Laforte, Hayes & Ford, Why Godel's Theorem cannot refute
computationalism. http://www.ihmc.us/users/phayes/Pub/LaforteHayesFord.pdf (031)
>
> -Rob
>
> _________________________________________________________________
> Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
> Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
> Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
> Shared Files: http://ontolog.cim3.net/file/
> Community Wiki: http://ontolog.cim3.net/wiki/
> To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
> To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx
>
> (032)
------------------------------------------------------------
IHMC (850)434 8903 or (650)494 3973
40 South Alcaniz St. (850)202 4416 office
Pensacola (850)202 4440 fax
FL 32502 (850)291 0667 mobile
phayesAT-SIGNihmc.us http://www.ihmc.us/users/phayes (033)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (034)
|