Пустой квадрат

Cтраница 2

На любом уровне каждой зоны памяти квадраты либо все полны, либо все пусты. Заметим, что нужно различать пустые квадраты и квадраты, используемые для хранения пробелов. Если ленты Mk первоначально пусты, то лента памяти / W2 также пуста, но нижние уровни каждой дорожки хранят пробелы, тогда как верхние уровни пусты. [16]

Кроме замечания О.Е. Николаевой о том, что часть книги написана по американским СААР вместо европейских МСФО, на которые и собралась переходить Россия, есть и прямые ошибки. Например, Иллюстрация 5.4 содержит пустой квадрат. [17]

Машина начинает работать в фиксированном начальном состоянии, а на входной ленте записано некоторое слово. Это слово ограничено с обеих сторон пустыми квадратами, и его самый левый символ находится под считывающей головкой. При обработке каждого входного слова машина в конце концов попадает в состояние ( заключительное), с которым связан выход. [18]

Избирательный бюллетень содержит в алфавитном порядке фамилии, имена, отества всех зарегистрированных по округу кандидатов и их данные, перечисленные в части четвертой статьи 36 настоящего Кодекса. Справа против данных о каждом кандидате помещается пустой квадрат. В конце списка кандидатов в депутаты помещается строка Против всех кащидатов с расположенным справа от нее пустым квадратом. [19]

В качестве примера на рис. 2, а изображена типичная конфигурация, которая может быть записана на дорожке ленты памяти. Буквы изображают символы внешнего алфавита Mh, а пустые квадраты изображают пробелы. [20]

Такое перемещение можно описать строго формально в терминах операторов, рассматривая пустой квадрат как некоторый объект, который может быть передвинут в любом из четырех направлений. Это дает четыре оператора - вверх, вниз, влево, вправо - которые могут быть применены к некоторому состоянию лотка, порождая новое состояние. На рис. 3.2 показаны результаты применения этих операторов к начальному состоянию такой игры. Определенные операторы могут оказаться неприменимыми в некоторых состояниях. В нашей игре оператор неприменим, если пустой квадрат находится на краю лотка и рассматриваемый оператор должен был бы столкнуть его с лотка. [21]

Взаимодействие между двумя возбуждениями изображается пересечением их пропагаторов. Оно называется вершиной и иногда отмечается символом в виде сплошного кружка или пустого квадрата. [22]

Лента с несколькими уровнями. [23]

Предположим, что время вычисления машины М не превосходит Кп. Такая машина, конечно, не может посетить более чем ( К -) п пустых квадратов ленты. Символы, которые могут встречаться теперь в квадратах новых лент, представляют упорядоченные комбинации из / С символов первоначальных лент, по одному символу на каждом уровне клетки ленты. Верхний уровень новой ленты используется для записи входного слова, в то время как оставшиеся К. Машина М начинает работу только с символов, которые встречаются в верхнем уровне ее ленты, и работает точно так же, как и М в начале своих вычислений. Однако, если М пытается выйти за пределы входной последовательности в пустую часть ленты, М возвращается обратно и работает в обратном направлении во втором уровне своей ленты. [24]

Для произвольной машины Тьюринга А с алфавитом из m букв ( символов, записываемых на ленте, включая пустой квадрат) и с п внутренними состояниями строится машина В с двумя внутренними состояниями и алфавитом не более чем из 4тп т символов. Машина В будет работать по существу так же, как и машина А. Во всех квадратах, кроме символа, воспринимаемого считывающей головкой и смежного с ним, на ленте машины В записано то же, что и на ленте машины А в соответствующие моменты работы двух машин. [25]

Можно показать, что в этом случае символы в первоначально пустой части становятся, за исключением конечного их числа, одинаковыми. В самом деле, либо головка передвигается вправо из первого пустого квадрата во второй пустой квадрат по меньшей мере R 1 раз, либо нет. В последнем случае спустя конечное время считывающая головка остается в бывшем первом пустом квадрате, и вся лента, кроме конечной части, остается пустой. Если же головка уходит вправо К 1 раз, то она не вернется в первый квадрат, первоначально пустой, ибо R есть число отражений для пустой ленты. Во втором первоначально пустом квадрате в конце, концов будет записан тот же самый постоянный символ, потому что ко второму квадрату применимо такое же рассуждение, как и к первому. Во всех случаях машина работает на той же самой ленте ( бесконечном ряде пустых квадратов) и приходит одно и то же число раз справа ( R) и соответственно ( R 1) слева. Тем самым все возможные случаи исчерпаны и доказательство завершено. [26]

Конфигурация ленты машины Т после моделирования прибавления единицы к содержимому счетчика 2 машины М. [27]

Процесс моделирования протекает так. После выполнения необходимых переносов Т передвигается еще на один квадрат влево, чтобы определить, достигнута ли самая левая для каналов дорожки i цифра. Затем Т выполняет чистку, именно движется вправо вплоть до пустого квадрата, следующего за квадратом младшего разряда, и во время этого движения проверяет условие ( 3), производя необходимые исправления, и, кроме того, заменяет нули, появляющиеся в данном канале слева от крайней единицы, пустыми символами. Ясно, что во время чистки Т проверяет также значения счег-чиков на равенство нулю. И наконец, после чистки Т передвигается на один квадрат влево, занимая снова квадрат младшего разряда. [28]

Страницы: 1 2 3