|
|
Tim Peters wrote:
...
[Proginoskes]
...
The computer science definition is: A(n infinite) sequence is random
if no algorithm can generate the sequence. Since there are
only countably many algorithms, that means that over 99% of the
sequences are random. (You can replace 99 with any integer < 100.)
[Eric Gisse]
Why is the number of algorithms countable as opposed to uncountable?
Yes, I know the difference between 'countable' and 'uncountable'.
It's for the same reason that the set of all possible books in any given
human language is countable: the set of all finite strings composed of
symbols from a finite alphabet is countable. An algorithm has to be
/specified/ somehow, right? Whether you pick English or a formalism like
Turing machines, all possible finite strings from the alphabet you pick are
countable. If you allow algorithm specifications of infinite length, you
can worm around that -- but then few would agree that you're still talking
about what /they/ mean by "algorithms".
[ about formalizations of the algorithm concept ... ]
If I remember correctly, the first formalizations of the
concept of "effect procedure" were arrived at in the 1930's.
One was Turing's idea of TM's . Another was the lambda-calculus.
Yet another was defining the recursive functions from N^k -> N
inductively, starting with functions admitted at the start, and
using a few rules operating on recursive functions that, by
definition, give possibly new recursives.
According to Wikipedia, it was Stephen Kleene who first
formulated the "Church–Turing thesis" :
``Every effectively computable function can be
computed by a Turing machine."
http://en.wikipedia.org/wiki/Church-Turing_thesis
David Bernier
|
|