## Orcle TM eh?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Larson, Moderators General, Prelates

### Orcle TM eh?

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
Last edited by bellykellyyang on Fri Mar 16, 2012 9:28 pm UTC, edited 1 time in total.
bellykellyyang

Posts: 3
Joined: Wed Mar 14, 2012 11:26 am UTC

### Re: Orcle TM eh?

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.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6779
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Orcle TM eh?

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

Posts: 3
Joined: Wed Mar 14, 2012 11:26 am UTC

### Re: Orcle TM eh?

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?
bellykellyyang

Posts: 3
Joined: Wed Mar 14, 2012 11:26 am UTC

### Re: Orcle TM eh?

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.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6779
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Orcle TM eh?

Hail phlip, restorer of worlds!