= 27d567bc2d48d9f40e9ccc20ea370b15)
username2 comments on Open thread, Sep. 26 - Oct. 02, 2016 - Less Wrong Discussion
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 (90)
Why is this useful to remember?
Because primitive recursion is quite easy, and so it is quite easy to get a universal Turing machine. Filling that machine with a useful program is another thing entirely, but that's why we have evolution and programmers...
Something that also makes this point is AIXI. All the complexity of human-level AGI or beyond can be accomplished in a few short lines of code... if you had the luxury of running with infinite compute resources and allow some handwavery around defining utility functions. The real challenge isn't solving the problem in principle, but defining the problem in the first place and then reducing the solution to practice / conforming to the constraints of the real world.
"A few short lines of code..."
AIXI is not computable.
If we had a computer that could execute any finite number of lines of code instantaneously, and an infinite amount of memory, we would not know how to make it behave intelligently.
This is incorrect. AIXI is "not computable" only in the sense that it will not halt on the sorts of problems we care about on a real computer of realistically finite capabilities in a finite amount of time. That's not what is generally meant by 'computable'. But in any case if you assume these restrictions away as you did (infinite clock speed, infinite memory) then it absolutely is computable in the sense that you can define a Turing machine to perform the computation, and the computation will terminate in a finite amount of time, under the specified assumptions.
Simple reinforcement learning coupled with Solomonoff induction and an Occam prior (aka AIXI) results in intelligent behavior on arbitrary problem sets. It just also requires impossible computational requirements on practical requirements. But that's very different from uncomputability.
Sorry, you are simply mistaken here. Go and read more about it before you say anything else.
Okay random person on the internet.
If you can't use Google, see here. They even explain exactly why you are mistaken -- because Solomonoff induction is not computable in the first place, so nothing using it can be computable.
Taboo the word computable. (If that's not enough of a hint, notice that Solomonoff is "incomputable" only for finite computers, whereas this thread is assuming infinite computational resources.)
Again, you are mistaken. I assumed that you could execute any finite number of instructions in an instant. Computing Solomonoff probabilities requires executing an infinite number of instructions, since it implies assigning probabilities to all possible hypotheses that result in the appearances.
In other words, if you assume the ability to execute an infinite number of instructions (as opposed to simply the instantaneous execution of any finite number), you will indeed be able to "compute" the incomputable. But you will also be able to solve the halting problem, by running a program for an infinite number of steps and checking whether it halts during that process or not. As you said earlier, this is not what is typically meant by computable.
(If that is not clear enough for you, consider the fact that a Turing machine is allowed an infinite amount of "memory" by definition, and the amount of time it takes to execute a program is no part of the formalism. So "computable" and "incomputable" in standard terminology do indeed apply to computers with infinite resources in the sense that I specified.)