From: Peter de Blanc (peter@spaceandgames.com)
Date: Mon Jun 23 2008 - 02:51:21 MDT
William Pearson wrote:
> Complexity is typically taken to be komogorov complexity that is the
> complexity of a program is measured by the shortest program that has
> the same output, There can be infinite programs with the same
> kolmogorov complexity, as you can always just append arbitrarily long
> amounts of garbage to a program that does nothing.
That would be the Kolmogorov complexity of a function, rather than a
program.
The same proof works even if you're interested in functions instead of
programs, because each program in the sequence implements a distinct
function.
- Peter de Blanc
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT