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