| |
 |
|
|
Science Forum Index » Logic Forum » Cardinality of Set of Computable Numbers?
Page 1 of 5 Goto page 1, 2, 3, 4, 5 Next
|
| Author |
Message |
| Russell Easterly |
 Posted: Thu Dec 25, 2003 7:32 pm |
|
|
|
Guest
|
As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
d is a computable number not in S.
Therefore, S can't be the set of computable numbers.
Cantor's powerset argument makes things even weirder.
Let S be the set of all computable numbers (countable or uncountable).
Let P(S) be the powerset of S. Cantor proves |S| < |P(S)|.
This means that P(S) contains members that are not in S.
These members must be noncomputable numbers.
In fact, nearly all members of P(S) are noncomputable.
So, the set of all computable numbers can't exist if
it is countable and if it is uncountable, most of its
powerset is noncomputable.
What am I missing?
Russell
- the universe is one dimensional |
|
|
| Back to top |
|
| Arturo Magidin |
| Posted: Thu Dec 25, 2003 7:32 pm |
|
|
|
Guest
|
In article <b6adnV6Pvd8vHHai4p2dnA@comcast.com>,
Russell Easterly <logiclab@comcast.net> wrote:
Quote: As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
I don't really see how to do this. Do you know that every computable
number has an infinite number of digits? If not, how do you know that
f^{-1}(j) (i.e., the j-th computable number) has at least j digits, so
that you can define a new number whose j-th digit is different from
the j-th digit of f^{-1}(j)?
Quote: d is a computable number not in S.
Therefore, S can't be the set of computable numbers.
Cantor's powerset argument makes things even weirder.
Let S be the set of all computable numbers (countable or uncountable).
Let P(S) be the powerset of S. Cantor proves |S| < |P(S)|.
This means that P(S) contains members that are not in S.
These members must be noncomputable numbers.
Actually, ALL members of P(S) are not computable numbers, since the
elements of P(S) are not numbers at all: they are sets of numbers.
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
magidin@math.berkeley.edu |
|
|
| Back to top |
|
| Lee Rudolph |
| Posted: Thu Dec 25, 2003 7:39 pm |
|
|
|
Guest
|
"Russell Easterly" <logiclab@comcast.net> writes:
Quote: As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
d is a computable number not in S.
To correctly conclude that "d is a computable number not in S"
by "Using f()", you would have to know that f is a computable
function (in, essentially, whatever sense you are using
"computable" in the phrase "computable numbers").
either
Quote: S can't be the set of computable numbers
or f isn't computable. Correct conclusion: no such f is
computable.
Lee Rudolph |
|
|
| Back to top |
|
| Chan-Ho Suh |
| Posted: Thu Dec 25, 2003 7:50 pm |
|
|
|
Guest
|
In article <b6adnV6Pvd8vHHai4p2dnA@comcast.com>, Russell Easterly
<logiclab@comcast.net> wrote:
Quote: As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
d is a computable number not in S.
Why is that? Can you exhibit a Turing machine to compute d?
In other words, you need a finite rule to compute this d. I don't
think you're going to find one.
Quote: Therefore, S can't be the set of computable numbers.
[...] |
|
|
| Back to top |
|
| James Waldby |
| Posted: Thu Dec 25, 2003 8:26 pm |
|
|
|
Guest
|
Lee Rudolph wrote:
Quote: "Russell Easterly" <logiclab@comcast.net> writes:
....
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
d is a computable number not in S.
To correctly conclude that "d is a computable number not in S"
by "Using f()", you would have to know that f is a computable
function (in, essentially, whatever sense you are using
"computable" in the phrase "computable numbers").
Therefore,
either
S can't be the set of computable numbers
or f isn't computable. Correct conclusion: no such f is
computable.
I don't agree that that is the problem per se. What is wrong
is that d is not well-defined, ie, not shown to exist. It is
not good enough to merely say "define a diagonal number, d".
If d is based on, for example, digit j of f(j), the process
will fail by f(j) having fewer than j digits, which is the case
for most computable numbers, expressed in any base.
-jiw |
|
|
| Back to top |
|
| fishfry |
| Posted: Thu Dec 25, 2003 9:10 pm |
|
|
|
Guest
|
In article <b6adnV6Pvd8vHHai4p2dnA@comcast.com>,
"Russell Easterly" <logiclab@comcast.net> wrote:
Quote: As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
47
12
487384
4738
74858587
343434
387498394838493
....
This is a countable list containing all computable numbers. Exactly
what do you mean by the diagonal number? Do you mean a natural number
whose n-th digit is different from the n-th digit of n-th member of the
list? It seems that the diagonal has a digit in EVERY n-th place, and
is therefore not even a natural number.
Can you clarify your argument to explain what you mean by the diagonal
number defined by the order f?
Even if you are talking about computable reals, say between 0 and 1, you
can then define a diagonal (an infinite decimal) but how do you know
that diagonal number is computable? What rule generates it? You don't
know, because you haven't made f explicit. You can't, because there are
in fact an uncountable number of possible f's.
That's because there are uncountably many bijections from N to N. |
|
|
| Back to top |
|
| Dik T. Winter |
| Posted: Thu Dec 25, 2003 9:12 pm |
|
|
|
Guest
|
In article <b6adnV6Pvd8vHHai4p2dnA@comcast.com> "Russell Easterly" <logiclab@comcast.net> writes:
Quote: As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
d is a computable number not in S.
You are using that 'd' is computable, but for 'd' to be computable,
'f' should be computable. But 'f' is not computable, so 'd' is not
computable.
Losely said, a number is computable if there is a finite algorithm
that delivers that number. The number of finite algorithms is
countable, so the number of computable numbers is countable. But you
can not say for all finite algorithms in finite time whether they
deliver a number or do not stop. So there always remain algorithms
for which you do not know whether they must be in the list or not.
The conclusion is that you can not compute the list.
So, using your 'f' (which is not computable) you get a 'd' (which
is also not computable).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ |
|
|
| Back to top |
|
| Russell Easterly |
| Posted: Thu Dec 25, 2003 10:16 pm |
|
|
|
Guest
|
"Chan-Ho Suh" <suh@math.ucdavis.nospam.edu> wrote in message
news:251220031650055558%suh@math.ucdavis.nospam.edu...
Quote: In article <b6adnV6Pvd8vHHai4p2dnA@comcast.com>, Russell Easterly
logiclab@comcast.net> wrote:
As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
d is a computable number not in S.
Why is that? Can you exhibit a Turing machine to compute d?
Good question. I need to define what computable means.
Quote: In other words, you need a finite rule to compute this d. I don't
think you're going to find one.
Maybe not.
Let a computable number be defined as the unbounded, but finite output tape
of a TM. Assume that each TM can be represented by a unique natural number.
Since the number of TMs is countable, there must be a countable number of
comptable numbers.
We need to define the output tapes more precisely.
Each output tape is unbounded, but finite and every position
not written to by the TM is initially set to zero.
Define the ordered set S as the set of numbers defined by
S(i) = output of TM(i).
Let d be the diagonal number.
To compute d(i) take the ith position of S(i):
If it is equal to 0 then d(i) = 1 else d(i) = 0.
Can d can be written to an unbounded, but finite output tape?
Probably not. The length of d is the largest i.
Is the set of natural numbers a set of computable numbers?
It seems computability implies countability,
but countability does not imply computability.
Russell
- Merry Xmas |
|
|
| Back to top |
|
| |-|erc |
| Posted: Fri Dec 26, 2003 1:37 am |
|
|
|
Guest
|
----------------------------- <^> <(·¿·)> <^> -----------------------------
"Arturo Magidin" <magidin@math.berkeley.edu> wrote in
Quote: In article <b6adnV6Pvd8vHHai4p2dnA@comcast.com>,
Russell Easterly <logiclab@comcast.net> wrote:
As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
I don't really see how to do this. Do you know that every computable
number has an infinite number of digits? If not, how do you know that
f^{-1}(j) (i.e., the j-th computable number) has at least j digits, so
that you can define a new number whose j-th digit is different from
the j-th digit of f^{-1}(j)?
d is a computable number not in S.
Therefore, S can't be the set of computable numbers.
Cantor's powerset argument makes things even weirder.
Let S be the set of all computable numbers (countable or uncountable).
Let P(S) be the powerset of S. Cantor proves |S| < |P(S)|.
This means that P(S) contains members that are not in S.
These members must be noncomputable numbers.
Actually, ALL members of P(S) are not computable numbers, since the
elements of P(S) are not numbers at all: they are sets of numbers.
How about a simple practical halt test on each number to a finite number of
digits, such that each has enough digits to make the diagonal.
Here is the raw computable list after x computations of a parallel UTM.
1 1 1
2 2 2 2 2
3 3
4
5 5 5 5 5 5 5 5
The 'partly computable' list is constructed incrementally from that :
1 1 1
2 2 2 2 2
3 5 5 5 5 5 5 5
This guarantees a list of effectively computable numbers. Admitedly a large
portion of processor time will be shared on non halting functions but the
well behaved functions are still guaranteed to terminate with suitable processor
scheduling.
Herc |
|
|
| Back to top |
|
| Stephen Montgomery-Smith |
| Posted: Fri Dec 26, 2003 3:27 am |
|
|
|
Guest
|
Russell Easterly wrote:
Quote: As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
d is a computable number not in S.
Therefore, S can't be the set of computable numbers.
The problem is that there is no function f, as you describe, that is computable.
Why? Well, you just provided the proof.
In fact, you have provided a rather roundabout way of proving Turing's halting
theorem (because there is an 'obvious' way to try to make a computable f - e.g.
interprete the number as a computer program in ASCII code, and run that program). |
|
|
| Back to top |
|
| Ahto Truu |
| Posted: Fri Dec 26, 2003 6:24 am |
|
|
|
Guest
|
Quote: Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
I don't really see how to do this. Do you know that every computable
number has an infinite number of digits? If not, how do you know that
f^{-1}(j) (i.e., the j-th computable number) has at least j digits, so
that you can define a new number whose j-th digit is different from
the j-th digit of f^{-1}(j)?
This is really not a problem. Any integer (representation in any base)
can be zero-padded from left to ensure it really has at least j digits.
Of course, the mere existance of d does not make it computable, still.
Ahto |
|
|
| Back to top |
|
| Chan-Ho Suh |
| Posted: Fri Dec 26, 2003 11:16 am |
|
|
|
Guest
|
In article <lpmdnYv-KIWGNXaiRVn-hQ@comcast.com>, Russell Easterly
<logiclab@comcast.net> wrote:
Quote: "Chan-Ho Suh" <suh@math.ucdavis.nospam.edu> wrote in message
news:251220031650055558%suh@math.ucdavis.nospam.edu...
In article <b6adnV6Pvd8vHHai4p2dnA@comcast.com>, Russell Easterly
logiclab@comcast.net> wrote:
As often happens, I have managed to confused myself.
Any enlightenment will be appreciated.
I have read that the set of computable numbers is countable.
Let S be the set of all computable numbers
and assume S is countable.
Since S is countable there is a function, f(),
that maps S to the natural numbers.
Using f() to order S, define a diagonal number, d.
d is a computable number not in S.
Why is that? Can you exhibit a Turing machine to compute d?
Good question. I need to define what computable means.
In other words, you need a finite rule to compute this d. I don't
think you're going to find one.
Maybe not.
Let a computable number be defined as the unbounded, but finite output tape
of a TM. Assume that each TM can be represented by a unique natural number.
Since the number of TMs is countable, there must be a countable number of
comptable numbers.
Your conclusion is right, but your definition of computable needs work.
See below.
Quote: We need to define the output tapes more precisely.
Each output tape is unbounded, but finite and every position
not written to by the TM is initially set to zero.
Here's the way Turing did it: every square on the tape is initially
blank. The TM outputs 0s and 1s (and possibly other symbols, which we
regard as 'garbage'). Any number between zero and one is called
computable if there's a TM that starts with a blank tape and produces
the binary expansion of the number (disregarding any garbage produced).
This binary expansion is culled from the subsequence of the sequence of
moves that produces 0s and 1s, so the 0s and 1s don't need to be
printed out in the right order on the tape and actually the TM may
overwrite some of the previously produced 0s and 1s.
In general a computable number is one that differs by an integer from
such a computable number between one and zero.
Important point: a number with terminating binary expansion may be
computed by a TM that *does NOT halt*.
Quote: Define the ordered set S as the set of numbers defined by
S(i) = output of TM(i).
Let d be the diagonal number.
To compute d(i) take the ith position of S(i):
If it is equal to 0 then d(i) = 1 else d(i) = 0.
Can d can be written to an unbounded, but finite output tape?
Probably not. The length of d is the largest i.
Hmm...I'm not getting what you're saying. 'i' seems to be the way you
are indexing the TMs. So what do you mean by largest 'i'? Of course,
d is likely to be some irrational number and have infinite length, but
that's not why it's not computable.
The point is that a TM that computes d, according to your scheme, must
first output S(i) to enough digits -- the i'th digit to be precise, in
order to figure out the i'th digit of d-- or *halt* after a certain
point before reaching the i'th digit so that you know the rest of the
digits are zero. So picture this: your TM starts computing S(i), but
maybe it takes a long time to get to the i'th digit; in any case you
get it eventually. But the TM may chug on, i.e. it is a non-halting
TM! Now of course, since this TM is really like a "sub"-TM of the one
that computes d, you may say you'll just arrange it so that as part of
the computing of d, you figure out if TM(i) halts or not. Well, now
you (hopefully) see the difficulty involved.
Actually, I dug out Turing's paper on computable numbers since my
curiosity was piqued, and I'm struck by how readable it still seems.
In fact, your very question is addressed! Since it seems you are not
operating with a text, I suggest getting a copy of the paper; it's not
only clear but has some of the most fundamental concepts of TMs in a
fairly short form. It should be available at your university library.
A.M. Turing, "On Computable Numbers, with an Application to the
Entscheidungsproblem.", Proceedings of the London Mathematical Society,
vol 42 (1936) p. 230-265.
Quote: Is the set of natural numbers a set of computable numbers?
Yes. I can compute them pretty easily ;-)
Just remember that Turing's definition of computable number is a fairly
natural one. It includes basically everything you would think of as
'computable' and even probably some more.
Quote: It seems computability implies countability,
but countability does not imply computability.
I'm not sure what you're saying here. Of course we can always take a
countable set of uncomputable numbers.
Quote: Russell
- Merry Xmas
Happy Holidays. |
|
|
| Back to top |
|
| George Greene |
| Posted: Fri Dec 26, 2003 3:21 pm |
|
|
|
Guest
|
"Russell Easterly" <logiclab@comcast.net> writes:
: Let S be the set of all computable numbers
: and assume S is countable.
What kinds of numbers are we talking about here?
Rational? Real? Complex? Supernatural? Infinitesimal?
--
---
"It's difficult ... you need to be united to have any
strength, but internal issues have to be addressed."
--- E. Ray Lewis, on liberalism in America |
|
|
| Back to top |
|
| George Greene |
| Posted: Fri Dec 26, 2003 3:33 pm |
|
|
|
Guest
|
"Russell Easterly" <logiclab@comcast.net> writes:
: Let a computable number be defined as the unbounded, but finite output tape
: of a TM.
That's possible but it's almost inverting the paradigm.
The number is computable iff the TM says it is. Traditionally,
in order for the TM to say something about the number,
the number has to be the INPUT, NOT the output, of the TM.
TMs are normally thought of as running on their input in order to
answer a question about it.
: Assume that each TM can be represented by a unique natural number.
That does not need to be assumed; that is inherent in the definition of "TM".
: Since the number of TMs is countable, there must be a countable number of
: comptable numbers.
Right.
Why isn't that just The Answer to the original question?
Why didn't knowing this in advance prevent you, in advance,
from asking the original question?
: We need to define the output tapes more precisely.
Far more importantly, you need to define the INPUT tapes
precisely. The output tapes are potentially irrelevant.
The *important* output of a TM is whether it halts
or loops.
: Each output tape is unbounded, but finite and every position
: not written to by the TM is initially set to zero.
The input and output tapes of a TM (viewed as variables, not constants; viewed
as holes, not pegs) are, under the traditional definition, THE SAME (the
same holes; but they can start with some pegs and finish with others).
Since 0 is going to be inescapably needed as a true
data-value in almost anybody's representation of "numbers", You need to pick
some OTHER symbol as your default. Most TM alphabets come with a built-in
designated "null" symbol. When I was in college we spelled that as an upside-down
delta.
: Define the ordered set S as the set of numbers defined by
:
: S(i) = output of TM(i).
TM(i) DOES NOT have a unique well-defined output!
What TM(i)'s output is will VARY depending on what TM(i)'s INPUT was!
Of course, you may, if you insist, make the input every bit as irrelevant
as the output by assuming that it is always null, but you will wind up
with a much bigger uglier collection of TM's to solve whatever problem
you were originally planning to solve.
: Let d be the diagonal number.
: To compute d(i) take the ith position of S(i):
: If it is equal to 0 then d(i) = 1 else d(i) = 0.
It is going to dawn on you in a minute that since i
can take every natural number as a value, and there are infinitely
many of these, you have just defined a d with infinitely many digits.
: Can d can be written to an unbounded, but finite output tape?
: Probably not. The length of d is the largest i.
But there IS NO largest i, OBVIOUSLY.
: Is the set of natural numbers a set of computable numbers?
Of course.
Every natural number is finite and every finite number
has the property that a TM can write it, once you decide on
a digital representation scheme.
--
---
"It's difficult ... you need to be united to have any
strength, but internal issues have to be addressed."
--- E. Ray Lewis, on liberalism in America |
|
|
| Back to top |
|
| George Greene |
| Posted: Fri Dec 26, 2003 3:36 pm |
|
|
|
Guest
|
magidin@math.berkeley.edu (Arturo Magidin) writes:
: I don't really see how to do this. Do you know that every computable
: number has an infinite number of digits? If not, how do you know that
: f^{-1}(j) (i.e., the j-th computable number) has at least j digits, so
: that you can define a new number whose j-th digit is different from
: the j-th digit of f^{-1}(j)?
It's a lot worse than that; he didn't originally know what he meant by
"number"; by itself, "number" is simply too vague.
If he meant "real number" then he really was obligated to SAY that. |
|
|
| Back to top |
|
| |
Page 1 of 5 Goto page 1, 2, 3, 4, 5 Next
All times are GMT - 5 Hours
The time now is Fri Dec 05, 2008 6:40 am
|
|