Читать онлайн "Новый ум короля [О компьютерах, мышлении и законах физики]" автора Пенроуз Роджер - RuLit - Страница 80

 
...
 
     



Выбрать главу
Загрузка...

Рекурсивно нумеруемые множества

Существует способ для описания основных результатов, полученных Геделем и Тьюрингом, в графическом виде, на языке теории множеств. Это позволит нам избежать произвольности описания в терминах конкретного символизма или в рамках формальной системы и выделить наиболее существенное. Мы будем рассматривать только множества натуральных чисел (конечные или бесконечные), такие как {4,5,8}, {0,57,100003}, {6}, {0}, {1,2,3,4….,9999}, {1,2, 3,4…. }, {0,2,4,6,8…. } ит. п.; или даже все множество N = {0,1,2,3,4… }, равно как и пустое множество ø = {}. Нас будут интересовать только вопросы вычислимости, скажем: «Какие множества натуральных чисел могут быть сгенерированы с помощью алгоритма, а какие — нет?»

Чтобы сформулировать такой вопрос, мы можем считать, что каждое отдельное число n обозначает определенную строчку символов некоторой формальной системы.

Это будет n-я строка символов, скажем, Qn, согласно заданному в системе лексикографическому порядку («синтаксически корректных») утверждений. Тогда каждое натуральное число будет представлять некое утверждение. При этом множество всех утверждений формальной системы соответствует всему множеству натуральных чисел; а, допустим, теоремы этой системы будут составлять некоторое меньшее множество натуральных чисел, скажем, множество Р. Однако детали произвольной системы нумерации утверждений для нас несущественны. Все, что нам потребуется для установления соответствия между натуральными числами и утверждениями — это заданный алгоритм получения каждого утверждения Qn (записанного должным образом в символических обозначениях) из отвечающего ему натурального числа n; и другой алгоритм для получения n из Qn. Имея эти алгоритмы в своем распоряжении, мы вольны идентифицировать множество натуральных чисел с множеством утверждений конкретной формальной системы.

Давайте выберем формальную систему достаточно непротиворечивую и широкую для того, чтобы включать в себя все действия всех машин Тьюринга — и, более того, «имеющую смысл» с учетом требования «самоочевидной справедливости» ее аксиом и правил вывода. Далее, пусть ряд утверждений Q0, Q1, Q2…. формальной системы имеет доказательства внутри системы. Эти «доказуемые» утверждения будут иметь номера, которые составляют некоторое множество в N — по сути, это множество Р «теорем», рассмотренных выше. Мы уже видели, что существует алгоритм для последовательного построения всех утверждений произвольно заданной формальной системы, имеющих доказательства. (Как отмечено ранее, «n-е доказательство» Пn получается из n алгоритмически. Все, что нам надо — это посмотреть на последнюю строчку n-го доказательства, чтобы найти «n-е утверждение, доказуемое в рамках системы», т. е. n-ю «теорему».) Следовательно, мы имеем алгоритм последовательной генерации элементов Р (при которой возможны и повторения, что для нас не важно).

     

 

2011 - 2018