для осуществления каких процедур можно
е. для осуществления каких процедур можно реализовать машины Тьюринга, и, следовательно, машины Тьюринга, поддающиеся имитации на универсальных машинах Тьюринга и, значит, поддающиеся имитации на современных вычислительных машинах. Тьюринг дал ответ и на этот вопрос: можно построить машину Тьюринга для реализации любого процесса, который было бы естественно назвать эффективной процедурой.
Этот тезис, называемый часто тезисом Черча (по имени логика Алонзо Черча), сформулировавшего его в ином, чем Тьюринг, контексте, не может быть доказан, поскольку содержит слово "естественно". Здесь у нас возникает в некотором смысле круг в доказательстве [Прим. перев.: Круг в доказательстве - логическая ошибка, состоящая в том, что доказываемый тезис обосновывается с использованием в данном доказательстве того же самого тезиса в качестве одного из оснований. Понятие круга в доказательстве - частный случай общего понятия порочного круга (или ложного круга), другим частным случаем которого является понятие круга в определении (когда, например, термин "А" определяется через термин "В", а "В" - через "А")]: любой процесс, поддающийся описанию в терминах машины Тьюринга, является эффективной процедурой и наоборот. Однако реальную интуитивную силу этой идее придает факт, что доказана эквивалентность четырех совершенно различных и независимо друг от друга полученных формулировок концепции "эффективной вычислимости" вычислимости в формализме Тьюринга и, следовательно, друг другу. Как замечает М. Минский, "доказательство эквивалентности двух или нескольких определений всегда производит неотразимый эффект, если эти определения отражают различные опыт и мотивацию"2 [Прим. перев.: В переводе цитируемой книги М. Минского на русский язык смысл этой фразы передан неверно]
Хотя мы и вынуждены полагаться на интуицию, давая определение, что "естественно" называть эффективной процедурой. Но можем точно и однозначно указывать, что именно эффективная процедура предписывает нам делать.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий