Формально программа машины Тьюринга определяет

Формально программа машины Тьюринга определяет вычисление для ленты с "любым начальным содержимым", то есть для любой бесконечной в обе стороны последовательности

...,a-3, a-2, a-1, a0, a1, a2, a3,...

Пример 4.2.

(html, txt)

элементов алфавита ? следующим образом. В произвольный момент вычисления существует "текущее состояние" q

Q и целочисленная величина "положение читающего устройства" p. Вначале q = q0 и p = 0. Если q

q? и если

(q, ap) = (s', k', q'), то следующим шагом вычисления будет замена значения p на p + k, q на q' и ap на s'. Если q = q?, вычисление заканчивается. (Вычисление может не закончиться; для программы (4.1) это произойдeт тогда и только тогда, когда aj="единица" для всех j < 0.)

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

(1) Семантическое правило " включить х в B ", связанное с синтаксическим правилом, означает, что x должен стать элементом множества B, где B - атрибут аксиомы S грамматики. Значением B будет множество всех x, для которых существует такое семантическое правило, связанное с каждым применением соответствующего синтаксического правила в дереве вывода. (Это правило можно рассматривать как сокращeнную запись семантического правила

связанного с каждым синтаксическим правилом. Здесь B - синтезированный атрибут, имеющийся у всех нетерминальных символов. Для терминальных символов B(x) пусто. Ясно, что эти правила позволяют получить нужное B(S).)

(2) Семантическое правило "определить f(x) = y", связанное с синтаксическим правилом, означает, что значение функции f в точке x будет равно y; здесь f - атрибут аксиомы S грамматики. Если встречается два правила, задающих значение f(x) для одного и того же значения x, то возникает ситуация ошибки, а дерево вывода, в котором она возникла, называется неправильным.

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий