Re: does sqrt(2) exist in CM?

• Previous message: tchow_at_lsa.umich.edu: "Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?"
• In reply to: Joe Kearney: "Re: does sqrt(2) exist in CM?"
• Next in thread: Keith Ramsay: "Re: does sqrt(2) exist in CM?"
• Reply: Keith Ramsay: "Re: does sqrt(2) exist in CM?"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: 09 Feb 2005 00:47:46 GMT

In article <1107906538.502021.290660@o13g2000cwo.googlegroups.com>,
Joe Kearney <joek350@gmail.com> wrote:
>Daniel W. Johnson wrote:
>> The un-representable real numbers are a proper subset of the
>> uncomputable real numbers.
>
>does this imply that there exist uncomputable numbers we can represent,
>or have i still missed the point of uncomputability? can you exhibit an
>uncomputable number?

The usual term here is "define" rather than "represent." (We also have to
be slightly careful how we use the word "define" lest we run into paradoxes
like the least number not definable with fewer than 100 words, but I'll be
lax about this.)

We can define uncomputable numbers; there are only countably many Turing
machines so there can only be countably many computable numbers. List
them all and then mutate the diagonal to get an uncomputable number.
I've just explained what this number is, so it's definable (I just
defined it).

Whether I've "exhibited" this number may be debatable. It's something
of a matter of opinion whether a particular definition or description is
sufficiently "explicit" to count as "exhibiting" the number or whether it
is merely a "nonconstructive existence proof."

Computability has to do more with whether you can calculate arbitrarily
accurate finite approximations to a number. This is a stronger
requirement than simply requiring you to pin the number down with a
verbal description (using whatever mathematical terminology you have at
your disposal).

-- 
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences

• Previous message: tchow_at_lsa.umich.edu: "Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?"
• In reply to: Joe Kearney: "Re: does sqrt(2) exist in CM?"
• Next in thread: Keith Ramsay: "Re: does sqrt(2) exist in CM?"
• Reply: Keith Ramsay: "Re: does sqrt(2) exist in CM?"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]