Re: [sl4] Is there a model for RSI?

From: Peter de Blanc (
Date: Mon Jun 23 2008 - 00:42:24 MDT

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. 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

> All that aside, your assertion is contrary to some pretty rudimentary
> (for this list) theorems in mathematics.

So show us these alleged theorems.

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT