Тьюрингова модель переработки информации
Описанная ниже модель несущественно отличается от модели, предложенной Тьюрингом.
Представление информации (модель памяти). Будем считать, что информация представляется словами, то есть конечными последовательностями, составленными из букв конечного алфавита, и записывается на неограниченной в обе стороны ленте, разделенной на ячейки. Слово записывается в идущих подряд ячейках по одной букве в ячейке.
В ячейку может быть ничего не записано, в этом случае говорим, что ячейка содержит пробел. Для обозначения пробела используем символ . Конечную последовательность, составленную из символов алфавита и символа пробела, называем псевдословом. Считаем, что слева от первой буквы псевдослова и справа от последней записаны пробелы, кроме того, один из символов псевдослова будем помечать стрелкой. Множество всех конечных последовательностей символов из алфавита обозначается через .
Если псевдослово имеет вид , где , , то называем его первым словом, — вторым и т.д. Слова могут быть и пустыми. Пустые слова не занимают места на ленте. При необходимости будем считать, что между двумя идущими подряд пробелами записано пустое слово.
Поскольку на ленте в каждый момент времени будет находиться не более чем конечное число символов, отличных от пробела, постольку для любого
в псевдослове будет определено его -е слово, возможно пустое.
Преобразователь информации. Преобразователь информации можно представить как некоторое устройство, снабженное головкой, обозревающей в каждый момент времени одну из ячеек ленты, которое по заранее намеченному плану (программе) может выполнять операции следующего вида:
- напечатать один из символов алфавита в обозреваемой ячейке;
- сдвинуть головку по ленте на одну ячейку влево;
- сдвинуть головку по ленте на одну ячейку вправо;
- ничего не делать до следующего такта времени.
Определение программы. Программу преобразования информации будем представлять в виде ориентированного графа, вершины которого помечены символами из множества , а дуги — символами из множества так, что разным дугам, выходящим из одной вершины, приписаны разные символы.
Одна вершина графа выделена в качестве входной, на рисунках будем отмечать ее входящей стрелкой. Предполагаем, что .
Действие программы осуществляется следующим образом. В начальный момент головка вычислительного устройства обозревает одну из ячеек ленты. Просматривается входная вершина программы. Если ей приписан символ , или , то головка вычислителя сдвигается по ленте на одну ячейку соответственно вправо, влево или остается на месте; если же ей приписан символ из алфавита или , то этот символ печатается в обозреваемой ячейке, а старое содержимое ячейки при этом стирается. После того как выполнено действие, соответствующее вершине , в графе отыскивается выходящая из дуга, помеченная той буквой, которая находится в данный момент в обозреваемой ячейке. Затем выполняется действие, соответствующее вершине, в которую ведет найденная дуга. Процесс продолжается до тех пор, пока не будет достигнута вершина, из которой не выходит дуга, помеченная буквой, обозреваемой в данный момент. Если такой момент не наступает, то программа работает бесконечно долго.
Вершину , для которой найдется хотя бы одна буква из , не используемая в качестве метки на дугах, выходящих из , будем называть выходной. Выходные вершины будем помечать выходящими "в никуда" стрелками, помеченными буквами, не использованными на других дугах.
Согласно данному описанию, программу можно задать как набор:
в котором — множество вершин графа;
— алфавит символов, печатающихся на ленте; — входная вершина (); — отображение в ; — частичное отображение
в .
Чтобы не загромождать чертежи большим количеством стрелок и надписей при изображении программ, мы используем следующие соглашения. Если из вершины в вершину
ведет несколько дуг, будем заменять их одной дугой с надписанными над ней буквами, соответствующими заменяемым дугам; одну из дуг, выходящих из данной вершины, будем оставлять неподписанной, считая при этом, что она помечена всеми буквами алфавита , которые не использованы на других дугах, выходящих из вершины .Такая дуга может оказаться единственной, выходящей из вершины . Ввиду большой близости введенного нами понятия программы с понятием машины Тьюринга будем называть наши программы тьюринговыми. Множество выходных вершин программы обозначим через .
Пример.
Пусть и на ленте записано псевдослово
, где , , а стрелка над символом показывает положение головки в начальный момент. Рассматривая слово
как двоичную запись натурального числа , требуется составить программу, которая на ленте оставляет псевдослово
, являющееся двоичной записью числа . Нетрудно увидеть, что поставленную задачу решает программа, представленная на рис. 11.1.
Рис. 11.1.
Здесь входная и выходная вершины помечены, соответственно, входящей и выходящей стрелками.