Практические задания к экзамену по теории алгоритмов

Практические задания к экзамену по теории алгоритмов

2011-2012

Доказать, что S(x, y) = x + y примитивно рекурсивная функция Доказать, что П(x, y) = x ? y примитивно рекурсивная функция Доказать, что функция примитивно-рекурсивна Доказать, что функция примитивно-рекурсивна Доказать, что функция примитивно-рекурсивна Доказать, что функция примитивно-рекурсивна Доказать, что функция примитивно-рекурсивна Доказать, что функция примитивно-рекурсивна Доказать, что функция примитивно-рекурсивна Доказать, что функция f(x, y) = x – y частично рекурсивна Доказать, что функция f(x, y) = x / y частично рекурсивна Реализовать на машине Тьюринга алгоритм вычисления функции n + 4 Реализовать на машине Тьюринга алгоритм вычисления функции n – 2 Реализовать на машине Тьюринга алгоритм вычисления функции 2n Доказать, что функция вычислима по Тьюрингу, для чего построить машину Тьюринга, вычисляющую ее Доказать, что функция вычислима по Тьюрингу, для чего построить машину Тьюринга, вычисляющую ее Машина Тьюринга имеет следующую функциональную схему: , , , , , . Найдите формульное выражение для функции f(x), вычисляемой этой машиной. Составить машину Поста для вычисления функции S(x, y) = x + y Предложить схему нормального алгоритма для вычисления функции (A = {1})
Найти канторовский номер упорядоченных троек (1;1;0), (2; 1; 1). Найти номер указанных троек для функции . Доказать, что функция S(x, y) = x + y является МНР-вычислимой Доказать, что функция является МНР-вычислимой.