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

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: Decius 09 August 2012 04:22:59PM 1 point [-]

So, how do you know in finite time whether it is a true oracle or if you haven't yet found N?

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"

Comment author: thomblake 09 August 2012 07:26:52PM *  0 points [-]

how do you know in finite time whether it is a true oracle or if you haven't yet found N?

  1. Write a short program that applies my method to an oracle. (Don't run it yet)
  2. Use my method to determine whether the oracle is "true" or "fake" for N = your program length. If "fake", then you're done.
  3. If "true" for N = your program length, then ask the oracle whether your program will halt. If so, then it's "fake".

EDIT: Somehow, I wrote the above having forgotten that the fake oracle outputs "never halts" above N, not "will halt".

Alternatively, you could just keep applying the method up to N that you're concerned about - you will thus always know before trusting the oracle with a program of length N, whether it's true or fake.

Comment author: Decius 11 August 2012 12:22:57AM *  0 points [-]

Write a program which halts if our oracle is false in the specified manner, and which does not halt if the oracle is true (for example, a program which tests a trivial halting program of length ++ in a loop.) You don't run that program, but you do determine that our oracle gives a true answer for programs of that size, by testing a longer halting program of the trivial type.

You then test the oracle on that program- if the oracle says the program halts, it is a false oracle. If the oracle says that program does not halt, it is not a false oracle of the specific type described in the problem.

And it can be solved in constant time- you need to ask the oracle twice.

I didn't see that you didn't actually have to test the oracle with a program of length N+1; you only need to figure out how to ask the oracle what it would say when asked that question.

Comment author: Vladimir_Nesov 11 August 2012 12:34:47AM 2 points [-]

Write a program which halts if our oracle is false in the specified manner, and which does not halt if the oracle is true

This is not a program, since the oracle is not a program, and so can't be called as a subroutine. Since this is not a program, it can't be given to the oracle.

Powered by Reddit Powered by Reddit