Re: Predictions & duplications

From: Marchal <>
Date: Mon Oct 15 07:51:46 2001

Saibal Mitra wrote:

>John Mikes wrote:
>``.... If you say: a sequence defying all
>rules, then it is not random, it is calculable. You have to consider all
>rules and cut them out.
>If you try to do that then you encounter the famous halting problem.

Exactly. So why not defined random by incompressible by any (universal)
machine (Kolmogorov incompressibility). In similar sense you can prove that
"most" finite and infinite sequence are incompressible.
Here Church Thesis gives some "absolute" epistemological meaning of that
notion of randomnes.

Cf Li and Vitanyi

Received on Mon Oct 15 2001 - 07:51:46 PDT

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