Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Есть еще многоленточные машины Тьюринга и другие модификации (варианты) подхода к понятию алгоритма, такие как машины Поста, машины Минского и др. Однако детальный анализ показывает, что все эти понятия равносильны в том смысле, что то, что можно осуш,ествить (вычислить) с помош,ью одной из этих машин, можно сделать (вычислить) с помош,ью машины Тьюринга, а следовательно, и с помош,ью нормального алгоритма, и наоборот. § 11. Основная гипотеза теории алгоритмов (нринцин нормализации или тезис Черча) С целью дать строгое (с некоторых позиций) определение алгоритма были введены понятия нормального алгоритма и алгоритма (машин) Тьюринга. Было выяснено, что оба эти подхода приводят к равносильным понятиям алгоритма, т.е. то, что можно осуш,ествить с помош,ью одного из этих алгоритмов, можно осуш,ествить с помош,ью другого, и наоборот. Естественно задаться вопросом: насколько обш,ими являются эти схемы вычислений с помош,ью нормального алгоритма или алгоритма Тьюринга и насколько эти понятия близки к интуитивному понятию любого алгоритма? На эти вопросы современная теория алгоритмов предлагает ответ в виде следуюш,ей гипотезы: Для всякого алгоритма В в алфавите А суш,ествует вполне эквивалентный ему нормальный алгоритм С над А, т.е. VP ъ А: В{Р) = С{Р). Иначе эта гипотеза формулируется так. Всякий алгоритм может быть задан посредством некоторой машины Тьюринга и реализован в этой машине. Эту гипотезу называют основной гипотезой, или основным тезисом теории алгоритмов, или принципом нормализации, или тезисом Черча. Ясно, что эта гипотеза не носит характера теоремы и не может быть, следовательно, доказана, ибо в нее входит нестрогое (неопределенное) понятие алгоритма. Уверенность в истинности гипотезы основана, главным образом, на опыте. Известные алгоритмы, которые были придуманы в течение многих тысячелетий, могут быть заданы посредством нормального алгоритма (машины Тьюринга). Имеются и другие соображения, подтверждаюш,ие правильность основной гипотезы. В § 6 данной главы были рассмотрены различные операции над нормальными алгоритмами (аналогичные операции можно рассмотреть и для алгоритмов (машин) Тьюринга), причем каждый раз оказывалось, что результируюш,ий алгоритм снова является нормальным алгоритмом. Заметим, что внутри самой теории алгоритмов основная гипотеза не применяется. В теории алгоритмов исследуется нормальный алгоритм, машина Тьюринга, машины Поста и т.п., устанавливается связь между ними и т.д. 164