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
