Составители:
92
вызывает подпрограмму T
1
один раз для каждой единицы в первом блоке,
отключая её проверку. Таким образом осуществляется умножение.
§ 6.3. Машина Тьюринга
как процедура
До сих пор мы определяли машину Тьюринга как распознающее
устройство. Но можно рассматривать машину Тьюринга и как процедуру.
Например, если мы желаем описать процедуру для определения того, является
ли число простым, мы могли бы построить машину Тьюринга, которая
принимает множество всех простых чисел. Рассматриваем мы эту машину, в
данном случае, как распознаватель или как процедуру — дело вкуса.
Если желательно рассмотреть процедуру манипуляции над строками
символов, то можно свести её к проблеме распознавания при помощи
построения другой машины Тьюринга, которая принимает пары строк,
разделенных специальным символом. Эта машина принимает данную пару
точно тогда, когда процедура превратила бы первую строку в паре во вторую и
остановилась. Мы оставим доказательство того факта, что по данной
процедуре можно найти соответствующий распознаватель, и наоборот, в
качестве упражнения для читателя. Большинство необходимых для этого идей
содержит §1.2.
Машина Тьюринга в примере 6.1 используется как распознаватель.
Заметим, что независимо от того, какова входная цепочка, эта машина со
временем достигнет условия, при котором для состояния конечного
управления и сканируемого символа функция δ не определена. В таком случае
машина Тьюринга останавливается и никакие дальнейшие её движения
невозможны. Если язык принимается машиной Тьюринга, которая
останавливается на всех входных цепочках, то говорят, что язык рекурсивен.
Следует подчеркнуть, что существуют языки, которые принимаются
машинами Тьюринга, не останавливающимися для некоторых цепочек, не
содержащихся в языке, но которые не принимаются никакими машинами
Тьюринга, останавливающимися на всех входных цепочках. Язык, который
может быть распознан некоторой машиной Тьюринга, называется рекурсивно
перечислимым множеством (
recursively enumerable set — res). В следующей
главе будет показано, что рекурсивно перечислимые множества являются в
точности языками, порождаемыми грамматиками типа 0.
Когда машина Тьюринга рассматривается как процедура и оказывается, что
она останавливается для всех входных цепочек, то говорят, что такая
процедура есть алгоритм.
Есть процедуры, для которых не существует никакого соответствующего
алгоритма. Примером их является процедура для определения, порождает ли
контекстно-зависимая грамматика (csg), по крайней мере, одну терминальную
цепочку. Можно построить машину Тьюринга, которая по заданной csg будет
порождать все возможные терминальные цепочки в некотором лексико-
графическом порядке. К каждой цепочке эта машина Тьюринга применяет
алгоритм, данный в гл. 2, чтобы увидеть, порождается ли данная цепочка этой
Страницы
- « первая
- ‹ предыдущая
- …
- 91
- 92
- 93
- 94
- 95
- …
- следующая ›
- последняя »
