Re: Countable vs Continuous
No - the set of computable numbers does not form a
continuum. Continuity is related to the concept of limits: {x_i} is a
convergent sequence if
\forall \epsilon0, \exist N: |x_i-x_N|\epsilon.
A continuous space is one for which every convergent sequence
converges to a limit, ie
\exists x: \forall\epsilon0\exists N: |x_i-x|\epsilon \forall iN.
we commonly denote x by lim_{i-\infty}x_i.
There are many convergent sequences x_i whose limits cannot be
computed (uncountably many, in fact).
However, my point has always been that the set of computable numbers
is not a discrete set, since between any two computable numbers, a
third can be found. This property is true of the rationals as well.
What should be chucked in the rubbish bin is the concept that only
discrete or continuous universes can exist - obviously other
mathematical structures exist, and I believe we happen to be living in
one.
Cheers
Brent Meeker wrote:
On 22-Jun-01, [EMAIL PROTECTED] wrote:
or continous. Don't the computable numbers form a continuum; hence
even restricting the universe to one we can describe would still
allow it to be continuous?
Brent Meeker
No, the computable numbers do not form a continuum - there are not
more than countably many of them. Any real number computable in the
limit (such as Pi) has a finite nonhalting program; the set of all
such programs cannot have higher cardinality than the integers.
Juergen Schmidhuber
http://www.idsia.ch/~juergen/
http://www.idsia.ch/~juergen/everything/html.html
http://www.idsia.ch/~juergen/toesv2/
Thanks for the reply, Juergen. I guess I didn't phrase my question
right. I know that the cardinality of the computable numbers is the
same as the integers. What I was asking was whether the computable
numbers form a continuum in the topological sense (I'm pretty sure they
do) - AND - is this a sufficient continuum to provide a model of
continuous space-time? Again, I think it is - but I don't know of a
proof one way or the other.
Brent Meeker
Dr. Russell Standish Director
High Performance Computing Support Unit, Phone 9385 6967
UNSW SYDNEY 2052 Fax 9385 6965
Australia[EMAIL PROTECTED]
Room 2075, Red Centrehttp://parallel.hpc.unsw.edu.au/rks
Re: Introduction (Digital Physics)
Joel: It seems to me there is a great deal more information in PI than just the 2 bytes it takes to convey it in an email message. Russell: Not much more. One could express pi by a short program - eg the Wallis formula, that would be a few tens of bytes on most Turing machines. Even expressing it as a pattern on your beloved CA, it would probably not consume more that a few hundred bytes. Yes, I see. Juergen pointed this out too, and I think it's a valid point to make the distinction between different representations of the same mathematical object. You are both correct - Pi can in fact be represented nicely (as a program) in a finite way. But I don't dispute this, as I wasn't talking about the finite representation. I was talking about the infinite process / function that pi represents. Maybe this is obvious, but my whole point is that we are fooling ourselves if we think we can compute physics using expressions that consume infinite resources (memory, or computing time). Yes, I understand that the universe as a whole may grow without bound (infinite history), but at any given moment, it must be a finite size. Otherwise we can't compute it! For example, if somehow the universe requires computations like the following: x = 0 do x = x + pi() print x loop Then we are doomed. We cannot run this kind of program. Yes, I know we can find a finite representation like this: x = 0 do x = x + 1 print x; pi loop But does this REALLY make use of the details of pi? I don't think so. I'm simply trying to get people to confront the truth that we humans are incapable of devising Theories of Everything that are NOT run on a universal computer. That's all. Many will say, Of course! We know that!. And then they go on, as if nothing happened, talking about the probabilities of items in infinite sets, and independent tosses of a fair coin, and quantum indeterminacy, and the continuum of the real numbers, as if these things exist! If we cannot program it... it's not a Theory of EVERYTHING. It's just a description. Let us take the realist approach and focus on the things we can actually compute fully. Joel
Re: Introduction (Digital Physics)
Joel Dobrzelewski wrote: And please explain for me how this calculation involved the continuum or infinite binary expansion of the symbol pi in any meaningful way. Sorry, missed getting in this riposte in the last post. What does a binary expansion have to with the calculation .1 * 10 = 1? (I am assuming the usual decimal base convention). Binary representations are no more real than pencil marks on a paper. As far as the continuum is concerned, calculations involving pi do not involve the continuum. There is a whole lot of mathematics in between the discrete and the continuous (pretty much all of it I'm afraid!). Cheers Dr. Russell Standish Director High Performance Computing Support Unit, Phone 9385 6967 UNSW SYDNEY 2052 Fax 9385 6965 Australia[EMAIL PROTECTED] Room 2075, Red Centrehttp://parallel.hpc.unsw.edu.au/rks
Re: Introduction (Digital Physics)
Joel Dobrzelewski wrote: Ok, sorry for being a smart-ass. Instead of baiting the discussion to make my point, I'll try to simply state the position clearly. We humans cannot deal with infinite structures, like pi. Numbers like pi and e and Omega and all the others are the devil! :) And we all know the devil is in the details... I think I made it obvious that pi and e are pretty simple objects, and humans are quite capable of dealing with them (OK maybe not all humans :). Omega, on the other hand, is quite a different beast again! We carry them along in our mathematics all the way to the end so that they can be evaluated in the final step. But I ask you: When does the universe evaluate its expressions? AFAIC, this is a meaningless question. ... Dr. Russell Standish Director High Performance Computing Support Unit, Phone 9385 6967 UNSW SYDNEY 2052 Fax 9385 6965 Australia[EMAIL PROTECTED] Room 2075, Red Centrehttp://parallel.hpc.unsw.edu.au/rks
Re: Introduction (Digital Physics)
Hello again Joel. I think I can agree with you, in a pragmatic sense, with what you state below. I agree that any useful TOE should be able to be implemented on a (large enough) computer. This computation can then SIMULATE the relevant or important aspects of the universe we observe, or all aspects of other possible universes, with their APPARENT real-number continua and infinite sets. Godel's theorem prevents us from simulating all aspects of our universe. Adopting that perspective, we should be able to justify that a simulation of our universe does not appear overly fine-tuned. At least that would suit my aesthetic tastes. Fred I'm simply trying to get people to confront the truth that we humans are incapable of devising Theories of Everything that are NOT run on a universal computer. That's all. Many will say, Of course! We know that!. And then they go on, as if nothing happened, talking about the probabilities of items in infinite sets, and independent tosses of a fair coin, and quantum indeterminacy, and the continuum of the real numbers, as if these things exist! If we cannot program it... it's not a Theory of EVERYTHING. It's just a description. Let us take the realist approach and focus on the things we can actually compute fully. Joel
Re: Introduction (Digital Physics)
Joel Dobrzelewski wrote: But I don't dispute this, as I wasn't talking about the finite representation. I was talking about the infinite process / function that pi represents. Maybe this is obvious, but my whole point is that we are fooling ourselves if we think we can compute physics using expressions that consume infinite resources (memory, or computing time). Yes, I understand that the universe as a whole may grow without bound (infinite history), but at any given moment, it must be a finite size. Otherwise we can't compute it! Yes - I understand that is your point of view, as it is also that of Hal Ruhl's. It is not shared by the majority - eg myself, Juergen or Bruno. To be quite frank, whether something can be computed using 32 bit integers, or IEEE floating point numbers or not is rather irrelevant to fundamental theories of reality. This is why Juergen's all possible descriptions approach has more legs. As an instance of the sort of problems you face, the number 0.1 can be represented as a finite string in base 10, but cannot be represented as a finite binary string (floating point number). Is 0.1 a valid number then? Unless you completely do the Kronecker thing, or course Dr. Russell Standish Director High Performance Computing Support Unit, Phone 9385 6967 UNSW SYDNEY 2052 Fax 9385 6965 Australia[EMAIL PROTECTED] Room 2075, Red Centrehttp://parallel.hpc.unsw.edu.au/rks
Re: Countable vs Continuous
Obviously, what you're looking for is some kind of counter example. I
think the problem lies in not being able to determine at any point of
the calculation just how many digits of the limit you have found. For
the counterexample what we need is a computable series, which we know
converges, yet we cannot compute the limit.
Perhaps the more mathematically nimble might try the following example
x_i = \sum_{j=0}^i 1/p_j, where p_j is the jth prime number. I suspect
this is a convergent sequence, yet converges too slowly to compute the
limit.
Cheers
Brent Meeker wrote:
On 25-Jun-01, Russell Standish wrote:
No - the set of computable numbers does not form a
continuum. Continuity is related to the concept of limits: {x_i} is a
convergent sequence if
\forall \epsilon0, \exist N: |x_i-x_N|\epsilon.
A continuous space is one for which every convergent sequence
converges to a limit, ie
\exists x: \forall\epsilon0\exists N: |x_i-x|\epsilon \forall iN.
we commonly denote x by lim_{i-\infty}x_i.
There are many convergent sequences x_i whose limits cannot be
computed (uncountably many, in fact).
Thanks for the education vis a vis definition of a continuum, but now I
don't see why the computable numbers don't form a continuum. Suppose
a0,a1,a2,...ai,... is a convergent sequence of computable numbers with
limit A. Then it seems that A must be a computable number since given
any number of decimal places (or bits) n there is a value of i=m such
that am is equal to A for the first n places and the digits in those
places will not change for all im. Isn't this the definition of a
computable number - one whose representation can be computed to a given
accuracy in a finite number of steps? So the computability of the
sequence ai entails computability of the sequences limit.
thnx, Brent Meeker
I am very interested in the Universe - I am specializing in the
Universe and all that surrounds it.
--- Peter Cook
Dr. Russell Standish Director
High Performance Computing Support Unit, Phone 9385 6967
UNSW SYDNEY 2052 Fax 9385 6965
Australia[EMAIL PROTECTED]
Room 2075, Red Centrehttp://parallel.hpc.unsw.edu.au/rks
Re: Countable vs Continuous
On 25-Jun-01, Russell Standish wrote:
Obviously, what you're looking for is some kind of counter example. I
think the problem lies in not being able to determine at any point of
the calculation just how many digits of the limit you have found.
OK, I can understand that. In order for a number to be considered
computable not only must there be an index m beyond which the the first
n places don't change, but we must be able to put a bound on m as a
function of n.
For
the counterexample what we need is a computable series, which we know
converges, yet we cannot compute the limit.
Perhaps the more mathematically nimble might try the following example
x_i = \sum_{j=0}^i 1/p_j, where p_j is the jth prime number. I suspect
this is a convergent sequence, yet converges too slowly to compute the
limit.
I don't think that's a counterexample, as Euler proved the sequence to
diverge (although *very* slowly).
Brent Meeker
Cheers
Brent Meeker wrote:
On 25-Jun-01, Russell Standish wrote:
No - the set of computable numbers does not form a continuum.
Continuity is related to the concept of limits: {x_i} is a
convergent sequence if
\forall \epsilon0, \exist N: |x_i-x_N|\epsilon.
A continuous space is one for which every convergent sequence
converges to a limit, ie
\exists x: \forall\epsilon0\exists N: |x_i-x|\epsilon \forall iN.
we commonly denote x by lim_{i-\infty}x_i.
There are many convergent sequences x_i whose limits cannot be
computed (uncountably many, in fact).
Thanks for the education vis a vis definition of a continuum, but now
I don't see why the computable numbers don't form a continuum.
Suppose a0,a1,a2,...ai,... is a convergent sequence of computable
numbers with limit A. Then it seems that A must be a computable
number since given any number of decimal places (or bits) n there is
a value of i=m such that am is equal to A for the first n places and
m. Isn't this
the definition of a computable number - one whose representation can
be computed to a given accuracy in a finite number of steps? So the
computability of the sequence ai entails computability of the
sequences limit.
thnx, Brent Meeker
I am very interested in the Universe - I am specializing in the
Universe and all that surrounds it.
--- Peter Cook
Dr. Russell Standish Director High Performance Computing Support Unit,
Phone 9385 6967 UNSW SYDNEY 2052 Fax 9385 6965 Australia
[EMAIL PROTECTED] Room 2075, Red Centre
http://parallel.hpc.unsw.edu.au/rks
Regards
