Правильная вычислимость функции по Тьюрингу

1.

Правильная вычислимость
функции по Тьюрингу

2.

Вычислимость функции по Тьюрингу

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

Контрольные вопросы
1. Охарактеризуйте машину Тьюринга. В чем отличие свойств МТ от реальной
вычислительной машины.
2. Какие операции существуют для машины Тьюринга?
3. Покажите на примере реализацию операций композиции и ветвления с помощью
машины Тьюринга.
4. Какими свойствами обладает операция композиции?
5. Что такое конфигурации машины Тьюринга и какие виды конфигураций существуют?
6. Какие элементарные машины Тьюринга существуют ?
7. Охарактеризуйте каждую элементарную машину.
8. Постройте копирующую машину с помощью остальных элементарных машин.
9. Постройте выбирающую машину с помощью остальных элементарных машин.
10. Определите правильную вычислимость функции по Тьюрингу.
11.Докажите, что каждая элементарная функция правильно вычислима по Тьюрингу.
12.Докажите, что операции подстановки, примитивной рекурсии и минимизации сохраняют
свойство правильной вычислимости функции по Тьюрингу.
13.Докажите, что всякая ПРФ, всякая ЧРФ – правильно вычислима по Тьюрингу.
14.Объясните эквивалентность двух уточнений алгоритма.
15.Чем отличаются уточнения понятия алгоритма в виде рекурсивной функции от машины
Тьюринга?