Бесконечность ленты находится в противоречии со сделанным выше утверждением, что машину Тьюринга можно было бы в принципе пост- роить. Дело в том, что мы объявили ленту бесконечной лишь для простоты изложения. С тем же успехом можно было бы предположить, что лента не бесконечная, а лишь неограниченно растущая в обе стороны: например, можно было бы считать, что лента наращивается
на одну секцию, как только каретка доходит до конца ленты и долж- на двигаться дальше, или считать, что за каждую единицу времени слева и справа секции уже добавлены, и тем самым, хотя и в ущерб реальности, полагать ленту бесконечной в обе стороны. Отсюда сле- дует, что порядок, в котором расположены секции ленты, подобен порядку, в котором расположены все целые числа. Пронумеровав все секции ленты числами, мы тем самым получаем возможность указывать какую-либо секцию ленты, называя ее порядковый номер.
_1.0
_4-5 -4 -3 -2 -1 0 1 2 3 4
---------------------------------------------------------
...¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦...
---------------------------------------------------------
_1.5
В дальнейшем мы будем пользоваться изображением конечного участка ленты, который можно неограниченно продолжить в обе сто- роны и нумеровать ячейки ленты натуральными числами:
_1.0
_41 2 3 4
---------------------------
...¦ ¦ ¦ ¦ ¦...
---------------------------
_1.5
Алфавит. Алфавит машины Тьюринга содержит конечное число зна- ков (символов) А={S_40,S_41,...,S_4n}, образующих так называемый _1внеш-
_1ний алфавит, в котором кодируются сведения, подаваемые в машину, а также те, которые вырабатываются в ней. В каждой ячейке ленты может храниться лишь одна буква алфавита, или же ячейка может оказаться пустой. В этом случае будем говорить, что в ячейке на- ходится символ S_40, называемый пустой знак (в дальнейшем будем изображать его ^). Посылка этого знака в какую-либо ячейку ленты гасит (стирает) тот знак, который в ней ранее хранился, и остав- ляет ее пустой. О пустой ячейке будем говорить, что она хранит пустой знак.
На любой стадии работы машины в каждой ячейке может храниться не более одного знака. Таким образом, на ленте только _1конечное
_1число_2 ячеек заполнены символами алфавита А, отличными от пустого знака _2S_40_2 и хранящихся по одному в некоторых ячейках ленты. Други- ми словами, почти все ячейки ленты будут содержать пустой символ
S_40 (будут пустыми). В процессе работы машины символы, находящиеся в ячейках, могут меняться. Представим себе это следующим образом: если в какой-то момент символ в ячейке надо заменить на новый, то старый "стирается" (как на магнитофонной ленте, где при новой за- писи автоматически стирается старая запись), а в ячейку вписыва- ется новый символ. Новый и старый символы могут совпадать (т.е. символ в ячейке не меняется).
Управляющая головка (каретка) для считывания или записи инфор- мации способна:
- воспринимать информацию, находящуюся в ячейке,
- изменять эту информацию, продвигаться по ленте, при этом:
1. В данный момент управляющая головка обозревает (воспринима- ет) лишь одну ячейку ленты.
2. За один такт работы машины головка может:
a) передвинуться _1влево и воспринимать соседнюю слева ячейку
(этот сдвиг головки будет соответствовать команде машины Тьюринга
Влево);
b) передвинуться _1вправо и воспринимать соседнюю справа ячейку
(этот сдвиг головки будет соответствовать команде машины Тьюринга
Вправо); с) может остаться _1на месте и воспринимать ту же ячейку (этот сдвиг головки будет соответствовать команде машины Тьюринга
На_месте).
_1.0
+--- _1Обозреваемая ячейка
_7^
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.