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

1. Нека је \(g\colon \mathbb N \to \mathbb N\) примитвно рекурзивна функција. Доказати да је тада и \(h(x,y) = g^y(x)\) примитивно рекурзивна функција. Напомена: \(g^k(x) = g(g^{k-1}(x))\) и \(g^0(x) = x.\)
2. Нека је функција \(f\colon \mathbb N^2 \to \mathbb N\) дефинисана на следећи начин \(f(x,0) = g(x)\) и \(f(x,y+1) = f(f(x,y),y).\) Доказати да уколико је \(g\) примитивно рекурзивна функција онда је и \(f\) примитивно рекурзивна

Свести наредне \(\lambda\)-изразе на нормалну форму (уколико она постоји):

1. \(\left(\left(\lambda x.\left(\left(\lambda y.\left(x\ y\right)\right)x\right)\right) \left(\lambda z.w\right)\right)\)
2. \(\left(\left(\lambda x.x\ x\right)\left(\lambda y.y\right)\right)\left(\lambda y.y\right)\)
3. \(\left(\left(\lambda kmn. + \left(*\ k\ m\right) n\right)\overline 3\right) \overline 4\)

Доказати да постоји рекурзивна функција \(s\colon \mathbb N^2 \to \mathbb N\) таква да за све \(x,y \in \mathbb N\) важи \(E_{s(x,y)} = E_x \cup E_y.\)

Нека је \(A\) рекурзивно набројив скуп и нека је \(B_x = \{2^x5^y \mid y \in \mathbb N\}.\) Доказати да је скуп \( \bigcup_{x \in A} B_x\) рекурзивно набројив.

Доказати да важи \(\{2^x+1 \mid x \in \mathbb N\} \leq_m \{5^x + 1 \mid x \in \mathbb N\}.\)