Niekonstruowalne funkcje i nietypowe wyniki

W książce Arora-Barak w definicji funkcji konstruowalnych w czasie mówi się, że użycie funkcji, które nie są konstruowalne w czasie, może prowadzić do „anomalnych wyników”. Czy ktoś ma przykład takiego „anomalnego wyniku”? Słyszałem w szczególności, że mogą istnieć funkcje, których nie utrzymuje twierdzenie o hierarchii czasu, czy ktoś ma przykład takich funkcji? Czy jest coś w tym gdzieś w literaturze?

Twierdzenie luki Borodina : Dla każdej całkowitej funkcji obliczeniowej istnieje całkowita funkcja obliczalna taka, że .$g(n) \geq n$$t$$DTIME[g(t(n))] = DTIME[t(n)]$

W rzeczywistości dotyczy to każdej miary złożoności Blum zamiast .$DTIME$

Zobacz także stronę wikipedii i odnośniki na niej.

Ponieważ artykuł w Wikipedii nie zawiera dowodu, a artykuł jest na ACM DL, pomyślałem, że może być przydatne opublikowanie dowodu tutaj:

TEOREM 3.7. (Twierdzenie luki).

Niech będzie miarą złożoności, nieskalującą funkcją rekurencyjną taką, że . Następnie istnieje rosnąca funkcja rekurencyjna tak że funkcje obliczalne ze miary złożoności są takie same jak funkcje obliczalne ze miary złożoności .$\Phi$$g$$\forall x, g(x) \geq x$$t$$t$$g\circ t$

DOWÓD.

Zdefiniuj w następujący sposób:$t$

$$t(0) := 1$$ $$t(n) := \mu{ k > t(n-1)}: \forall i \leq n, (\Phi_i(n)<k \lor \Phi_i(n)> g(k) )$$

1. dla wszystkich istnieje , ponieważ dla wszystkich :$n$$k$$i \leq n$

   za. jeśli jest niezdefiniowany, to , i$\Phi_i(n)$$\forall k, \Phi_i(n)>g(k)$

   b. jeśli to .$\Phi_i(n)$$\exists k, \Phi_i(n) < k$

2. $k$ można znaleźć rekurencyjnie, ponieważ jest miarą złożoności, a zatem oraz są predykatami rekurencyjnymi.$\Phi$$\Phi_i(n) <k$$\Phi_i(n) > g(k)$

3. $t$ spełnia twierdzenie, ponieważ implikuje, że albo lub .$n \geq i$$\Phi_i(n) < t(n)$$\Phi_i(n) > g \circ t(n)$

CO BYŁO DO OKAZANIA.

Zauważamy, że dowolnie duże może być zgodne z Twierdzeniem 3.7. Załóżmy, że chcemy , a następnie zdefiniować$t$$t(n) > r(n)$

$$t(0) := r(0) + 1$$ $$t(n) := \mu{k > max\{t(n-1), r(n)\}}: \ldots$$

(Allan Borodin, „ Złożoność obliczeniowa i istnienie luk w złożoności ”, JACM 1972, z niewielkimi modyfikacjami).