"The problem I have in mind is deciding whether ..."

https://arbital.com/p/5vs

by Jaime Sevilla Molina Aug 14 2016


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$~$?