Kompresowanie informacji o problemie zatrzymania w maszynach wyroczni Turinga

Wiadomo, że problem zatrzymania jest niemożliwy do obliczenia. Możliwe jest jednak wykładnicze „kompresowanie” informacji o problemie zatrzymania, tak aby dekompresowanie było możliwe do obliczenia.

Dokładniej, można obliczyć na podstawie opisu maszyn Turinga, a n- bitowa porada stanowi odpowiedź na problem zatrzymania dla wszystkich 2 n - 1 maszyn Turinga, przy założeniu, że stan porady jest godny zaufania - my pozwól naszemu doradcy wybrać bity, aby opisały, ile maszyn Turinga zatrzymuje się w trybie binarnym, poczekaj, aż tyle zatrzyma się, i przekaż, że pozostałe nie zatrzymają się.$2^{n}-1$$n$$2^{n}-1$

Argument ten jest prostym wariantem dowodu, że stała Chaitina może być wykorzystana do rozwiązania problemu zatrzymania. Zaskoczyło mnie to, że jest ostry. Nie ma obliczalnej mapy z opisu maszyn Turinga i n- bitowych wskazówek dla 2 n bitów wyjścia zatrzymującego, które otrzymają właściwą odpowiedź, dla każdej krotki maszyn Turinga, dla pewnej krotki bitów. Gdyby tak było, moglibyśmy wytworzyć kontrprzykład poprzez przekątne, przy czym każda z 2 n maszyn Turinga symuluje to, co program robi na jednym z 2 n możliwych układów n bitów, a następnie wybiera własny stan zatrzymania, aby naruszyć prognozę.$2^n$$n$$2^n$$2^n$$2^n$$n$

Nie jest możliwe kompresowanie informacji o problemie zatrzymania w maszynach Turinga z wyrocznią zatrzymującą (bez samodzielnego dostępu do jakiejś wyroczni). Maszyny mogą po prostu symulować to, co przewidujesz na wszystkich możliwych wejściach, ignorując te, w których się nie zatrzymujesz, i wybierając ich czasy zatrzymania, aby dać leksykograficznie pierwszą odpowiedź, której nie przewidziałeś na żadnym wejściu.

To zmotywowało mnie do zastanowienia się nad tym, co dzieje się z innymi wyroczniami:

Czy istnieje przykład wyroczni, w której problem zatrzymania maszyn Turinga z tą wyrocznią można skompresować ze średnią szybkością wzrostu między liniową a wykładniczą?

$f(n)$$m$$m$$n$$m$$m$$n$$m$$1$$0$

$n<f(n)<2^{n}-1$$\omega(n)=f(n)=o(2^n)$

$J^A(e)$$e$$A$$e$$J$$J^A(e)$

$A$$h:\mathbb N\to\mathbb N$$e$$J^A(e)\in T_e$$(T_e)_{e\in\mathbb N}$$|T_e|\le h(e)$$e$

$f^A(k,n)=$$n$$k$$0,\dots,n-1$$k$$f^A(k,n)$

$f^A$$A$$g$$f^A(k,n)=J^A(g(k,n))$

$n$$A$$h(e)$$T_e$$e=g(k,n)$$k$

$h$$A$

Jest to dość dobry kandydat w tym sensie, że mamy jeden kierunek (górna granica szybkości wzrostu) i że w sposób możliwy do udowodnienia metoda, dzięki której uzyskaliśmy górną granicę, nie daje znacznie mniejszej górnej granicy.