"Surely they are equivalent. Given a Rice-decidi..."


by Patrick Stevens Aug 14 2016

Surely they are equivalent. Given a Rice-deciding oracle, we can ask the oracle, "Does the partial function defined by machine $~$[n]$~$ specify where input $~$k$~$ should go?"; that determines whether $~$[n]$~$ halts on input $~$k$~$ or not.


Jaime Sevilla Molina

The problem I have in mind is deciding whether the Halting problem is equivalent to any statement of the form "You cannot decide membership for $~$S$~$", where $~$S$~$ is a non-trivial set of computable functions.

Clearly the argument exposed above shows that the Halting problem implies any of these statements, but does the reverse implication hold directly? In my proof of how Rice implies Halting I am handpicking an $~$S$~$. Can we make do without the handpicking?

In other words, given a Halting oracle, can we make a Rice oracle for an arbitrary $~$S$~$?

Patrick Stevens

I think the answer is no. Indeed, there are uncountably many $~$S$~$, but only countably many machines which can access oracles.