= 27d567bc2d48d9f40e9ccc20ea370b15)
asr comments on My summary of Eliezer's position on free will - 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 (100)
In general, no. To predict the output of an arbitrary algorithm, you have to have equivalent states to the algorithm. If I give you a Turing machine and ask you what its output is, you can't do any better than running it.
You can do various trivial transforms to it and say "no, I'm running a new machine", but it's as expensive as running the original and will have to be effectively isomorphic to it, I suspect.
I agree.
But if you're saying that it's proven that "you have to ...", I wasn't aware of that.
I don't have a proof of that claim, either, just a strong intuition. I should have specified that more clearly. If some other LWer has a proof in mind, I'd love to see it.
Here are some related things I do have proofs for.
There's no general procedure for figuring out whether two programs do the same thing -- this follows from Rice's theorem. (In fact, this is undecidable for arbitrary context-free languages, let alone more general programs.)
For any given problem, there is some set of asymptotically optimal algorithms, in terms of space or time complexity. And a simulator can't improve on that bound by more than a constant factor. So if you have an optimal algorithm for something, no AI can improve on that.
Now suppose I give you an arbitrary program and promise that there's a more efficient program that produces the same output. There can't be a general way to find the optimal program that produces the answer.*
When you say "optimal" you mean space or time used.
When you say "minimize" you mean "shortest equivalent program"?
I love this list of undecidable problems.
I meant to minimize in terms of asympototic time or space complexity, not length-of-program.
Oh. That makes sense (since you can't even tell if the machine will halt or not). I'm still not convinced it applies to free will, but I will not argue the point further since I agree with the conclusion anyway.