Стандарт организации (стр. 8 )

№ 36.

1) .

2) Наибольший общий делитель чисел x и y.

3)

Лабораторная работа № 3. Машина Тьюринга. Синтез. Доказательство вычислимости функции по Тьюрингу.

Цели и задачи работы: изучение логики работы машины Тьюринга, разработка машины Тьюринга, выполняющей вычисление функции.

Теоретические сведения о работе приведены в конспекте лекций, литературе [1-3].

Описание используемых средств для выполнения работы : операционная система Windows ХР/7, Visual Studio 2008-2010, программа automat или другой тестер для проверки правильности работы машины Тьюринга.

Методика выполнения работы:

1.  Изучить способы задания и логику работы машины Тьюринга.

2.  Определить, какую функцию вычисляет заданная машина Тьюринга (задание 1).

3.  Доказать вычислимость функции по Тьюрингу. (задание 2).

4.  Протестировать машину Тьюринга на всевозможных значениях аргументов функции.

5.  Продемонстрировать преподавателю работу МТ.

Требования к отчету:

Отчет по лабораторной должен содержать титульный лист, запись аналитического вида функции по заданию 1, команды МТ или граф по заданию 2.

Защита лабораторной, помимо теоретических вопросов, включает выполнение практического задания по построению МТ, предложенной преподавателем.

Индивидуальные задания:

А. Задания с обычным уровнем сложности

№1.

1) f(x, y, z) = ?

2)

№ 2.

1) f(x, y) = ?

2)

№ 3.

1) f(x, y, z, t) = ?

2)

№ 4.

1) f(x, y) = ?

2)

№ 5.

1) f(x, y, z, t) = ?

2)

№ 6.

1) f(x, y, z) = ?

2)

№ 7.

1) f(x, y, z, t) = ?

2)

№ 8.

1) f(x) = ?

2)

№ 9.

1) f(x, y) = ?

2)

№ 10.

1) f(x, y, z) = ?

2)

№ 11.

1) f(x, y) = ?

2)

№ 12.

1) f(x) = ?

2)

№ 13.

1) f(x, y) = ?

2)

№ 14.

1) f(x, y) = ?

2)

№ 15.

1) f(x, y) = ?

2)

№ 16.

1) f(x, y, z) = ?

2)

№ 17.

1) f(x, y, z, t) = ?

2)

№ 18.

1) f(x, y) = ?

2)

№ 19.

1) f(x, y, z, t) = ?

2)

№ 20.

1) f(x, y) = ?

2)

Б. Задания с низким уровнем сложности

№ 21.

1) f(x, y, z) = ?

2)

№ 22.

1) f(x, y, z) = ?

2)

№ 23.

1) f(x) = ?

2)

№ 24.

1) f(x, y, z) = ?

2)

№ 25.

1) f(x, y, z) = ?

2)

№ 26.

1) f(x, y, z) = ?

2)

№ 27.

1) f(x, y, z) = ?

2)

№ 28.

1) f(x, y, z, t) = ?

2)

№ 29.

1) f(x) = ?

2)

№ 30.

1) f(x, y) = ?

2)

№ 31.

1) f(x, y, z, t) = ?

2)

№ 32.

1) f(x, y, z) = ?

2)

№ 33.

1) f(x, y, z) = ?