|proof=
Пусть <tex>L-</tex> перечислимый.
: <tex>p(x):</tex>:: for <tex>for ~ i = 1 ~ .. ~ \infty</tex>::: if <tex>if ~ g(i) == x</tex>:::: return <tex>return ~ 1</tex>
Пусть <tex>L-</tex> полуразрешимый.
: <tex>g_0(i):</tex>:: <tex>cnt = 0</tex>:: for <tex>for ~ k = 1 ~ .. ~ \infty</tex>::: for <tex>for ~ x \in \{x_1, x_2, .., x_k\}</tex>:::: if <tex>if ~ p|_k(i) == 1</tex>::::: <tex>cnt++</tex>++:::: if <tex>if ~ cnt == i</tex>::::: return <tex>return ~ x</tex> : <tex>g(i):</tex>:: <tex>U = \emptyset</tex>:: for <tex>for ~ j = 1 ~ .. ~ \infty</tex>::: <tex>x \leftarrow = g_0(j)</tex>:::: if <tex>if ~ x \notin U</tex>::::: <tex>cnt++</tex>++::::: if <tex>if ~ cnt == i</tex>:::::: return <tex>return ~ x</tex>::::: <tex>U.insert(x)</tex>
Приведённые программы доказывают эквивалентность определений.
}}
