Составители:
82
Глава 6
МАШИНЫ ТЬЮРИНГА
§ 6.1. Неформальное и формальное описания
В этой главе мы рассмотрим ещё один тип распознающих устройств —
машины Тьюринга. Это абстрактное устройство было предложено в качестве
математической модели для описания процедур. Так как наше интуитивное
понятие процедуры как конечной последовательности инструкций, которые
могут выполняться механически, не является математически точным, мы не
можем доказать формально, что оно эквивалентно точному понятию машины
Тьюринга. Однако из определения этого устройства будет очевидно, что любое
вычисление, которое может быть описано посредством машины Тьюринга,
может быть выполнено механически. Также может быть показано, что любое
вычисление, которое может быть выполнено на современной вычислительной
машине, может быть описано посредством машины Тьюринга. Таким образом,
если кто-нибудь когда-нибудь нашёл бы процедуру, которая соответствует
интуитивным понятиям, но не поддаётся описанию посредством машины
Тьюринга, то она была бы необычной природы, так как не могла бы быть
запрограммирована для любой существующей вычислительной машины. Было
предложено много других формализаций процедуры, и было показано, что все
они эквивалентны формализации машины Тьюринга. Это поддерживает нашу
уверенность в том, что машина Тьюринга имеет достаточную общность, чтобы
охватить интуитивное понятие процедуры.
А.Чёрчем была высказана гипотеза, что любой процесс, который
естественным образом мог бы быть назван процедурой, реализуем машиной
Тьюринга. Впоследствии вычислимость при помощи машины Тьюринга стала
общепризнанным определением процедуры. Мы примем гипотезу Чёрча и
просто подставим формальное определение машины Тьюринга вместо
интуитивного понятия процедуры.
В литературе определение машины Тьюринга давалось разными способа-
ми. Мы начнём с обсуждения основной модели (рис. 6.1).
a
1
a
2
…
a
i
…
a
n
…
B B
…
Рис. 6.1.
Основная модель имеет конечное управление, ленту, которая разделена на
ячейки, и головку ленты, которая сканирует одну ячейку ленты в один приём.
Лента имеет
крайнюю левую ячейку, но простирается в бесконечность в правую
сторону. Каждая ячейка может содержать ровно один из конечного числа
символов ленты.
Первоначально n крайних левых ячеек для некоторого
конечного n содержат входную цепочку, строку символов ленты, называемых
Лента:
Конечное
управление
Страницы
- « первая
- ‹ предыдущая
- …
- 81
- 82
- 83
- 84
- 85
- …
- следующая ›
- последняя »
