2015-04-12
1156
Математическая модель машины Тьюринга имеет вид:
Т = < vt; Q; W; j; y; x >,
| где: VT = {ai; a2;... an} | – множество символов внешнего алфавита; |
| Q = {qi; q2;... qm} | – множество символов внутреннего алфавита; |
| W = {R; L; S} | – множество символов алфавита перемещения головки; |
| j: Q Ä vt => vt | – функция выхода машины Тьюринга; |
| y: Q Ä vt => vt | – функция переходов машины Тьюринга. |
| x: Q Ä vt => vt | – функция перемещения головки машины Тьюринга. |
С алгебраической точки зрения машина Тьюринга является трехосновной алгеброй, т. е. алгеброй с тремя множествами (внешним алфавитом, внутренним алфавитом и перемещения головки) и тремя функциями (выхода, переходов и перемещений).
Полное описание машины Тьюринга определяется полной записью всех слов на информационной ленте, положением головки относительно ячеек информационной ленты и текущим состоянием управляющего устройства. Такое описание называют конфигурацией машины Тьюринга и обозначают
K = a qi b, где a – слово, расположенное слева от головки;
b – слово, расположенное вправо от головки;
|
|
|
qi – текущее состояние машины Тьюринга.
Введенное понятие «состояние» машины Тьюринга определяет ее «память», т. е. учет всех тех конфигураций, которые привели машину в текущее qi состояние. Следует обратить внимание, что символ, находящийся в ячейке под считывающей головкой, является первым символом слова b, т.е. b=(aj g).
Каждая конфигурация содержит только одно вхождение символа qi. К незаключительной конфигурации может быть применима только одна команда, которая переводит машину в новую конфигурацию. Так реализуется дискретность и детерминированность алгоритмического процесса.
Для удобства анализа вычислительных алгоритмов рекурсивных функций математик Пост предложил ограничить множество символов внешнего алфавита vt двумя символами, т.е. vt = {|; #}, где "|" (палочка) есть символ унарного кода числа, а "#" – символ пробела между числами. При этом любое целое неотрицательное число может быть представлено на информационной ленте последовательностью палочек, как это представлено в табл. 2.
Запись числа «x» эквивалентно «| x + 1».
Таблица 2
| Число в десятичной системе счисления | «Слово» в унарном коде на информационной ленте |
| | | |
| || | |
I Для упорядочения составления протоколов машины Тьюринга информационную ленту ограничивают полулентой бесконечной длины только в одну сторону. Алгоритмы допустимо исследовать на левой полуленте бесконечной в левую сторону и правой полуленте бесконечной в правую сторону. В зависимости от используемой полуленты приняты различные схемы записи стандартных конфигураций машины Тьюринга (табл. 3). Таблица 3 Стандартная Информационная полулента конфигурация правая левая Началь-ная qí | x 1+ 1# | x 2+ 1 #... #| x n+ 1 | x 1+ 1# | x 2+ 1 #... #| x n qí | Конечная qk | y + 1 | y qk | Работу машины Тьюринга удобно представлять протоколом, таблицей и графом. При протокольной записи все команды должны быть записаны упорядоченным списком. Например, 1) ai qí® ajqiW 2) ak qi ® ai qj W ................................. n) am q| ® an qk S. При табличном представлении строки описывают текущее состояние машины, а столбцы – содержимое обозреваемой ячейки. Тогда элементами матрицы этой таблицы являются правые части команд (aiqjW) для соответствующей пары текущего состояния машины (акqi). Табличная форма описания машины более компактна и позволяет применить матричные методы анализа для оптимизации структуры алгоритма (табл. 4). Таблица 4 Текущее Символы vt состояние аi ак ... am q1 ajqiW ... qi ... aiqjW ... ... ... ... ... ... q0 ... ... ... anqkS
|
|
|
