From: J. Andrew Rogers (andrew@ceruleansystems.com)
Date: Mon Jun 23 2008 - 01:18:50 MDT
On Jun 22, 2008, at 11:42 PM, Peter de Blanc wrote:
> J. Andrew Rogers wrote:
>> If your "counter" does not occupy memory then the complexity is
>> constant. If it does occupy memory, it is eating bits as N grows
>> on a finite machine. Either way, you have a problem.
>
> Turing machines have infinite memory.
Either way, you either have an algorithm with constant complexity, or
an algorithm with a complexity that is a function of N. Neither case
is what you are asserting.
> But the argument still works for finite machines:
>
> Let K be the complexity of machine 0. Let M be the number of
> machines of complexity at most K (if complexity is measured in bits,
> that's 2^(k+1)-2). Then somewhere in the set 0...M, there's a
> machine with complexity greater than K. We're only counting up to M,
> so that's pretty finite.
Eh? I'm not following this.
>> All that aside, your assertion is contrary to some pretty
>> rudimentary (for this list) theorems in mathematics.
>
> So show us these alleged theorems.
While it has many expressions in literature (Chaitin has his own
quaint pedestrian expressions of the concept), let us work from the
fact that you are arguing against a trivial consequence of the
Invariance Theorem, which opens Chapter 2 of my copy of Li & Vitanyi.
It is prefaced with the following quote:
"The following 'Invariance Theorem' is the cornerstone for the
subsequent development of the [algorithmic information] theory. In
fact, for many later applications it embodies the entire theoretical
foundation."
This is old territory, so I don't see a reason to rehash it here. You
are failing to grok elementary algorithmic information theory. Li &
Vitanyi is the canonical text for such things, so I would recommend
buying a copy. In any case, it is far too basic to justify dedicating
a thread to it if you do not understand it. There are other AGI
related lists that will gladly humor such things.
Algorithms do not create information, they *are* information.
J. Andrew Rogers
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT