14.06.2021.

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

Време израде: 120 минута.

1

Функција \(f\colon \mathbb N \rightarrow \mathbb N\) дефинисана је на следећи начин:

\[f(0) = 5, \quad f(x+1) = f([x/2])^2 + 2x.\]

Доказати да је функција \(f\) примитивно рекурзивна.

2

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

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}\)

4

Доказати да постоји рекурзивна функција \(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\}.\)

5

Нека је \(f\) унарна аритметичка функција. Доказати да је \(f\) израчунљива акко је скуп

\[A = \{2^x5^{f(x)} \mid x \in \text{Dom}(f)\}\]

рекурзивно набројив.