Hal wrote:
>Actually on further thought I think I was wrong to suggest that the number
>of TM programs is c, since that would allow for infinite length programs,
>which is perhaps outside the spirit of a TM. If we require only finite
>length programs then the number of TMs is aleph 0 since we can enumerate
>all the programs, and that would be the number of universes as well.
>Not so many after all.
Well, I was writing a post on this, but I can put it in the trash now.
Indeed TM are typically finite object, and the number of TM is aleph_0.
Nevertheless I do think that the key notion are computations by TM, and
most of these computations are infinite. If we take into account, for
exemple
that the great programmer dovetail also on the TM + all approximations
of the real (Turing Oracle) then there is a sense in which machines must
take into account the aleph_1 possible continuations.
Having said this I must say that I don't really care about the cardinality
of the MW, if only because numbers like aleph_1 are relative to a model
of set theory.There are typically relative notion. Remember Skolem
paradox,
a set could be uncountable from the point of view of a machine embedded
in a universe, and countable from the point of view of a machine embedded
in a larger universe.
BTW, Hal, I have not understand why you were saying to Jacques M. Mallah
that Kolmogorof's complexity is not machine independant. Precisely:
>However I think there is a worse problem. That is that K. complexity is
>not uniquely defined. K. complexity is defined only with regard to some
>specific universal Turing machine (UTM). Two different UTMs will give a
>different answer for what the K. complexity is of a string or program.
>In fact, given any particular string, you can construct a UTM which gives
>it an arbitrarily large or small K. complexity as measured by that UTM.
(Hal, see
http://www.escribe.com/science/theory/index.html?mID=824)
It seems to me that this would contradict the "invariance theorem" (Li
and Vitanyi page 90seq). Look at the remark page 94-95. Kolmogoroff
complexity does not apply, only for non-standart enumeration of all
partial recursive functions. But these are ad-hoc and are not linked
to universal Turing machine. Most of the whole theoretical computer
science doesn't apply to non standart enumerations.
Bruno
Received on Wed Jul 14 1999 - 03:30:25 PDT