= 27d567bc2d48d9f40e9ccc20ea370b15)
Eliezer_Yudkowsky comments on Who thinks quantum computing will be necessary for AI? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (101)
You don't sound like you're now much less confident you're right about this, and I'm a bit surprised by that!
I got the ladder down so I could get down my copy of Goldreich's "Foundations of Cryptography", but I don't quite feel like typing chunks out from it. Briefly, a pseudorandom generator is an algorithm that turns a small secret into a larger number of pseudorandom bits. It's secure if every distinguisher's advantage shrinks faster than the reciprocal of any polynomial function. Pseudorandom generators exist iff one-way functions exist, and if one-way functions exist then P != NP.
If you're not familiar with PRGs, distinguishers, advantage, negligible functions etc I'd be happy to Skype you and give you a brief intro to these things.
Okay, makes sense if you define "distinguishable from random" as "decodable with an amount of computation polynomial in the randseed size".
EDIT: Confidence is about standard cryptographically strong randomness plus thermal noise being sufficient to prevent expected correlation with bits playing a functional role, which is all that could possibly be relevant to cognition.
Decoding isn't the challenge; the challenge is to make a guess whether you're seeing the output of the PRG or random output. Your "advantage" is
Adv_PRG[Distinguisher] = P(Distinguisher[PRG[seed]] = "PRG") - P(Distinguisher[True randomness] = "PRG")
Note that this is standard notation when one discusses pseudorandom generators. Hence Ciphergoth's comment about "the usual definitions."
(Nods.)