Orcle TM eh?

[bellykellyyang]

I know that { (M,x) | M, with an oracle for the Halting Problem, halts on x} is a undecidable..
but is this not recognizable? and if I complement this language will i get not recognizable?

Please, don't abuse the editing option to delete your posts. We don't allow that here. I have restored your post thanks to Google Cache. - phlip

[phlip]

Recognisable, as in, you could make a program (presumably, a TM program, not a TM+Oracle program), that succesfully halts for "yes" answers (ie pairs of TM+Oracle programs and inputs such that the program halts on that input), and either unsuccessfully halts or never halts for "no" answers? The normal TM halting question is trivially recognisable in this way.

I'm pretty sure that your question is not recognisable. Consider the program that uses the halting oracle on its input and then halts iff the passed-in program does not halt. If we could make a TM that could recognise even just this TM+Oracle program, then we could pair it with the TM that recognises the TM halting problem, and make a TM that solves the TM halting problem. Which is impossible.

[bellykellyyang]

So are you saying the language is not-recognizable?
But I thought it's recognizable because if HALT-OTM(oracle turing machine) gets input of OTM as turing machine and x as an input, and ask if it will halt, if oracle says "yes it'll halt", then it will go into infinite loop and if it says "no it won't halt" then it will halt. Doesn't this mean it's recognizable since it loops? or it's unrecognizable because it doesn't accept on input? I'm confused..

[bellykellyyang]

I'm pretty sure that your question is not recognisable. Consider the program that uses the halting oracle on its input and then halts iff the passed-in program does not halt. If we could make a TM that could recognise even just this TM+Oracle program, then we could pair it with the TM that recognises the TM halting problem, and make a TM that solves the TM halting problem. Which is impossible.


can you explain this again?

[phlip]

It seems to me you have a very flimsy grasp of what your question actually means.

To make sure we're on the same page, can you please tell me your understanding of what each of the following terms means: "TM", "OTM", "Halt", "Recognise", "Recognisable", "Decide", "Decidable", and the Halting Problem. Also, while you're at it, proof by contradiction, since that's what a proof of the answer to your question will probably use.

[philoctetes]

Hail phlip, restorer of worlds!
Good answer. Elegant reduction.