Re: ESSAY: Program length, Omega and Friendliness

From: Philip Goetz (philgoetz@gmail.com)
Date: Mon Feb 27 2006 - 17:02:09 MST


On 2/26/06, Nick Hay <nickjhay@hotmail.com> wrote:
> There's a simple bijection between the positive integers
> and all finite binary strings: take the binary enoding of the integer, and
> remove the initial 1:
>
> 1 1 empty string
> 2 10 0
> 3 11 1
> 4 100 00
> 5 101 01
> . ... ..
>
> Hence, the set of all finite strings is countable (aleph-null). Similar tricks
> can be used for any alphabet.

Oops. I was thinking that the set of all finite binary strings (aleph-null)
had the same cardinality as the set of infinite binary strings (2^aleph-null).

- Phil



This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:56 MDT