Fungsi yang tidak dapat dikonstruksikan dan hasil anomali

Dalam buku Arora-Barak, dalam definisi fungsi yang dapat dikonstruksikan waktu, dikatakan bahwa menggunakan fungsi yang tidak dapat dikonstruksikan oleh waktu dapat mengarah pada "hasil yang tidak normal". Apakah ada yang punya contoh "hasil yang tidak biasa" seperti itu? Saya telah mendengar khususnya bahwa mungkin ada fungsi sehingga teorema hierarki waktu tidak berlaku, apakah ada yang punya contoh fungsi tersebut? Apakah ada sesuatu tentang ini di suatu tempat di perpustakaan?

$g(n) \geq n$$t$$DTIME[g(t(n))] = DTIME[t(n)]$

$DTIME$

Lihat juga halaman wikipedia dan referensi di dalamnya.

Karena artikel Wikipedia tidak memberikan buktinya dan makalahnya ada di ACM DL, saya pikir mungkin berguna untuk mengirim buktinya di sini:

THEOREM 3.7. (Gap Theorem).

$\Phi$$g$$\forall x, g(x) \geq x$$t$$t$$g\circ t$

BUKTI.

$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. $n$$k$$i \leq n$

   $\Phi_i(n)$$\forall k, \Phi_i(n)>g(k)$

   $\Phi_i(n)$$\exists k, \Phi_i(n) < k$

2. $k$$\Phi$$\Phi_i(n) <k$$\Phi_i(n) > g(k)$

3. $t$$n \geq i$$\Phi_i(n) < t(n)$$\Phi_i(n) > g \circ t(n)$

QED.

$t$$t(n) > r(n)$

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

(dari Allan Borodin, " Kompleksitas komputasi dan keberadaan celah kompleksitas ", JACM 1972, dengan sedikit modifikasi.)