Концепція Н. а. спеціально пристосована для реалізації алгоритмів що діють над словами в тих або інших алфавітах. При цьому під алфавітом в математиці розуміється будь-який кінцевий набір чітко відмітних один від одного графічних символів (букв), а під словом в даному алфавіті — довільний кінцевий ланцюжок букв цього алфавіту. Ланцюжок, що зовсім не містить букв, також вважається словом в даному алфавіті (порожнє слово). Наприклад, ланцюжки «іїаам», «книга», «гамма» є словами в російському алфавіті, а також в шестибуквеному алфавіті {до, н, і г, а, м-код}. Елементарним актом перетворення слів в алгоритмічних процесах, Н, що задаються. а., є т.з. операція «підстановки замість першого входження». Хай Р , Q , R — слова в деякому алфавіті. Результатом підстановки Q замість першого входження Р в R називається слово å ( R , Р , Q ), отримуване таким чином. Якщо Р входить в R , тобто R уявно у вигляді S 1 Ps 2 , то серед таких вистав відшукується вистава з найбільш коротким словом S 1 і вважається å ( R , Р , Q ) = S 1 Qs 2 . Якщо ж Р не входить в R , то å ( R , Р , Q ) = R . Так å (гамма, а, е) = гема.
Для завдання Н. а. необхідно фіксувати деякий алфавіт А , що не містить букв «®» і « · », і впорядкований список слів вигляду Р ® Q (проста формула підстановки) або Р ® · Q (укладе. формула підстановки), де Р і Q — слова в А . Формули підстановок прийнято записувати один під одним в порядку дотримання, об'єднуючи їх зліва фігурною дужкою. Фігура, що виходить, називається схемою Н. а. Початковими даними і результатами роботи Н. а.
де d i (1 £ i £ n ) означає «®» або «®», розвертається таким чином. Відшукується найменше i , при якому P i входить в R . Якщо все P i не входять в R , то робота можна побудувати Н. а., що є композицією і, тобто реалізовуючий наступний інтуїтивний алгоритм: «спочатку виконати алгоритм, потім до результату застосовувати ».
Співвідношення між інтуїтивними алгоритмами і Н. а. описується висунутим А. А. Марковим принципом нормалізації: всякий алгоритм, що переробляє слова в даному алфавіті А в слова в цьому ж алфавіті, може бути реалізований за допомогою Н. а. у деякому розширенні А . [Легко вказати дуже прості алгоритми в А , Н, що не реалізовуються. а. у A ; з іншою сторони, завжди можна обмежитися двохбуквеним (і навіть одинбуквеним) розширенням A .] Принцип нормалізації еквівалентний тезі Черча і, аналогічно останньому, не може бути доведений із-за неточності інтуїтивної концепції алгоритму.
Літ.: Марков А. А., Теорія алгоріфмов, М. — Л., 1954 (Тр. Математичного інституту АН(Академія наук) СРСР, т. 42); Мендельсон Е., Введення в математичну логіку, пер.(переведення) з англ.(англійський), М., 1971.
