3 ms·

> suppose you’ve set your sights on a less lofty goal than calculating the exact time-bounded Kolmogorov complexity of every possible string — suppose you’re co

> suppose you’ve set your sights on a less lofty goal than calculating the exact time-bounded Kolmogorov complexity of every possible string — suppose you’re content to calculate it approximately, and just for most strings. If there’s an efficient way to do this, Liu and Pass showed, then true one-way functions cannot exist. In that case, all our candidate one-way functions would be instantly breakable, not just in theory but in practice. Wow, this discovery seems to have really deep implications for the limits of artificial general intelligence, but I don’t have quite enough background in the field to make a formal mathematical connection. At first glance, this seems to imply: cryptography or AIXItl, choose one. Anyone working in the field have more insight on this paper’s potential AGI implications?

contravariant 5y ago
Not sure why the intelligence being artificial is needed for these implications? Though I don't really follow you reasoning anyway, you would expect a general intelligence to be able to estimate the exact Kolmogorov complexity of nigh everything?
pas 5y ago
Isn't there other formulations of AGI that don't rely on Solomonoff induction (which relies on Kolgomorov complexity)? Furthermore humans are already general intelligences, and worst case it's possible to do whole brain emulation, and then optimize that.
- ravi-delia 5y ago
  I'm much much more of a pure math than CS person, but I've stopped in on more than a few lectures. The impression I get is that Solomonoff Induction was already an upper bound. This just makes it a strict upper bound (assuming we believe one-way functions exist, which I think we do). It seems fairly intuitive that you wouldn't be able to even approach the peak in reasonable computational time, and I don't think most people working this angle disagreed.

contravariant 5y ago

Not sure why the intelligence being artificial is needed for these implications? Though I don't really follow you reasoning anyway, you would expect a general intelligence to be able to estimate the exact Kolmogorov complexity of nigh everything?

pas 5y ago

Isn't there other formulations of AGI that don't rely on Solomonoff induction (which relies on Kolgomorov complexity)? Furthermore humans are already general intelligences, and worst case it's possible to do whole brain emulation, and then optimize that.

ravi-delia 5y ago
I'm much much more of a pure math than CS person, but I've stopped in on more than a few lectures. The impression I get is that Solomonoff Induction was already an upper bound. This just makes it a strict upper bound (assuming we believe one-way functions exist, which I think we do). It seems fairly intuitive that you wouldn't be able to even approach the peak in reasonable computational time, and I don't think most people working this angle disagreed.