Infinite length computer programs

From: Russell Standish <>
Date: Mon, 26 May 2003 09:19:36 +1000 (EST)

Before this thing gets totally out of context, may I remind
participants that we are talking about infinite length strings called
"descriptions" in the Schmidhuber ensemble. These descriptions may be
fed into a Turing Machine, where they become programs. There is a 1-1
correspondence between these and real numbers, as can be seen by
expanding real numbers in binary expansion.

The more usual program we're used to is of finite length, and
corresponds to a set of infinite length programs having the same
prefix. These sets have positive measure 2^{-\ell} where \ell is the
length of the program.


Jean-Michel Veuillen wrote:
> >This is where we make closest contact. There are an uncountable
> >infinity of factorial programs written in Fortran.
> I can spot a mistake here: There is a one to one correspondance between
> computer programs and integers. Think of a computer program as another way
> of writing an integer, in another base.
> Jean-Michel Veuillen

A/Prof Russell Standish Director
High Performance Computing Support Unit, Phone 9385 6967, 8308 3119 (mobile)
UNSW SYDNEY 2052 Fax 9385 6965, 0425 253119 (")
Room 2075, Red Centre
            International prefix +612, Interstate prefix 02
Received on Sun May 25 2003 - 19:24:04 PDT

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