Генерация всех слов в некотором алфавите, удовлетворяющих заданным ограничениям

• Алфавит — конечное множество символов, из которых составляются слова для обработки.
• Схема алгоритма — упорядоченный набор правил подстановки, определяющих, как изменять слова.
• Правила подстановки — инструкции вида:

 * Простое правило: ${\displaystyle L\to D}$, где
   * ${\displaystyle L}$ — левая часть (образец для поиска),
   * ${\displaystyle D}$ — правая часть (замена образца).
 * Заключительное правило: ${\displaystyle L\to \cdot D}$; после его применения алгоритм завершается.

1. **Начало**: задано исходное слово ${\displaystyle V}$ в алфавите алгоритма. 2. **Поиск правила**: на каждом шаге ищется первое по порядку правило, применимое к самому левому вхождению ${\displaystyle L}$ в слово. 3. **Применение правила**:

  * Если найдено простое правило ${\displaystyle L\to D}$, заменяем ${\displaystyle L}$ на ${\displaystyle D}$ и продолжаем работу.
  * Если найдено заключительное правило ${\displaystyle L\to \cdot D}$, заменяем ${\displaystyle L}$ на ${\displaystyle D}$ и завершаем алгоритм.

4. **Окончание**: если ни одно правило не применимо, алгоритм завершается, возвращая текущее слово.

Преобразование двоичного числа в унарное (единичное представление):

• • Алфавит**: { 0, 1, | }

• • Правила**:

1. ${\displaystyle 1\to 0|}$ 2. ${\displaystyle |0\to 0||}$ 3. ${\displaystyle 0\to }$ (пустая строка)

• • Исходное слово**: 101

• • Ход работы**:

1. **Применяем правило 1**:

  101 ⟶ 0|01

2. **Применяем правило 1** к оставшейся '1':

  0|01 ⟶ 0|0|

3. **Применяем правило 2**:

  0|0| ⟶ 00||

4. **Применяем правило 3** к '0's:

  00|| ⟶ 0|| ⟶ || (удаляем все '0's)

• • Результат**: || (две палочки, соответствующие числу 2 в унарном представлении)

• **Тьюринг-полнота**: нормальные алгоритмы Маркова по вычислительной мощности эквивалентны машинам Тьюринга.
• **Эквивалентность моделям вычислений**: они могут описывать любые вычислимые функции и процессы.
• **Принцип нормализации**: утверждает, что любой алгоритмически вычислимый процесс может быть представлен в виде нормального алгоритма.

• **Теория вычислимости**: изучение пределов вычислений и алгоритмических процессов.
• **Языки программирования**: идеи нормальных алгоритмов легли в основу языков, таких как РЕФАЛ, для обработки символов и строк.
• **Символьные вычисления**: используются для формального преобразования выражений и текстов.

Нормальные алгоритмы Маркова являются фундаментальным инструментом в математической логике и теоретической информатике, позволяющим формализовать понятие алгоритма. Они демонстрируют эквивалентность различных моделей вычислений и служат основой для разработки языков программирования и методов обработки строк.