23.06.2020.
Писмени испит из предмета Теорија алгоритама За смер Л.
Време израде: 120 минута.
1
12 поена
- Нека је \(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.\)
- Нека је функција \(f\colon \mathbb N^2 \to \mathbb N\) дефинисана на следећи начин \(f(x,0) = g(x)\) и \(f(x,y+1) = f(f(x,y),y).\) Доказати да уколико је \(g\) примитивно рекурзивна функција онда је и \(f\) примитивно рекурзивна
2
12 поена
Свести наредне \(\lambda\)-изразе на нормалну форму (уколико она постоји):
- \(\left(\left(\lambda x.\left(\left(\lambda y.\left(x\ y\right)\right)x\right)\right) \left(\lambda z.w\right)\right)\)
- \(\left(\left(\lambda x.x\ x\right)\left(\lambda y.y\right)\right)\left(\lambda y.y\right)\)
- \(\left(\left(\lambda kmn. + \left(*\ k\ m\right) n\right)\overline 3\right) \overline 4\)
3
12 поена
Доказати да постоји рекурзивна функција \(s\colon \mathbb N^2 \to \mathbb N\) таква да за све \(x,y \in \mathbb N\) важи \(E_{s(x,y)} = E_x \cup E_y.\)
4
12 поена
Нека је \(A\) рекурзивно набројив скуп и нека је \(B_x = \{2^x5^y \mid y \in \mathbb N\}.\) Доказати да је скуп \( \bigcup_{x \in A} B_x\) рекурзивно набројив.
5
12 поена
Доказати да важи \(\{2^x+1 \mid x \in \mathbb N\} \leq_m \{5^x + 1 \mid x \in \mathbb N\}.\)