Математическая логика и теория алгоритмов

«Знаете что, скрипка? Мы ужасно похожи: Я вот mooice ОРУ- а доказать ничего не умею!» В. Маяковский § 11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Чёрча) С целью дать строгое (с некоторых позиций) определение алгоритма были введены понятия нормального алгоритма и алго­ ритма (машин) Тьюринга. Было выяснено, что оба эти подхода приводят к равносильным понятиям алгоритма, т.е. то, что можно осуществить с помощью одного из этих алгоритмов, можно осу­ ществить с помощью другого, и наоборот. Естественно задаться вопросом: насколько общими являются эти схемы вычислений с помощью нормального алгоритма или алгоритма Тьюринга и насколько эти понятия близки к ии1-уитивному понятию любого алгоритма? На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы: Для всякого алгоритма В в алфавите Л существует вполне эквивалентный ему нормальный алгоритм С над т.е. VF в А: В (Р) =С(Р). Иначе эта гипотеза формулируется так: Всякий алгоритм может быть задан посредством некоторой машины Тьюринга и реализован в этой машине. Эту гипотезу называют основной гипотезой или основным тезисом теории алгоритмов, или принципом нормапизации, или тезисомЧёрча. Ясно, что эта гипотеза не носит характера теоремы и не может быть, следовательно, доказана, ибо в нее входит нестрогое (неопре­ деленное) понятие алгоритма. Уверенность в истинности гипотезы основана, главным образом, на опыте. Известные алгоритмы, которые 244