Алгоритмов сочетания

название, установившееся за рядом конкретных способов конструирования новых алгоритмов из нескольких заданных. В применении к нормальным алгорифмам наибольшую известность получили следующие А. с.: нормальная композиция [img: http://localhost:8080/file/010122-1.jpg] двух нормальных алгорифмов [img: http://localhost:8080/file/010122-2.jpg].нормальное объединение [img: http://localhost:8080/file/010122-3.jpg] двух нормальных алгорифмов [img: http://localhost:8080/file/010122-4.jpg] нормальное разветвление [img: http://localhost:8080/file/010122-5.jpg] двух нормальных алгорифмов [img: http://localhost:8080/file/010122-6.jpg] управляемое нормальным алгорифмом [img: http://localhost:8080/file/010122-7.jpg] нормальное повторение [img: http://localhost:8080/file/010122-8.jpg] нормального алгорифма [img: http://localhost:8080/file/010122-9.jpg], управляемое нормальным алгорифмом [img: http://localhost:8080/file/010122-10.jpg]. Если [img: http://localhost:8080/file/010122-11.jpg] [img: http://localhost:8080/file/010122-12.jpg] - нормальные алгорифмы в нек-ром алфавите А, то упомянутые их сочетания являются нормальными алгорифмами в нек-ром фиксированном расширении Аи удовлетворяют следующим условиям: а) для любого слова [img: http://localhost:8080/file/010122-13.jpg] в [img: http://localhost:8080/file/010122-14.jpg] имеет место [img: http://localhost:8080/file/010122-15.jpg] (теорема композиции); б) для любого слова Рв Аимеет место (теорема объединения); в) для любого слова Рв А [img: http://localhost:8080/file/010122-17.jpg] причем если ([img: http://localhost:8080/file/010122-18.jpg] определено, то определено и [img: http://localhost:8080/file/010122-19.jpg] (теорема разветвления); г) для любых слов [img: http://localhost:8080/file/010122-20.jpg] и [img: http://localhost:8080/file/010122-21.jpg] в A графическое равенство [img: http://localhost:8080/file/010122-22.jpg] имеет место тогда и только тогда, когда может быть указан ряд слов [img: http://localhost:8080/file/010122-23.jpg] в алфавите [img: http://localhost:8080/file/010122-24.jpg] таких, что [img: http://localhost:8080/file/010122-25.jpg] (теорема повторения). Аналогичные теоремы могут быть получены и для Тьюринга машин. В теории рекурсивных функций наибольшее употребление нашли их сочетания, доставляемые оператором подстановки, оператором примитивной рекурсии и m-оператором. Теоремы об А. с. вскрывают весьма существенную особенность осуществленных стандартизации общего понятия алгоритма - их "устойчивость" по отношению к естественным способам А. с. Это обстоятельство является одним из наиболее веских доводов в пользу основной гипотезы теории алгоритмов (Чёрча тезиса). Теоремы об А. с. составляют важный раздел общей теории алгоритмов. Будучи доказаны однажды, они позволяют в дальнейшем убеждаться в осуществимости сложных и громоздких алгоритмов без фактического выписывания определяющих их схем. Значительный интерес для общей теории алгоритмов представляет вопрос о разыскании базиса, позволяющего при фиксированном наборе способов А.- с. порождать любой алгоритм к.-л. интересующего нас класса.