Tibor Radó

Dowód twierdzenia (Tibor Radó, 1962)

Załóżmy, że $f$ jest RAM-obliczalna. Jak wynika z lematu 4, możemy ją zdominować ściśle rosnącą funkcją RAM-obliczalną $g$.

Cel:
pokazać, że $f_{B^2}$ dominuje $g$.

Niech $[P]=g$ i $|P|=n_0$. Dla każdego $n$ utworzymy teraz RAM-program $Q_n$, który mając na wejściu 0 zwraca $g(f_{B^2}(n))$. Niech $P^+$ będzie programem uzyskanym z $P$ przez dodanie $\sigma(P[n])$ do każdego niezerowego numeru rejestru występującego w $P$, gdzie $\sigma(P[n])$ jest największym numerem rejestru używanym przez $P[n]$.

bb.gif

Teraz możemy zdefiniować program $Q$:

$P[n]$
$P^+$

Zauważmy, że $Q$ ma co najwyżej $n+n_0$ instrukcji i $[Q_n](0)=g(f_{B^2}(n))$. Zatem:

(1)
\begin{align} f_{B^2}(n+n_0)\geq g(f_{B^2}(n)) \end{align}

Dla $n > n_0 + 6$

(2)
\begin{align} f_{B^2}(n+n_0+6)>f_{B^2}(n+n_0+5)\geq g(f_{B^2}(n+5)) \geq g(2n) \geq g(n+n_0+6) \end{align}

Zatem $f_{B^2}(m) > g(m)$ dla $m>2(n_0+6)$, czyli $f_{B^2}$ dominuje $g$.

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License