- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Marchal <marchal.domain.name.hidden>

Date: Wed Jul 14 03:30:25 1999

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

Date: Wed Jul 14 03:30:25 1999

Hal wrote:

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:

(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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:06 PST
*