Составители:
93
грамматикой. Если она порождает хотя бы одно слово, машина найдет его и
остановится в конечном состоянии. Но если язык, порождаемый этой
грамматикой, пуст, то машина будет продолжать порождать слова и проверять
их вечно. Имеет место факт, что не существует машины Тьюринга, которая
останавливается на каждой входной цепочке и определяет для каждой csg,
является ли язык, порождаемый этой грамматикой, пустым. Другими словами,
проблема распознавания непустоты контекстно-зависимого языка алгоритми-
чески неразрешима.
В дополнение к рассмотрению машины Тьюринга как распознающего
устройства или процедуры мы можем рассматривать её как средство определе-
ния функций.
Пусть f(n) — функция, отображающая положительные целые в положи-
тельные целые, и пусть T = (Q, Σ, Γ, δ, q
0
, F) — машина Тьюринга. Если для
каждого целого n имеет место (q
0
, 1
n
, 1)
(p, 1
f (n)
,
1) для p∈F, то говорят, что
машина вычисляет функцию f(n).
Если некоторая машина Тьюринга T вычисляет функцию f(n) для каждого n,
то говорят, что функция f(n) рекурсивна.
Если
f(n) определена для не всех n, то говорят, что f(n) — частичная функция.
Если некоторая машина Тьюринга T вычисляет функцию f(n) всякий раз,
как f (n) определена, но может не остановиться для тех n, для которых f(n) не
определена, то f (n) — частично рекурсивная функция.
§ 6.4. Модификации
машин Тьюринга
Одна из причин, по которой машины Тьюринга принимаются в качестве
общей модели вычисления, состоит в том, что модель, с которой мы имеем
дело, инвариантна по отношению ко многим модификациям, которые, казалось
бы, увеличивают вычислительную мощность устройства. В этом параграфе
даются доказательства некоторых из этих теорем об эквивалентности этих
модификаций .
6.4.1. Машина
Тьюринга с бесконечной лентой в обе стороны
обозначается, как и первоначальная модель, T = (Q, Σ, Γ, δ, q
0
, F). Как
подразумевает её название, лента бесконечна не только вправо, но и влево.
Конфигурация такого устройства, как и прежде, есть (q, α, i), где q ∈ Q —
состояние, α ∈ Γ
+
— непустая строка символов, но i (и это необычно) — поло-
жение головки ленты относительно левого конца строки α. Другими словами,
i = 1, если машина сканирует самый левый символ цепочки α; i = 2, если она
сканирует второй символ, и т.д. Предполагается, что имеется бесконечно много
пустых ячеек не только справа, но и слева от цепочки α. Таким образом,
возможно, что i = 0, и в этом случае машина сканирует пробел непосредствен-
но слева от цепочки α.
Отношение
, связывающее две конфигурации, из которых вторая
получается из первой при помощи единственного движения, определяется так
же как для первоначальной модели, но со следующими исключениями для i ≤ 1:
__
T
*
Ò
−
−
Страницы
- « первая
- ‹ предыдущая
- …
- 92
- 93
- 94
- 95
- 96
- …
- следующая ›
- последняя »
