From: Matt Mahoney (matmahoney@yahoo.com)
Date: Tue Nov 20 2007 - 10:04:35 MST
Legg proved in http://www.vetta.org/documents/IDSIA-12-06-1.pdf that there is
a (fairly small) level of complexity beyond which theorems cannot be proved,
i.e. Godel incompleteness in ubiquitous. Likewise, Wolfram's principle of
computational equivalence (
http://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html ) argues
empirically that beyond some (fairly small) level of complexity, that all
processes are equivalent to universal Turing machines (thus, the halting
problem is undecidable). Are these assertions equivalent, in the same sense
that Godel incompleteness is equivalent to the halting problem? Did Legg
prove Wolfram's assertion? It seems that Legg and Wolfram arrived at the same
conclusion independently, as neither cites the other's work as far as I know.
The question came up while I was considering theoretical lower bounds on the
complexity of self improving intelligence. It seems to me that Turing
completeness would be sufficient, possibly a few hundred bits. This would be
a quicker (but possibly more dangerous) path to a singularity than superhuman
intelligence. I am trying to understand the risk, and why it has happened
only once in the last 3 billion years.
-- Matt Mahoney, matmahoney@yahoo.com
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:00 MDT