a.) Или программа при данном значении параметра через конечное время заканчивает работу, выдает на выход некое вычисленное ею целое число >=1 и останавливается.
b.) Или программа при данном значении параметра никогда не останавливается (работает вечно).
Причем у одной и той же программы с входным параметром при одном значении параметра может получиться случай a.), а при другом значении параметра может получиться случай b.).
(Вот простейший пример программы, которая никогда не остановится. Программа работает с одним целым числом. Если результат предыдущих вычислений – число четное, то программа прибавляет к нему единицу. Если нечетное – отнимает от него единицу. Программа должна закончить работу и выдать на выход результат вычислений, если этот результат делится без остатка на 3. Если такая программа получит на входе число 4, то она никогда не закончит работу, т.е. никогда не остановится.)
Чтобы программа могла исполняться компьютером, она должна быть написана с помощью определенного набора знаков, понятных данному компьютеру. Этот набор знаков всегда конечен и может быть назван "алфавитом". Предполагается, что знаки этого "алфавита" каким-нибудь образом упорядочены.
Будем считать, что все конечные тексты, составленные из знаков этого "алфавита", раз и навсегда упорядочены:
a.) По размеру, т.е. по количеству содержащихся в них знаков.
b.) При одинаковом размере по "алфавиту".
Такой способ упорядочения текстов гарантирует, что при их просмотре в указанном порядке за конечное число шагов дело дойдет до просмотра любого текста, хотя в целом множество конечных текстов бесконечно. (Этот способ упорядочения использует Гедель в своей знаменитой статье 1931 г. Правда, у Геделя в подробностях немножко не так, но в принципе аналогично.)
Допустим сначала, что каждая "Программа с входным параметром" при любом целом значении параметра >=1 за конечное время заканчивает свою работу и дает на выходе какое-то целое число >=1. (Это допущение ложное, т.к. каждый программист, к своему сожалению, по опыту знает, что программа не всегда заканчивает свою работу. Но допустим это для интереса, чтобы посмотреть, что получится.) В таком случае можно построить матрицу, такую что номер строки i соответствует порядковому номеру программы в списке конечных текстов (если считать только тексты, являющиеся "Программами с входным параметром"), а номер столбца j соответствует значению входного параметра. (Эта матрица похожа на матрицу Aij, описанную выше, только значения ее элементов не 0-9, а любые целые числа >=1). Число Aij – это то число, которое выдает на выходе i-я "Программа с входным параметром" при значении входного параметра, равном j. Тогда можно построить программу (назовем ее "Особая программа"), которая делает следующее:
– получив на входе число j, просматривает наш список конечных текстов и считает встречающиеся "Программы с входным параметром";
– дойдя до j-й по порядку "Программы с входным параметром" запускает ее на выполнение, давая входному параметру значение j;
– ждет, когда эта программа закончит свою работу и выдаст на выходе целое число >=1;
– выдает на свой выход число на 1 большее, и останавливается.
Теперь используем логику диагонального доказательства Кантора. "Особая программа" отличается:
– от 1-й "Программы с входным параметром" результатом работы при значении входного параметра, равном 1;
– от 2-й "Программы с входным параметром" результатом работы при значении входного параметра, равном 2;
– и т.д. до бесконечности.
Т.е. "Особая программа" не совпадает ни с одной конечной "Программой с входным параметром". Но ведь в нашем списке по определению содержатся ВСЕ конечные тексты. А для каждого программиста очевидно, что текст "Особой программы" конечный, и даже не очень большой, т.к. она реализует довольно незамысловатый алгоритм. Получается явное логическое противоречие, из чего следует, что исходное допущение было неверным. И действительно, при каких-то значениях входного параметра "Программа с входным параметром" может никогда не остановиться, т.е. работать вечно. Поэтому когда "Особая программа" получит на входе число j и запустит на выполнение j-ю по счету "Программу с входным параметром" со значением входного параметра, равным j, не исключено, что эта "Программа с входным параметром" никогда не остановится. Тогда и "Особая программа" никогда не остановится, и логика диагонального доказательства не сработает.
Но можно попытаться все-таки провести диагональное доказательство с помощью другого допущения. Допустим, что существует конечная программа "Определитель", которая способна для любой "Программы с входным параметром" и любого значения входного параметра определить, закончит ли работу эта программа или нет. Тогда можно будет создать "Особую программу", которая делает следующее:
– получив на входе число j, просматривает наш список конечных текстов и считает встречающиеся "Программы с входным параметром";
– дойдя до j-й по порядку "Программы с входным параметром", узнает с помощью программы "Определитель", закончит ли работу j-я "Программа с входным параметром" при значении входного параметра, равном j;
– если не заканчивает, то "Особая программа" выдает на свой выход число 1 и останавливается;
– если заканчивает:
– запускает на выполнение j-ю "Программу с входным параметром", давая входному параметру значение j;
– ждет, когда эта программа закончит свою работу и выдаст на выходе целое число >=1;
– выдает на свой выход число на 1 большее, и останавливается.
Применяя снова логику диагонального доказательства Кантора, приходим к выводу, что "Особая программа" не совпадает ни с одной "Программой с входным параметром" из нашего списка. Но ведь в списке есть ВСЕ конечные тексты, в том числе и все конечные "Программы с входным параметром". Таким образом, мы снова приходим к безысходному логическому противоречию. Выходит, "Особая программа" не может быть конечным текстом. Но в ней самой по себе нет ничего бесконечного. Единственный сомнительный момент это то, что она использует программу "Определитель" в качестве подпрограммы. Значит, программа "Определитель" не может быть конечным текстом. Т.е. как конечная программа "Определитель" не может существовать, т.к. обязательно найдется такая "Программа с входным параметром" и такое значение входного параметра, что программа "Определитель" не сможет определить, закончит ли когда-нибудь работу эта программа. А так как одно из утверждений:
– эта "Программа с входным параметром" при данном значении входного параметра когда-нибудь закончит свою работу
или
– эта "Программа с входным параметром" при данном значении входного параметра никогда не закончит свою работу
обязательно является истиной, то выходит что бывают недоказуемые истины.
Таким образом, утверждение "Существуют недоказуемые истины" доказано.
––
Кто-то может спросить: а нельзя ли в таком случае усовершенствовать программу "Определитель"? Разумеется можно, и тогда она совершенно точно определит, закончит ли работу та программа, на которой споткнулся "Определитель" до усовершенствования. Но это не решает проблему радикально, т.к. сколько ни совершенствуй программу "Определитель", обязательно найдется какая-нибудь "Программа с входным параметром", на которой споткнется и самый усовершенствованный "Определитель". Т.е. усовершенствование программы "Определитель" – это бесконечный процесс. Ибо если бы этот процесс мог быть завершен и мог бы быть создан универсальный "Определитель", мы получили бы безысходное логическое противоречие (см. доказательство выше).
––
Программа "Определитель" – это как бы абсолютный математик, который способен доказать все, что вообще возможно доказать, исходя из принятой конечной системы аксиом.
Вывод: если система аксиом конечна, то можно доказать не любое истинное утверждение. Значит, чтобы уменьшить множество недоказуемых истин, приходится расширять систему аксиом. Но при любом расширении системы аксиом, пока она остается конечной, множество недоказуемых истин не станет пустым множеством.
––
Приведенное доказательство имеет прямое отношение к проблеме существования свободной человеческой воли (см. Гл.5 "Физика", п.5.3.). Если бы ВСЕ совершалось только по законам природы, свободная человеческая воля не могла бы существовать, для нее не было бы места в нашем мире.
Допустим, что это действительно так: ВСЕ в нашем мире совершается только по законам природы, и следовательно человеческая воля полностью детерминирована. Значит, человеку только кажется, что он в какой-то степени свободен, а на самом деле никакой, даже самой маленькой свободы у него нет.
Разберем проблему подробнее.
Во-первых, конечно ли множество законов природы или бесконечно? Разумеется конечно. Ведь человек знает лишь конечное количество этих законов, но довольно успешно может предвидеть течение многих природных процессов. А если бы количество законов природы было бесконечным, то известные человеку законы природы составляли бы 0% от общего их числа. А как можно хоть что-нибудь предвидеть, имея 0% информации?
Во-вторых, если бы ВСЕ в нашем мире совершалось только по законам природы (и при этом количество этих законов конечно), то могла бы существовать конечная программа "Определитель", которая по запросу человека на основании законов природы давала бы абсолютно точный прогноз будущего, и уж во всяком случае была бы способна ответить на любой разумный вопрос.
Конечность такой программы "Определитель" следует из того, что рационально составленная программа, опирающаяся лишь на конечное число основоположений (в данном случае законов природы) обязательно будет конечной (т.е. ее текст будет конечным). Не говоря уже о том, что бесконечная программа – это нонсенс, ведь чтобы ввести в компьютер бесконечный текст понадобилось бы бесконечное время и бесконечный компьютер.
Но только что было доказано, что в принципе не может существовать даже такой скромный "Определитель", который способен для любой "Программы с входным параметром" определить, закончит она когда-нибудь работу или нет. А значит, тем более невозможен тотальный "Определитель", способный ответить на любой вопрос, и даже выдающий точный прогноз развития событий. И дело даже не в том, что человечество пока что не способно написать такую программу-"Определитель", а в том, что такая программа В ПРИНЦИПЕ НЕ МОЖЕТ СУЩЕСТВОВАТЬ, само предположение о возможности существования такой программы приводит к логическому противоречию (см. доказательство выше в этом же параграфе).
Из изложенного однозначно следует, что хотя многое в мире совершается по законам природы, но все-таки НЕ ВСЕ, а значит есть и другие факторы, влияющие на ход событий. Таких факторов может быть только два:
1.) Божественная Воля.
2.) Свободная человеческая воля.
Но так как непосредственное вмешательство Божественной Воли в текущие события представляется сомнительным, то остается только один вариант: кроме законов природы на ход событий в мире может в определенной степени влиять свободная человеческая воля.