bachal-2 (Варианты контрольных работ и экзамена)

ВариантЗадача 1. Построить машину Тьюринга, вычисляющую функцию f (x) = [ x2 ].Задача 2. Какая функция получается в результате применения оператора примитивной рекурсии кпаре функций g(x) = 0 и h(x, y, z) = sg(z).Задача 3. Доказать, что функция f (x, y) = x mod y, вычисляющая остаток от деления x на y(полагая f (x, 0) = 0), является примитивно рекурсивной.Задача 4. Какая функция получается в результате применения оператора минимизации µy f (x, y) кфункции f (x, y) = x + y?Задача 5. Доказать, что нигде не определенная функция натурального аргумента f (x) являетсячастично рекурсивной.Задача 6.

Доказать,что следующая функция не является частично рекурсивной1,есличисла x и y являются геделевыми номерами машин Тьюринга,вычисляющих одинаковые функции;ϕ(x, y) = 0, иначе.ВариантЗадача 1. Построить машину Тьюринга, вычисляющую функцию f (x) = |x − y|.Задача 2. Какая функция получается в результате применения оператора примитивной рекурсии кпаре функций g(x) = x и h(x, y, z) = y + 1 + z.Задача 3. Доказать, что функция f (x, y) = max(x, y), вычисляющая максимальное из двух чисел xи y, является примитивно рекурсивной.Задача 4. Какая функция получается в результате применения оператора минимизации µy f (x, y) кфункции f (x, y) = x × y?Задача 5.

Доказать, что всякая функция функция натурального аргумента f (x) с конечной областьюопределения является частично рекурсивной.Задача 6. Доказать,что следующая функция не является частично рекурсивной1,еслиx является геделевым номером машины Тьюринга,которая не останавливается ни на одной начальной конфигурации;ϕ(x) = 0, иначе..