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


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

200
Ф. К. Хенни, Р. Е. Стирнэ
Предположим, что конфигурация символов, изображенная на рис. 2, а, в начале некоторого шага моделирования записана на одной из дорожек ленты памяти М2 и что в следующий момент времени Mh печатает вместо символа, который она считывает, символ «т», а также сдвигает ленту вправо. Для моделирования этого действия М2 должна напечатать во внутреннем квадрате символ «га» и изменить конфигурацию символов на дорожке таким образом, чтобы символ «а» попал во внутренний
и И М ^ I и к и
с к д г 0 X
• • • f h е Ч и i а у f ) и m Р » • •
Внутренний квадрат
с H g г т 0 X
• • • t h е Ч и i а f J и т Р • • •
L
Внутренний квадрат

• • • t h е Ч и i с k 0 г * т f 0 X л и т Р • • •
• • |• |f |П \C[4\U\ I \С [ffjg
^-Внутренний квадрат Рис. 2. Два последовательных упорядочивания.
квадрат и удовлетворялись правила 1 — 3. Это может быть достигнуто, как показано на рис. 2, б, путем сдвига символа «а» во внутренний квадрат и помещения только что напечатанного символа «т» на верхний уровень первой справа зоны памяти. Предположим теперь, что на следующем шаге вычисления печатает вместо символа, который она считывает, символ «Ь и сдвигает ленту еще на один квадрат вправо. В этом случае перестройка конфигурации символов будет осуществляться сложнее. Символ, который должен быть сдвинут во внутренний квадрат, находится на верхнем уровне третьей слева зоны памяти. Просто сдвинуть этот символ во внутренний квадрат, оставив третью зону памяти без изменения, невозможно, так как каждый уровень зоны памяти должен быть или целиком полным, или целиком пустым (правило 1). Наиболее быстрый способ восстановить правильную конфигурацию — это переместить все символы из верхнего уровня третьей зоны памяти в нижние уровни левой первой и второй зон памяти. Размеры зон памяти выбраны таким образом, что три из этих символов

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 201 202 203 204 205 206 207 208 209 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика