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. (01)
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. (02)
Your argument is that I don't know what I am talking about because I
don't see the problem this way. (03)
My question was of course rhetorical. I wanted people to think about
the problem from the opposite perspective. (04)
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". (05)
Looked at from the other perspective, from the point of view of the
computation, it is the idea of theory which is limited. From this
perspective "undecidability" becomes what Wolfram calls "computational
irreducibility". (06)
For instance the halting problem might be seen as the "theory" that a
program either halts or it doesn't. Well, Turing tells us that in
general this is unknowable, in finite time. That's just a fact about
the world. Does this then mean computation has failed? No, 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. Absolute knowledge of halting
or not halting is not a valid theory of the world. (07)
It is a bit like quantum mechanics. QM "fails" to tell us whether we
should think of light as a wave or a particle. But is this a "limit of
quantum mechanics" (by analogy with the "limit of computation")? No,
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.) (08)
> See ya. I'm done trying to help. (09)
Thanks for participating. At least you are willing to express the
traditional point of view, which helps put the solution in context. (010)
-Rob (011)
_________________________________________________________________
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 (012)
|