Cтраница 3
Машина начинает работать в фиксированном начальном состоянии, а на входной ленте записано некоторое слово. Это слово ограничено с обеих сторон пустыми квадратами, и его самый левый символ находится под считывающей головкой. При обработке каждого входного слова машина в конце концов попадает в состояние ( заключительное), с которым связан выход. [31]
Однако особенность выбранного варианта машины Тьюринга состоит в том, что содержимое входной ленты остается неизменным на протяжении всего вычисления. Это позволяет в дальнейших построениях обходиться ( в конфигурации) без слова, записанного на входной ленте. Таким образом, мы приходим к понятию неполной конфигурации ( /, fe, w, 0 2), гДе параметры /, fe, z0i, w имеют тот же смысл, что и выше. [32]
Группу операторов слияния, исполняемых, начиная с момента освобождения одной из входных лент, назначаемой выходной, и вплоть до освобождения какой-либо другой входной ленты, будем называть этапом слияния. [33]
Основная память делится на три поля, два из которых загружаются посегментно с входных лент. Записи, находящиеся во входных сегментах, объединяются в выходной сегмент, который по мере заполнения перезаписывается на одну из выходных лент, затем продолжается объединение записей входных сегментов. [34]
В этой программе БФ - регистр, в котором собирается каждое слово на входной ленте; ВЫХ - регистр, на котором собирается результат сжатия исходной информации на ленте ввода. Программа работает следующим образом. Вначале вводится таблица ТИНФ и сбрасываются ( очищаются) рабочие регистры БФ и ВЫХ. Затем в комплексе команд СЛОВО происходит формирование в регистре БФ текущего слова на ленте ввода. Как только слово будет сформировано ( признаком является появление пробела на ленте ввода), управление передается комплексу команд СЖАТИЕ, в котором сформированное слово в памяти БФ сравнивается со словами в первой колонке памяти ТИНФ. Если подобное слово будет найдено, то в регистр ВЫХ будет дописан более короткий эквивалент слова на регистре БФ. Этот эквивалент будет взят из второй колонки доступной ячейки таблицы ТИНФ. [35]
В отличие от этих результатов, устанавливающих инвариантность, мы покажем, что наличие входной ленты с двусторонним движением сильно изменяет минимум времени вычислений. Двусторонняя ( off-line) модель имеет входную ленту, на которой помещается только читающая головка. На каждом шаге двусторонняя СМ может передвигать читающую головку на один квадрат влево или вправо по входной ленте, не выходя за границы области, в которой записано входное слово. Под принимающими и отвергающими состояниями понимают состояния остановки, и слово принимается или отвергается согласно состоянию, в котором останавливается СМ. [36]
Идея построения такой процедуры состоит в том, что начальные упорядоченные группы распределяются по входным лентам неравномерно, и поэтому входные ленты в процессе выполнения операторов слияния освобождаются неодновременно. Освободившаяся входная лента назначается выходной для следующих операторов слияния, а лента, выполнявшая до этого функции выходной ленты - входной. Размер упорядоченных участков на ленте, переназначенной из выходных во входные, естественно, будет отличаться от размеров упорядоченных участков на других входных лентах, и поэтому последовательное применение указанного алгоритма приведет к тому, что количество упорядоченных участков на всех входных лентах будет разным и размеры упорядоченных участков тоже будут отличаться друг от друга. Неравенство друг другу размеров сливаемых участков будет, естественно, снижать результативность и эффективность операторов слияния. [37]
В дальнейшей части программы индекс i присваивается выходной ленте, а индекс / - входным лентам. Блок 6 фиксирует количество упорядоченных участков на выходной ленте. Блок 10 фиксирует момент исчерпания исходного количества начальных участков N для перехода в случае исчерпания на другую ветвь программы. [38]
Все автоматы, которыми мы будем пользоваться, суть частные случаи машины Тьюринга с входной лентой, которая может быть описана следующим образом. Машина имеет две ленты - входную и рабочую. Каждой ленте сопоставлены алфавит с выделенным в нем пустым символом и головка, также называемые соответственно входными и выходными. [39]
Машина допускает цепочку со, если начав работу в начальной ситуации с цепочкой со на входной ленте через конечное число шагов, она может оказаться в заключительной ситуации. [40]
Управляющая система устанавливает момент завершения обработки записей каждого из входных сегментов с их последующей загрузкой с соответствующих входных лент. Эти действия выполняются до тех пор, пока на одной из входных лент не завершится выборка ее. При этом содержимое второго участка переписывается на выходную ленту. [41]
Будем говорить, что машина находится в начальной ситуации ( конфигурации), если на ее входной ленте непосредственно за ограничивающим символом записана цепочка, не содержащая пустого символа, рабочая лента пуста ( кроме ограничивающей ячейки), обе головки обозревают ограничивающие символы и машина находится в начальном состоянии. [42]
Такая машина начинает свои вычисления, если входное слово записано на одной из ее лент, называемой входной лентой. Вторая лента, называемая внешней лентой, перед началом вычислений полностью пуста. Простой способ выполнения желаемого вычисления состоит из следующих трех шагов. [43]
Длина участка 1 - равна сумме длин участков, записанных в / - м этапе на всех входных лентах. На М-1 входную ленту упорядоченные участки последовательно записывались в предыдущих М-1 этапах процедуры или, если этапов было меньше чем М-1, то частично при формировании начальных участков. В последнем случае длины участков ( считая, как и прежде, единицей длины объем ОЗУ) равны единице. [44]
Машина с ограниченной активностью ( МОА) имеет детерминированное управляющее устройство с конечным числом состояний, оперирующее с входной лентой, с которой можно только считывать и на которой символы располагаются только в одну строчку, с выходной лентой, на которую можно только писать, причем тоже в одну строчку, и с памятью. Память - счетное множество ячеек, каждая из которых может содержать бинарную величину. Полный шаг МОА описывается следующим образом. В зависимости от состояния конечного управляющего устройства входная лента может быть продвинута на один символ и в точности одна рабочая головка должна быть сдвинута одним из сдвигов. Затем в зависимости от управляющего состояния, нового входного символа ( если он существует) и величины, которая хранится в обозреваемой ячейке памяти, возможно запоминание новой величины, определение выходного символа и введение нового управляющего состояния. Таким образом, для каждого данного символа на входной ленте существует единственный шаг, когда этот символ читается, и по определению он не может быть прочитан еще раз. [45]