Cтраница 2
Формальные определения 4, 5 и 7 устанавливают критерии правильности программы, в основе которых лежит понятие вычислимости и которые не накладывают никаких требований на ее отдельные процедуры. Принимая это во внимание, мы рассмотрим следующую программу. [16]
Факт переноса вычисления в дедуктивный формализм сам по себе еще не обязательно дает какое-либо пригодное для применений уточнение понятия вычислимости, если не потребовать, чтобы оперирование с выражениями происходило в этом формализме по четко описанным правилам. [17]
Для каждого из этих подходов, равно как и для друг подходов к вычислимости на области D, использующих в треннюю структуру D, мы убеждаемся, как и следовало ож дать, что они эквивалентны подходу, основанному на перено понятия вычислимости с N на D с помощью кодирован И наоборот, каждое естественное понятие вычислимости области D индуцирует альтернативное ( но эквивалентнс понятие вычислимости на N через кодирование, как мы Э4 видели в § 5 относительно вычислимости по Посту. [18]
Для каждого из этих подходов, равно как и для друг подходов к вычислимости на области D, использующих в треннюю структуру D, мы убеждаемся, как и следовало ож дать, что они эквивалентны подходу, основанному на перено понятия вычислимости с N на D с помощью кодирован И наоборот, каждое естественное понятие вычислимости области D индуцирует альтернативное ( но эквивалентнс понятие вычислимости на N через кодирование, как мы Э4 видели в § 5 относительно вычислимости по Посту. [19]
Бели такой метод существует, то тьюрингово понятие вычислимости оказывается слишком узким: в этом случае существуют вычислимые функции, не являющиеся вычислимыми по Тьюрингу, и, в частности, такова функция и. Бели же тьюрингово понятие вычислимости достаточно широко, чтобы охватить все функции, вычислимые хоть в каком-либо интуитивном смысле, то сформулированная проблема оказывается неразрешимой. [20]
Это воистину замечательный факт, который подчеркивает глубоко объективный и математичный характер понятия вычислимости. На первый взгляд, понятие вычислимости по Черчу не связано с вычислительными машинами. И тем не менее, оно имеет непосредственное отношение к практическим аспектам вычислений. В частности, мощный и гибкий язык программирования LISP включает в себя как существенный элемент основные структуры исчисления Черча. [21]
Несущественно, принимаем мы этот тезис для произвольных натуральных чисел или же ограничиваемся лишь положительными целыми. Не обладая точной общей формулировкой понятия вычислимости, мы не можем доказать этот тезис; мы можем лишь убедиться в его правдоподобии в результате исследований, подобных тем, что проведены нами в гл. [22]
Таким образом, объекты переработки, или состояния ( в частности, исходные данные и результаты), алгоритмов Колмогорова из работы [5] и обзоров [13, 14] различаются. Можно показать, что для таких функций понятия вычислимости алгоритмами Колмогорова из [5] и неориентированными машинами Колмогорова из [13] совпадают. [23]
Это охватывает случай, когда р - вычислимое действительное число. Объединяя оба случая, получим следующий аналог теоремы 2 для понятий вычислимости. [24]
Вначале мы вводим понятие счетности ( перечислимости, нумеруемости) и устанавливаем существование несчетных множеств Затем определяется понятие вычислимости посредством машин Тьюринга и доказывается, что проблема их остановки неразрешима. Мы вводим еще два понятия вычислимости и доказываем их эквивалентность вычислимости по Тьюрингу. Неразрешимость ( элементарной) логики первого порядка выводится непосредственно из неразрешимости проблемы остановки, без использования арифметичации Затем устанавливаются корректность и полнота некоторой системы логического вывода. Теорема Левенгейма-Сколема в редакции всякая интерпретация обладает элементарно эквивалентной подинтерпретацией со счетной областью устанавливается при доказательстве корректности и полноты. [25]
Поскольку эти операции имеют дело с бесконечными объектами ( функциями или множествами), они как будто лежат в стороне даже от нашего неформального понятия вычислимости, которое, очевидно, применяется к конечным объектам. Тем не менее, каю мы убедимся, индекс функции ФхФу эффективно находится по-индексам х и у. В следующих примерах и упражнениях мы увидим, что многие другие операции являются эффективными, если их рассматривать как операции над индексами затраги - ваемых объектов. [26]
Здесь мы приведем лишь существенный для данного контекста результат этих исследований. По поводу его обоснования мы отсылаем читателя к Приложению II 2), а здесь только отметим, что это обоснование опирается на одно предположение, которое вследствие неточности обиходного понятия вычислимости лишь может быть сделано правдоподобным и оправданным последующими результатами. Речь идет о предположении, что любая вычислительная процедура может быть изображена в виде вывода в подходящем, специально для этой цели построенном дедуктивном формализме, причем этот формализм может быть устроен так ( и это существенно. [27]
В заключительной, четырнадцатой, главе впервые в этой книге вводятся бесконечные системы. Показано, что вещественные числа образуют несчетное множество. Определяется понятие вычислимости, объясняется его связь с машинами Тьюринга. Наконец, понятие машинной вычислимости связывается с некоторыми идеями математической лингвистики и проблемой классификации языков программирования. [28]
Вначале мы вводим понятие счетности ( перечислимости, нумеруемости) и устанавливаем существование несчетных множеств Затем определяется понятие вычислимости посредством машин Тьюринга и доказывается, что проблема их остановки неразрешима. Мы вводим еще два понятия вычислимости и доказываем их эквивалентность вычислимости по Тьюрингу. Неразрешимость ( элементарной) логики первого порядка выводится непосредственно из неразрешимости проблемы остановки, без использования арифметичации Затем устанавливаются корректность и полнота некоторой системы логического вывода. Теорема Левенгейма-Сколема в редакции всякая интерпретация обладает элементарно эквивалентной подинтерпретацией со счетной областью устанавливается при доказательстве корректности и полноты. [29]
Например мы могли бы опустить ( iii) и ( iv), сохраняя ( п), или вместо ( и) мы могли бы допустить, чтобы машина была снабжена лентой, бесконечной только в одну сторону и добавить требование, что она должна остановиться, если оказалась в такой ситуации, из которой таблица требует движения влево от самой левой клетки. После § § 68 и 69 будет нетрудно показать, что каждое из этих понятий вычислимости эквивалентно нашему ( ср. [30]