Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Описание нормальных алгоритмов. Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.
Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам, из символов которого алгорифм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где и – два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где и – два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).
Примером схемы нормального алгоритма в пятибуквенном алфавите может служить схема
Процесс применения нормального алгорифма к произвольному слову в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть – слово, полученное на предыдущем шаге работы алгорифма (или исходное слово , если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в , то работа алгорифма считается завершённой, и результатом этой работы считается слово . Иначе среди формул подстановки, левая часть которых входит в , выбирается самая первая. Если эта формула подстановки имеет вид , то из всех возможных представлений слова в виде выбирается такое, при котором – самое короткое, после чего работа алгорифма считается завершённой с результатом . Если же эта формула подстановки имеет вид , то из всех возможных представлений слова в виде выбирается такое, при котором – самое короткое, после чего слово считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.
Например, в ходе процесса применения алгорифма с указанной выше схемой к слову последовательно возникают слова , , , , , , , , , и , после чего алгорифм завершает работу с результатом . Другие примеры смотрите ниже.
Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот – любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча-Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».
Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования – например, в языке Рефал.
3. Пример 1: использование алгоритма Маркова для преобразований над строками
Алфавит:
{ а...я, А...Я, пробел, точка }
Правила:
Исходная строка:
Я купил кг Аов в Т М.
При выполнении алгоритма строка претерпевает следующие изменения:
На этом выполнение алгоритма завершится (так как будет достигнута формула № 5, которую мы сделали заключительной).
4. Пример 2: преобразование чисел
Данный алгоритм преобразует двоичные числа в «единичные» (в которых записью целого неотрицательного числа N является строка из N палочек). Например, двоичное число 101 преобразуется в 5 палочек:
Дата публикования: 2014-10-20; Прочитано: 507 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!