9.Система команд машины Тьюринга: структура команды, способы представления

Совокупность всех команд - система команд. Она абсолютна детерминирована, т.е. все команды имеют различные левые части. Система команд представляется 3мя способами:

•Список команд

•Таблица (строки нумеруются номерами состояний, а столбцы – алфавитом лент)

•Графический (граф, в котором вершины сопоставляются с состояниями, а каждой команде соответствует дуга, ведущая из начального состояния в конечное)

10.Конфигурации машины Тьюринга, стандартные конфигурации, смена конфигураций

Текущей конфигурацией машины Тьюринга (или любого её варианта), рассматриваемой в определённый момент времени, называется полная информация о состоянии машины в этот момент, содержимом её ленты и положении головки на ленте.

Стандартной начальной конфигурацией МТ является: УУ находится в начальном состоянии q1, головка находится на самом левом непустом символе.

Стандартной заключительной конфигурацией МТ является: УУ находится в заключительном состоянии qz, головка находится на самом левом непустом символе.

11.Вычислимость по Тьюрингу

Введем функцию f:V->W

Функция f является правильно вычислимой по Тьюрингу если:

1)Для любых v принадлежащих V и любых w принадлежащих W имеет место последовательность конфигураций - q1v->q2w;

2)Для любого v принадлежащего V такого что f(V) –неопределена, Мт запущенная в конфигурации f(v) не останавливается.

12.Композиция машин Тьюринга

Если и вычислимы по Тьюрингу, то их композиция также вычислима по Тьюрингу.

Композицией называется машина и она изображается блок схемой:

Для этого отождествляем состояние q1z c q21 конечное состояние машины с начальным состоянием машины . Систему команд приписываем системе команд машины . Начальным состоянием объявим состояние q11 а заключительным q22.

13.Вычисление предиката на машинах Тьюринга с восстановлением и без

Пусть задан предикат Р(а), где а является словом в некотором алфавите А. Как известно предикат может быть либо истинным, либо ложным либо неопределенным. Поставим в соответствие предикату машину Тьюринга следующим образом. Машина тюринга правильно вычисляет предикат Р(а), если

T(a)=

14.Функции разветвления на машинах Тьюринга

было уже

15.Понятие универсальной машины Тьюринга, принцип действия

Для любой МТ T(a), где T(a) – E_t построить МТ U(E_t a)

U останавливается, когда ост-ся T и не остаеавливается, когда T не останавливается

U(E_t a) = T(a)

И U принято называть – универсальной М.Т.

16.Кодирование алфавитов и смена конфигураций в универсальной машине Тьюринга

Было уже, вопрос 41, 42

17.Алгоритмическая неразрешимость задач

Задачи, для которых невозможно построить алгоритм

18.Примеры неразрешимых задач, не имеющих общего метода решения

Задача останова, Совершенные числа

19.Примеры информационно-неопределенных и логически неразрешимых задач

Задача позиционирования головки М.Т. ,Машина останова, Проблема эквивалентности алгоритмов, Проблема тотальности

20.Проблема соответствий Поста

Тут дохера, уже 3:12 , идите ауй, я спать, раньше надо было учить…, и не надо сейчас говорить какой я плохой, я все равно узнаю.