Способы записи логической функции.

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

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

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

Графический способ записи логической функции называется диаграммой (графом) переходов. Вершинами графа являются состояния машины Тьюринга из множества состояний Q, ребрами графа – команды перехода из состояния в состояние с указанием записываемого символа и направления сдвига головки.

 Осуществляется переход из состояния q₂ в состояние q₈, в ячейку будет записан символ алфавита S₁, головка сдвинута влево на одну позицию.

Работа машины Тьюринга. Тьюрингово вычисление

Работа машины Тьюринга.

Пусть задана МТ с алфавитом S = {1, á, â, ë} и состояниями Q = {q₁, q₂, q₃, q₄, q₅}. Перед началом работы на ленту заносится начальная информация (например, пять 1) и фиксируется начальная обозреваемая ячейка (например,4). Работа описывается таблицей:

Определить:

- Информацию на ленте после останова.

- Записать систему Тьюринговых команд.

- Построить блок-схему работы МТ.

Изобразим на ленте начальную информацию и фиксированную ячейку:

Учитывая начальные условия, будем искать в таблице пересечение строки содержащей символ алфавита 1 и состояния q₁. Это пересечение равно - q₂ áE. Система Тьюринговых команд имеет вид - . Данная запись означает: машина переходит в состояние q₂, записывает в 4 ячейку символ алфавита á и оставляет головку на ячейке с номером 4. Теперь будем искать в таблице пересечение строки содержащей символ алфавита á и состояния q₂ . Это пересечение равно - q₂ áR. Данная запись означает: машина переходит в состояние q₂, записывает в 4 ячейку символ алфавита á и переводит головку на ячейке с номером 3 и т.д.

Информация на ленте	Система Тьюринговых команд

Состояние МТ не меняется, символ в ячейке не меняется, следовательно, состояние q₅ является конечным состоянием. Работа машины Тьюринга останавливается.

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