Cóż, tytuł prawie wszystko mówi. Interesujące pytanie powyżej zostało zadane przez komentatora Jaya na moim blogu (patrz tutaj i tutaj ). Zgaduję, że odpowiedź brzmi „tak” i że istnieje stosunkowo prosty dowód, ale nie widziałem go od razu. (Jednak z grubsza można by próbować pokazać, że jeśli język w nie był w , to musiałby mieć nieskończoną algorytmiczną wzajemną informację z , w którym to przypadku nie byłby obliczalny. Należy również pamiętać, że jeden kierunek jest trywialny: języki obliczeniowe w pewnością zawierają ).
Zauważ, że nie pytam o klasę AlmostP , która składa się z tych języków, które są w dla prawie każdego (i jest dobrze znane z równego ). Na to pytanie, musimy najpierw naprawić , a następnie spojrzeć na zestaw języków obliczalnych w . Z drugiej strony, może próbować pokazują, że gdy język, w jest obliczeniowy, nawet na nieruchomej losowo oracle , to w rzeczywistości, że język musi znajdować się w A l m O a T P .
Ściśle powiązane pytanie brzmi, czy z prawdopodobieństwem 1 w stosunku do losowej wyroczni mamy
Jeśli tak, to otrzymujemy następującą interesującą konsekwencję: jeśli , to z prawdopodobieństwem 1 przypadkowej wyroczni R , jedynymi językami, które są świadkami separacji wyroczni P R ≠ N P R, są języki nieobliczalne.