Re: Proportions of Infinity

From: Hal Finney <hal.domain.name.hidden>
Date: Wed, 21 May 2003 11:52:42 -0700

Maybe you can say that programs could be (countably) infinite in length.
I'm not sure it makes sense but it's possible.

However, if you adopt this convention, then I think you can show that
a dovetailer cannot run all programs. It can only run a countable number
of programs since it can only run a countable number of steps. But
if programs are infinitely long, then there are an uncountable number
of programs. There are uncountably infinitely many programs that the
dovetailer never runs.

Hal Finney
Received on Wed May 21 2003 - 15:05:54 PDT