Re: Proportions of Infinity

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Wed, 21 May 2003 10:18:22 +0200

At 11:01 21/05/03 +1000, Russell Standish wrote:
>Bruno Marchal wrote:
> > In computability
> > the models
> > (object of semantics, that is one of the logician's approach to the
> > "meanings") are the
> > "real" things, for example the description can be <a program for factorial
> > written in fortran> and
> > the real thing will be the infinite set of couples {(0,1) (1,1) (2,2)
> > (3,6), (4,24), (5,120), ...}.
> >
>
>This is where we make closest contact. There are an uncountable
>infinity of factorial programs written in Fortran. (All the programs
>with junk data after the final "END" statement also count).

To get uncountable number of programs you will need infinite junk
strings behind the final end. OK, if you want, but that's a quite unusual
use of the standard vocabulary ...


>However,
>there is only one meaning (namely {(0,1) (1,1) (2,2) (3,6), (4,24),
>(5,120), ...}). In this case, one can identify the meaning with the
>set of programs producing that output.

Same remark. Note that that set is necessarily non recursive.


>When talking about measure, the measure of a particular program is
>zero (in the space of all programs). However, the measure of the
>meaning is not - it turns out to be approximately 2^{-K(x)} where K is
>the Kolmogorov complexity of the program x. (Result of the coding
>theorem).
>
>I agree that in some sense the program x is a finite object, and the
>meaning is infinite, but that is irrelevant to the discussion of measure.

I am not convinced. It certainly depends on which hypothesis we make.

Bruno
Received on Wed May 21 2003 - 04:27:19 PDT