Составить нормальный алгоритм, обеспечивающий выполнение операции сложения в троичной системе счисления.
Алфавит будет содержать символы: А = {0, 1, 2, +}; система подстановок: 0 + 1 → 1, 1 + 1 → 2, 2 + 1 → +10, +1 → 1. Применим алгоритм для различных исходных слов:
Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами допустимых подстановок. Нормальный алгоритм Маркова можно рассматривать как стандартную форму для задания любого алгоритма. Данная форма представления алгоритма важна не только с точки зрения проведения исследований в теории алгоритмов, но она послужила основой специализированного языка символьных преобразований в системах искусственного интеллекта.