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