You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

IlyaShpitser comments on From the "weird math questions" department... - Less Wrong Discussion

5 Post author: CronoDAS 09 August 2012 07:19AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (49)

Comments (49)

You are viewing a single comment's thread. Show more comments above.

Comment author: IlyaShpitser 09 August 2012 06:15:43PM 1 point [-]

If the oracle is fake, you will find out in finite time since eventually you will print N 1s, and the oracle will lie about that program. If the oracle is true, this method will never terminate. But I don't think there is a way for a Turing machine to check for a true oracle (only for a fake oracle!).

Comment author: Decius 10 August 2012 04:38:37PM -1 points [-]

What if the finite time needed to determine N is greater than the finite time that you have available?

Comment author: IlyaShpitser 10 August 2012 04:40:48PM *  0 points [-]

OP asked "is there a way" not "is there a fast way".

Comment author: Decius 10 August 2012 04:52:38PM -1 points [-]

"In finite time" is not the same as "Using a halting process"

Powered by Reddit Powered by Reddit