Возможности вычислительных машин и человеческий разум



         

Глава 2. Откуда возникает мощь вычислительной машины - стр. 27


е. для осуществления каких процедур можно реализовать машины Тьюринга, и, следовательно, машины Тьюринга, поддающиеся имитации на универсальных машинах Тьюринга и, значит, поддающиеся имитации на современных вычислительных машинах. Тьюринг дал ответ и на этот вопрос: можно построить машину Тьюринга для реализации любого процесса, который было бы естественно назвать эффективной процедурой.

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

Хотя мы и вынуждены полагаться на интуицию, давая определение, что "естественно" называть эффективной процедурой. Но можем точно и однозначно указывать, что именно эффективная процедура предписывает нам делать.


Содержание  Назад  Вперед