Писмени испит из предмета Теорија алгоритама За смер Р.

Функција \(f\colon \mathbb N \rightarrow \mathbb N\) дефинисана је на следећи начин: \[f(0) = 5, \quad f(x+1) = f([x/2])^2 + 2x.\]Доказати да је функција \(f\) примитивно рекурзивна.

Написати програм за Тјурингову машину који израчунава функцију \(f(x) = [\frac x 3].\)

Написати \(\lambda\)-израз \(\bm{\text{Max }}\) којим се за два задата нумерала одређује већи од њих. Примери:

• \(\bm{\text{Max }} \overline 7 \; \overline 3 \equiv \overline 7\)
• \(\bm{\text{Max }} \overline 6 \;\overline {15} \equiv \overline {15}\)

Доказати да постоји рекурзивна функција \(k \colon \mathbb N \rightarrow \mathbb N\) таква да је \(W_{k(x)} = \{0,1 , 2, \ldots x-1\}\) и \(E_{k(x)} = \{1, 3, 5, \ldots, x-1\}.\)