**From:** Matt Mahoney (*matmahoney@yahoo.com*)

**Date:** Tue Nov 20 2007 - 10:04:35 MST

**Next message:**Peter de Blanc: "Re: How to make a slave (was: Building a friendly AI)"**Previous message:**John K Clark: "Re: How to make a slave (was: Building a friendly AI)"**Next in thread:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Reply:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**Peter de Blanc: "Re: How to make a slave (was: Building a friendly AI)"**Previous message:**John K Clark: "Re: How to make a slave (was: Building a friendly AI)"**Next in thread:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Reply:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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