Re: Turing vs math

From: Juergen Schmidhuber <>
Date: Thu, 4 Nov 1999 11:48:53 +0100

> Step n owns 2^(n-1) initial segments.

Bruno, why are we discussing this? Sure, in finite time you can compute
all initial segments of size n. In countable time you can compute one
real, or a countable number of reals. But each of your steps needs more
than twice the time required by the previous step. Therefore you need
more than countable time to compute all reals.

> Now, could you give me a bitstring which is not generated
> by this countably infinite process ?

Sure. The output of the program "While TRUE print 1" won't
be computed in countable time by your procedure.

Received on Thu Nov 04 1999 - 02:51:07 PST

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