Читаем Новый ум короля: О компьютерах, мышлении и законах физики полностью

Часть доказательства, приведенного Геделем, содержало некий очень сложный и детализированный кусок. Однако нам не обязательно разбираться во всех его тонкостях. Основная идея, в то же время, была проста, красива и глубока. И ее мы сможем оценить по достоинству. В «сложной» части (которая, впрочем, содержит много остроумных рассуждений) подробно показано, каким образом частные правила вывода и использование различных аксиом формальной процедуры могут быть представлены в виде арифметических операций. (Хотя в сложной части становится понятной плодотворность этих действий!) Для этого представления нам необходимо будет найти какой-нибудь удобный способ нумерации утверждений при помощи натуральных чисел. Один из способов мог бы заключаться в том, чтобы использовать своего рода «алфавитный» порядок для строчек символов формальной системы, имеющих одинаковую длину, упорядочить заранее строчки по длине. (Таким образом, за выстроенными в алфавитном порядке строками из одного символа будут следовать строки длиной в два символа, также упорядоченные по алфавиту; за ними идут строки из трех символов и так далее.) Это называется лексикографическим порядком [72]. В действительности Гедель использовал более сложную систему нумерации, но различия в данном случае для нас несущественны. Нас же должны в особенности интересовать функции исчисления высказываний одной переменной, наподобие введенной выше G( ω). Пусть n- я(из пронумерованных выбранным способом строк символов) такая функция от аргумента ω обозначается

P n( ω).

Мы можем допустить, чтобы наша нумерация по желанию была несколько «либеральна» в отношении синтаксически некорректных выражений. (Это позволит значительно упростить перевод системы на язык арифметических операций по сравнению со случаем, когда мы будем стараться исключить из рассмотрения синтаксически некорректные выражения.) Если P n(ω) синтаксически корректно, то оно будет представлять из себя некоторое совершенно определенное арифметическое выражение, в котором фигурируют два натуральных числа п и ад. Каков будет конкретный вид этого выражения — зависит от особенностей системы нумерации, которую мы выбрали. Но эти детали рассматриваются в «сложной» части и сейчас нас не касаются. Пусть П n будет n-м доказательством. (Опять же мы можем использовать «либеральную нумерацию», когда для некоторых значений n выражение П n не является синтаксически корректным и, тем самым, не доказывает никакую теорему.)

А теперь рассмотрим следующую функцию исчисления высказываний от натурального числа ω:

— Eк.с.x[ П x доказывает P ω( ω)].

В выражении в квадратных скобках частично присутствуют слова, но, тем не менее, это — абсолютно точно определенное выражение. Оно говорит о том, что доказательство номер х является доказательством утверждения Р ω(), примененного к самому ω. Находящийся за скобками квантор существования с отрицанием позволяет исключить из рассмотрения одну из переменных («не существует такого х, что…»), приводя нас в конечном счете к арифметической функции исчисления высказываний, зависящей только от ω. В целом данное выражение утверждает, что не существует доказательства Р ω( ω). Я буду предполагать, что оно оформлено синтаксически корректным образом (даже если Р n( ω) некорректно — поскольку тогда выражение было бы истинным за невозможностью существования доказательства синтаксически некорректного утверждения). На самом деле, в результате сделанного нами перевода на язык арифметики, написанное выше будет в действительности неким арифметическим выражением, включающим натуральное число ω(тогда как в квадратных скобках окажется четко определенное арифметическое выражение, связывающее два натуральных числа х и ω). Конечно, возможность представления этого выражения в арифметическом виде далеко не очевидна, но она существует. Рассуждения, приводящие к этому заключению, составляют наиболее трудную задачу в «сложной» части доказательства Геделя. Как и ранее, непосредственный вид арифметического выражения будет зависеть от способа нумерации и в еще большей степени от конкретной структуры аксиом и правил вывода, принятых в нашей системе. Поскольку все это входит в «сложную» часть доказательства, то в данном случае нас не интересует.

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

— Eк.с.x[ П х доказывает P ω( ω)] = Р k( ω).

Теперь исследуем эту функцию при определенном значении: ω= k. Мы получаем:

Eк.с.х[ П х доказывает P k( k)] = P k( k)

Перейти на страницу:

Все книги серии Синергетика: от прошлого к будущему

Похожие книги

Что такое полупроводник
Что такое полупроводник

Кто из вас, юные читатели, не хочет узнать, что будет представлять собой техника ближайшего будущего? Чтобы помочь вам в этом, Детгиз выпускает серию популярных брошюр, в которых рассказывает о важнейших открытиях и проблемах современной науки и техники.Думая о технике будущего, мы чаще всего представляем себе что-нибудь огромное: атомный межпланетный корабль, искусственное солнце над землей, пышные сады на месте пустынь.Но ведь рядом с гигантскими творениями своих рук и разума мы увидим завтра и скромные обликом, хоть и не менее поразительные технические новинки.Когда-нибудь, отдыхая летним вечером вдали от города, на зеленом берегу реки, вы будете слушать музыку через «поющий желудь» — крохотный радиоприемник, надетый прямо на ваше ухо. Потом стемнеет. Вы вынете из кармана небольшую коробку, откроете крышку, и на матовом экране появятся бегущие футболисты. Телевизор размером с книгу!В наш труд и быт войдет изумительная простотой и совершенством автоматика. Солнечный свет станет двигать машины.Жилища будут отапливаться... морозом.В городах и поселках зажгутся вечные светильники.Из воздуха и воды человек научится делать топливо пластмассы, сахар...Создать все это помогут новые для нашей техники вещества — полупроводники.О них эта книжка.

Глеб Анфилов , Глеб Борисович Анфилов

Детская образовательная литература / Физика / Техника / Радиоэлектроника / Технические науки