Исходный алфавит

Cтраница 3

Ясно, что кодирование информации в двоичном алфавите неоднозначно. Более того, для любого исходного алфавита существует бесконечное множество таких преобразований. [31]

Второй шаг состоит в построении таблицы переходов искомого автомата А. При этом входными сигналами служат буквы исходного алфавита Ж, а внутренние состояния автомата отождествляются с множествами основных индексов. [32]

На рис. 24.3 изображен квадрат Вшкенера, построенный на основе смешанного алфавита, приведенной) на ряс. Сверху и по левому краю квадрата выиисан исходный алфавит. В первой строке квадрата представлен смешанный алфавит. Во второй строке тот же алфавит циклически сдвинут на одну позицию, при этом первая буква переместилась в правый конец строки. Квадрат состоит из 32 смешанных алфавитов, полученных из одного смешанного алфавита, каждому из них соответствует та буква исходного алфавита, которая записана слева от него. На рис. 24.4 показано шифрование фразы при помощи ключевого слова ЛИСП и данного квадрата. Ключевое слово многократно записывается под исходным текстом, и каждая буква исходного текста шифруется при помощи смешанного алфавита, соответствующего той букве ключевого слова, которая стоит под данной буквой исходного текста. Эта схема шифрования уже не поддается раскрытию при помощи простого под-кодирование же подразумевает замену целых слов или фраз, а не отдельных букв. Лица, владеющие шифром или кодом, шифруют или кодируют свои сообщения, а получатели сообщений дешифруют или декодируют их. Лица, пытающиеся узнать чужой секрет, расшифровывают сообщения; различие между этими глаголами соответствует различию между знанием секрета шифра и попыткой разгадать его. [33]

Блок перестановок. [34]

Одним из простейших методов является прямая замена исходных символов их эквивалентом из вектора замен. Для очередного символа исходного текста отыскивается его местоположение в исходном алфавите. Эквивалент из вектора замены выбирается как отстоящий на полученное смещение от начала алфавита. При дешифровании поиск производится в векторе замен, а эквивалент выбирается из исходного алфавита. [35]

Это приводит к концепции рассмотрения процесса движения по ГДП, как срабатывание системы переходов-актов, увеличивающих глубину продвижения. Тьюринга, в которой в метках ленты состояний находятся не стринги над исходным алфавитом, а некоторые графы. Подобная концепция позволяет интерпретировать ГДП как систему эво-люционизирующих графов, а последующая автоматизация описанного подхода позволила бы реализовать схему горизонтальной ориентации проблемного пользователя в процессе интерактивного взаимодействия без введения новых траекторий в ГДП. [36]

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

Предположим, что алгоритм а существует. Полученное противоречие и доказывает неразрешимость проблемы останова в исходном алфавите операторов. [38]

На 4 - м расширении применять правило замены уже не требуется, ввиду отсутствия символов внутренних состояний. Ясно, что все последующие расширения уже не будут менять полученного выражения. Заметим еще, что при первом расширении мы применяли операции алгебры событий с целью упрощения полученного выражения; введенный здесь символ е означает пустое слово и в исходный алфавит не входит. Разумеется, применять упрощения выражений в алгебре событий при выполнении операции расширения вовсе необязательно, - это делается лишь с целью упрощения записи. [39]

Легко видеть, что с помощью простейших эквивалентных преобразований, информацию, заданную в любом конечном алфавите, можно записать в алфавите, содержащем только две буквы. Такие преобразования выполняются следующим образом: ищется такое натуральное число т, чтобы число различных слов длины т в двоичном алфавите превышало или было бы равным числу п различных букв исходного алфавита А, после чего каждая из букв алфавита А заменяется словом длины т в двоичном алфавите так, чтобы различным буквам соответствовали различные слова. [41]

Команды первых двух типов устанавливают новое содержимое обозреваемой ячейки ленты, оставляя эту ячейку в поле зрения машины. Первые пять типов команд не зависят от информации на ленте; поэтому, если бы алгоритм был составлен только из команд этих типов, то он записывал бы на ленту всегда одно и то же слово, зависящее только от вида алгоритма, но не от входного слова. Однако добавление шестого типа команд делает алгоритмическую схему Поста такой же универсальной, как алгоритмические схемы Тьюринга и Маркова. Доказательство возможности перехода от любой машины Тьюринга к машине Поста основывается на том, что после кодировки исходного алфавита знаками 0 и 1 каждое состояние машины Тьюринга, работающей с этими знаками, описывается несколькими состояниями машины Поста. [43]

Понятие нормального алгоритма над алфавитом означает следующее. В ряде случаев не удается построить нормальный алгоритм, эквивалентный данному алгоритму в алфавите А, если ис-лользовать в подстановках алгоритма только буквы этого алфавита. В этом случае принято говорить, что построенный алгоритм является алгоритмом над алфавитом А, хотя алгоритм по-прежнему будет применяться лишь к словам в исходном алфавите А. [44]

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