Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

170 А Розенберг
состояний машины разделяется на две группы: «голосующие» состояния и «автономные» состояния.
Находясь в голосующем состоянии, машина воспринимает очередной входной символ. На основе текущего состояния, входного символа и символов, считываемых с рабочих лент, машина изменяет свое состояние, и каждая головка независимо от других записывает на своей рабочей ленте не более одного символа из вспомогательного алфавита и сдвигается не более чем на одну клетку вправо или влево. Начальное состояние обязательно должно быть голосующим.
Находясь в автономном состоянии, машина не воспринимает входного символа; но она выполняет очередной шаг работы так, как описано выше, в зависимости только от текущего состояния и от символов, считываемых с рабочих лент.
Голосующие состояния в свою очередь подразделяются на допускающие и отвергающие состояния. Входная последовательность допускается (соответственно отвергается) /г-ленточной машиной Тьюринга, если, исходя из начального состояния с пустыми рабочими лентами, при данной последовательности, подаваемой на вход символ за символом, машина совершает последовательность элементарных шагов, описанных выше, и заканчивает работу в допускающем состоянии (соответственно не делает этого).
Многоленточная машина Тьюринга со входом работает в реальном масштабе времени, если все ее состояния голосующие. Хорошо известно, что ограничение «реального времени» очень сильно суживает возможности машины Тьюринга.
Дадим формальное определение
Определение 1. «-ленточной машиной Тьюринга со входом (короче, просто машиной) называется восьмерка (КР, Ка, 2, W, М, 5, so, F) , где
(1) Кр и Ка — непересекающиеся конечные множества (соответственно голосующие и автономные состояния);
(2) 2 — алфавит входных символов; W — рабочий или вспомогательный алфавит, содержащий /;
(3) М — функция перехода из состояния в состояние, отображающая (КР X 2 X [Wln)(i(Ka X [W]n) в Кр U Ка\
(4) S — функция действия, отображающая (КР X 2 X[H7]n)U
"
(5) s0 — начальное состояние, элемент множества /Ср;
(6) F — множество допускающих состояний, подмножество множества Кр-
Если на 2 и W не наложено никаких дополнительных требований, мы часто будем обозначать машину просто

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 171 172 173 174 175 176 177 178 179 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика