fregimus: (oak)
Я набрел на эту задачу случайно — на одном вебсайте предлагалось решить ее на разных языках программирования. Когда я задумался, оказалось, что программировать вовсе не надо, и задачу можно решить на обороте конверта. [livejournal.com profile] fregima говорит, что она эту задачу видела уже давно, так что, может, я просто не находил ее раньше. Формулируется она так.

Составить число перестановкой цифр от 1 до 9 включительно так, чтобы:
* все число делилось без остатка на 9;
* число без последней цифры делилось на 8;
* без двух последних на 7;
* и так далее, пока цифры не кончатся.

Решение единственное, и, как оказалось, перебирать нужно не 9! вариантов, а много меньше. Можно сузить область поиска до 576 чисел, можно до 96, можно до 48, а можно и еще дальше. Больше подсказывать не буду.

Кстати, интересно, что очевидное расширение этой задачи на другие системы счисления дает единственное решение еще в 14-ричной системе. Но этот вариант я на бумажке решать не пробовал, он уже компьютером вычислен!
Tags:
fregimus: (q)
Друзья, что-то я никак не соображу, куда мне смотреть. Вопрос возник из функции (плотности?) вероятности, определенной только для рациональных чисел.

Если у нас есть конечное число событий, то сумма их вероятностей должна быть равна 1. Если множество событий континуально-бесконечное, то мы отображаем пространство событий на вещественные числа, и говорим, что в этом случае интеграл функции плотности вероятности по всей вещественной оси равен 1. Но как быть со счетно-бесконечными пространствами событий? В распределениях с целым носителем к 1 сходится сумма бесконечного ряда, но как быть с рациональными?
Tags:
fregimus: (oak)
Как и у большинства людей, у меня нет простого интуитивного восприятия вероятности. Пытаюсь себя заставлять. Вот две задачки (вторая недавно была в журнале у [livejournal.com profile] mi3ch'а, а первая, кажется, из де Гроота, хотя обе, несомненно, старше) для развития такой интуиции.

1. Имеется две одинаковые коробки с шарами. В первой коробке поровну черных и белых шаров, а во второй только черные. Сперва случайным образом с равной вероятностью выбирается одна из коробок. Затем из выбранной коробки выбирается случайный шар. Этот шар оказывается черным. Какова вероятность, что при случайном равновероятном выборе нам попался ящик с одними черными шарами? Бонус за ответ, не основанный на теореме Байеса — требуется его «проинтуировать», а не вывести.

2. Ученые открыли новую инфекцию. Никаких симптомов при заражении нет, так что подозревать у себя болезнь нет никаких оснований. Однако, все-таки опасна: она значительно повышает риск умереть от внезапной остановки сердца. По счастью, инфекция редкая: только один человек из 10 000 инфицирован. Имеется анализ на инфекцию, работающий с точностью 99% (1% ошибки возможен в обе стороны — и назвать больного здоровым, и здорового больным). N. сдал этот анализ, и он показал, что N. инфицирован. Какова вероятность, что он болен на самом деле? Для тех, кто уже обсуждал это решение недавно, добавим еще один вопрос: если после первого положительного анализа N. прошел анализ еще раз, и он опять выдал положительный результат, то какова вероятность, что N. заражен?
Tags:
fregimus: (oak)
Математическое рассуждение может быть, хоть и изрядно схематично, представлено работой двух способностей, которые мы можем назвать мастерством (ingenuity) и интуицией. Деятельность интуиции состоит в производстве спонтанных суждений, не являющихся результатом осознанной цепочки рассуждений. Такие суждения часто, но отнюдь не заведомо верны (оставим без рассмотрения вопрос о том, что имеется в виду под «верным»). Часто бывает возможно найти другой путь проверки верности интуитивного суждения. Мы можем, например, рассудить, что все положительные целые однозначно раскладываются на простые множители; подробные математические выкладки приведут к тому же результату. В этих выкладках окажутся задействованными другие интуитивные суждения, но уже менее сомнительные, чем начальное суждение об однозначности разложения. Не стоит пытаться разъяснить идею «интуиции» более явно.

Turing A. Systems of Logic Based on Ordinals, 11: The Essential Turing, B. J. Copeland, ed., Oxford Uni Pr: 2004.
Tags:
fregimus: (Default)
Если вы еще не читали рассказа [livejournal.com profile] akukleva о вещественных числах и реальности, то вы, полагаю, немало упустили! Для меня вещественные числа всегда представляли собой загадку. Чем дольше я о них думаю, тем менее я их могу себе представить. Сложная тема.
Я хочу рассказать о двух основополагающих в науке абстракциях, которые вызывают сомнения у людей, тяготеющих к объективизму и другим формам жесткого реализма, отказывающего в состоятельности любым понятиям, не проистекающим напрямую из объективных свойств наблюдаемой физической реальности. Я постараюсь как можно более детально объяснить, почему обе эти абстракции не смотря на свою эфемерность совершенно необходимы для анализа и понимания этой самой объективной реальности. Речь пойдёт о бесконечности и о точке.
Tags:
fregimus: (Default)
Возьмем словарь синонимов и антонимов. Для каждого слова (или значения слова) даются синонимические значения и противоположные. Какую интересную информацию о языке можно выделить, механически получить, переработав этот словарь? В статье [1] описывается удивительно простой и изящный подход, приведший к получению весьма нетривиального результата.

Возьмем все слова... )
_________________________________
1. Samsonovic AV, Ascoli GA (2010) Principal Semantic Components of Language and the Measurement of Meaning. PLoS ONE 5(6): e10921. doi:10.1371/journal.pone.0010921
fregimus: (Default)
Задача по теории вероятности: 57 человек подписали некую историческую декларацию.

1. Какова вероятность, что из них а) двое; б) двое или больше умрут в один и тот же день года?
2. Какова вероятность, что из них а) двое; б) двое или больше умрут в тот же исторический день года, в который была подписана декларация?
3. Какова вероятность, что из них а) двое; б) двое или больше умрут в один день и год, и это будет юбилейный день подписания декларации?

Будем считать, что вероятность умереть в любой день года одинакова, и что високосных лет не бывает. Для вопроса 3, пусть вероятность умереть в любой год после подписания, при условии, что подписавший к этому году еще жив, одинакова и равна p = 1/40 (это, конечно, упрощение, потому что вероятность умереть в данный год с возрастом человека увеличивается).

А навеяна эта задача вот каким любопытным историческим фактом: из 57 человек, подписавших Декларацию независимости США 4 июля 1776 г., двое, Томас Джефферсон и Джон Адамс, умерли в 50-ю годовщину подписания декларации, 4 июля 1826 г. Джефферсону было 83 года, а Адамсу — 91.

Оказывается, кстати, что 14% школьников в возрасте 12—17 лет полагают, что колонии объявили независимость от Франции, а еще 5% — что от Канады.
Tags:
fregimus: (Default)
Сегодня исполняется 100 лет со дня рождения Алана Тьюринга, одного из величайших математиков XX в. О судьбе Тьюринга я уже писал здесь и здесь.

На главной странице «Гугола» сегодня действующая машина Тьюринга. А вот несколько действующих машин на «Ютубе» — из чего только их не строят!


http://www.youtube.com/playlist?list=PLF87F259C658F6872
Tags:
fregimus: (Default)
Один моллюск, пока рос, частенько размышлял о фрактале Серпинского. И вот что из этого вышло:



Моллюсков домик ископал [livejournal.com profile] avkh. Еще такие здесь, здесь и здесь. А Правило 110, между прочим, обладает вычислительной мощностью универсальной машины Тьюринга. А говорите, моллюски, моллюски…
Tags:
fregimus: (bugsy)
Четных чисел, друзья мои, гораздо больше, чем нечетных. Рассмотрим четные числа: добрая половина из них делится на 4. Возьмем все нечетные и удвоим каждое из них. Из одного нечетного числа получается ровно одно четное, все различные, и ни одно из этих четных, само собой ясно, на 4 не делится. Выходит, что нечетных чисел едва хватит, чтоб из них половину от четных наделать. Такие дела QED.
fregimus: (Default)
В некоей стране каждая семья по традиции имеет ровно одного ребенка-мальчика. Если в семье рождается девочка, то семья рожает следующего ребенка, и так далее, пока не родится мальчик, после чего семья перестает рожать детей. Вероятность рождения мальчика равна 1/2. Какова доля мальчиков в общем количестве детей в этой стране?

Строго вопрос следует переформулировать так: каков предел доли мальчиков, когда количество семей стремится к бесконечности, или, иными словами, каково матожидание доли мальчиков среди всех детей.

Комментарии не прячу, так что там могут быть решения; если хотите поломать голову, то заглядывать не торопитесь.
Tags:
fregimus: (Default)
Задолжал сложную эстафетную задачу [livejournal.com profile] ushastyi. Отдаю долг.

Mos maiorum народа нмого запрещает им строить деревни ближе, чем на дистанции одного сурового взгляда Великого Нмого (назовем для простоты это расстояние 1 св). Тем не менее, аборигены стараются располагать свои деревни так, чтобы расстояние между ними было поменьше — и торговля процветает, и к знакомым чайку попить недалеко идти.

На острове Нмала находится 6 деревень нмого, и, как говорят, расположены они так, что расстояние между двумя самыми удаленными друг от друга деревнями минимально возможное (назовем оптимальным и такое расположение, и расстояние между самыми удаленными друг от друга деревнями в оптимальном расположении).

1. (Частичное неконструктивное решение.) Найти и обосновать верхнюю и нижнюю границу оптимального расстояния (доказать, что оно находится в интервале [pq]). Тривиальным ответом на этот вопрос будет, например, интервал [1; 5], т. к. самые дальние деревни не могут быть ближе, чем 1 св по построению, а 5 соответствует деревням, расположенным на одной линии. Но это очень слабое решение, а чем более стягивается интервал, тем менее тривиальным делается доказательство.

2*. (Конструктивное решение.) Найти расположение деревень на острове Нмала и доказать, что расстояние между самыми удаленными деревнями минимальное из возможных.

3****. Решить вопросы 1 и 2 для общего случая N > 6 деревень. (Доб. Насколько я знаю, общего решения не известно, но попытаться стоит!)

Деревни, само собой, следует полагать безразмерными точками.

Кто предложит лучшее решение, тот в наказание будет задавать следующую задачу у себя в журнале.

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

Доб. Все деревни находятся в одной плоскости. Евклидовой, предупреждая дальнейшие сомнения.
Tags:
fregimus: (Default)
Крейсер «Аврора» стреляет большим чугунным ядром по Зимнему дворцу. Воздух между крейсером и дворцом предусмотрительно откачан, так что аэродинамическим сопротивлением следует пренебречь. Какой геометрической кривой описывается траектория ядра? Ответ должен быть общим и содержать объяснение; частные вырожденные случаи (например, прямая линия при выстреле вертикально вверх) неинтересны.

Комментарии спрятаны. Ответ и чествование победителей завтра.

Ответ )
Tags:
fregimus: (Default)
Вдруг осознал, что ни разу не вертел в руках Лоренцева аттрактора. Вот: код... )


(кликабельно)
Tags:
fregimus: (q)
У меня возникла комбинаторная задачка со стековой машиной, которую было бы интересно проанализировать.

Представьте себе игру с перекладыванием карточек, целью которой является переставить карточки с буквами из исходного порядка в заданный. ... )
Tags:
fregimus: (Default)
Прежде, чем вы начнете читать этот текст, я попрошу вас ответить на два простых вопроса, не заглядывая в другие ответы. Первый: по каким траекториям обращаются планеты вокруг Солнца? Второй: что такое парабола? Если вам удобно, оставьте ваши ответы, мне будет интересно, угадал я их или нет; отвечать на них не обязательно, но обязательно, чтобы ответы были честными: до прочтения текста и комментариев. Правильного ответа на них нет; это вопросы о вашей интуиции, а правильной интуиции, само собой, быть не может. А разговор наш будет именно об истории астрономической и математической (в приложении к небесной механике) интуиции, и о ее возможном дальнейшем развитии.

Идея сопоставления пяти планет пяти правильным многогранникам... )
fregimus: (Default)
Стихи А. А. Маркова-младшего. Говорят, самое полное издание.
Гиппомонада

Черная гиппомонада
вышла из бездны времен
и говорит, что не надо
ей ни гербов, ни знамен.

Черная гиппомонада
вышла из дали веков
и говорит, что не надо
ей ни вождей, ни полков.

Черная гиппомонада
вышла из чащи лесов
и говорит, что не надо
ей большинства голосов.

Черная гиппомонада
вышла на берег одна.
Ей не нужна канонада,
ей ненавистна война.

Черная гиппомонада
бодро бежит без подков,
и ничего ей не надо,
кроме жиров и белков.
a mitrio.
Tags:
fregimus: (bugsy)
«…монада — моноидальный объект в категории эндофункторов: return — единица, а join — умножение. Проще этого и объяснить нельзя! Если это кажется запутанным, посмотрите на монаду как слабый функтор из терминальной бикатегории…»
fregimus: (Default)
Интересный вопрос, на который я не смог ответить, обсуждая одну задачу (задание 1. 19 из sicp) с учеником. Пресловутый «детский вопрос». Впрочем, начнем по порядку.

Много формул про числа Фибоначчи… )

А вот и детский вопрос, поставивший меня в тупик: как именно добрый волшебник Хэл Абельсон пришел именно к такой форме функции ψ? Признаюсь, я с размаху сел в лужу. Давайте меня коллективно из нее доставать. Как определить, что для данного рекуррентного отношения существует самоподобное решение для перепрыгивания через 2 или несколько шагов? И, конструктивно, — как его отыскать?

___________________________
LaTeX to image conversion
CodeCogs - An Open Source Scientific Library
Tags:
fregimus: (Default)
Про Пуанкаре говорят, что он был последним человеком, знавшим всю современную ему математику. Второго Пуанкаре так и не появилось, и вышло так, что знать всю математику стало просто некому. Чтобы не очень сильно из-за этого огорчаться, люди стали говорить, что математика сделалась будто бы столь обширна, что одному человеку ее познать не под силу. А потом постепенно и сами в это поверили.

Через сколько-то лет так же будут говорить о людях, знавших всю тригонометрию.
Tags:
fregimus: (Default)
Расскажите мне, пожалуйста, представляете ли вы себе отрезок или окружность состоящими из точек? Можно ли окружность «разобрать» на составляющие ее точки? Если да, то как так можно из не имеющих размера точек составить имеющую размер линию? Как это укладывается в голове?

Аристотель полагал такую возможность абсурдной.

Интересно мнение и математиков, и естественников, и гуманитариев. Я знаю, что математики сейчас вспомнят Лебегову меру, и все сделается интуитивно просто и естественно. Но совсем недавно, до самого конца в XIX в., даже слов таких еще не было. Как бы без них, а обычной, не математической интуицией обойтись?

Прямую линию в геометрии не определяют, но окружность имеет определение.

Окружность есть множество точек, равноудаленных от данной.

Здесь используется операционное понятие множества. Хотелось бы без него. Попробуем так:

Окружность есть геометрическое место (locus, τόπος) точек, равноудаленных от данной.

Геометрическое место определяется предикативно, не через собирание всех входящих в него точек, а через описание свойства любой из них (не все точки, равноудаленные от данной, образуют собою окружность, но любая точка, принадлежащая окружности, равноудалена от данной). Но это определение, хотя и приводится в классических учебниках, но, на мой взгляд, хромает: две окружности одного радиуса не обязательно одинаковы, даже если их границы являются плотными множествами точек. Как бы еще это разрулить? Плотная, но не непрерывная линия — тоже не очень интуитивное понятие. Аристотель бы не одобрил.

Евклид: Κύκλος ἐστὶ σχῆμα ἐπίπεδον ὑπὸ μιᾶς γραμμῆς περιεχόμενον [ἣ καλεῖται περιφέρεια], πρὸς ἣν ἀφ᾽ ἑνὸς σημείου τῶν ἐντὸς τοῦ σχήματος κειμένων πᾶσαι αἱ προσπίπτουσαι εὐθεῖαι [πρὸς τὴν τοῦ κύκλου περιφέρειαν] ἴσαι ἀλλήλαις εἰσίν (1, 15). Σχῆμα ἐστι τὸ ὑπό τινος ἤ τινων ὅρων περιεχόμενον (1, 14). Ὅρος ἐστίν, ὅ τινός ἐστι πέρας (1, 13).

То есть, круг есть плоская фигура, ограниченная одной линией, обладающая тем свойством, что одинакова длина всех/каждой (πᾶσαι) прямой, падающей на нее из одной точки внутри фигуры. Фигура (σχῆμα) — это то, что содержится внутри границы или границ, а граница (ὅρος) — край/предел (πέρας) чего угодно. Иными словами, у Евклида — геометрическое место, а не множество.

Не представляю себе, насколько современному человеку естественно понятие множества точек, составляющих линию. Для меня, испорченного математикой, оно естественно вполне. Для Аристотеля это было нелепостью. Евклид аккуратно обходит острые углы.
Tags:
fregimus: (Default)
Карточный фокус, о котором я писал на прошлой неделе, исполни́м. На первый взгляд кажется, будто передаваемые карты не содержат достаточного количества информации. На самом деле, 4 карты можно передать в разном порядке 4!=24 способами, а пятая карта может быть одной из 52−4=48. И это действительно так: передать 4 случайные карты, чтобы однозначно указать на пятую, тоже случайную, нельзя.

Однако, можно сделать так, чтобы передаваемые карты содержали больше информации, если помнить о том, что помощник выбирает карты не случайно, а отбирает 4 карты из 5. Упомяну о трех различных вариантах решения задачи... )
Tags:
fregimus: (Default)
Я даю вам обычную стандартную колоду из 52 карт. Вы выбираете из нее 5 карт любым способом и отдаете моему помощнику. Помощник передает мне по очереди 4 карты, я называю их вслух, а затем… называю и пятую!

Как это у меня так получается?

Доб. Если ответ вдруг найдется в гуголе, не говорите вслух. Эту задачку можно решить, не подглядывая!

Доб 2. Хорошо бы еще система кодирования была практичной, чтобы помощнику и мне не надо было помнить громоздких таблиц или считать факториалы. Этот фокус действительно можно показывать после небольшой тренировки.
Tags:
fregimus: (Default)
Только что добавил трансляцию блога popmath.ru в ЖЖ как [livejournal.com profile] popmath. Подписывайтесь, читайте.
Tags:
fregimus: (Default)
[livejournal.com profile] old_surehand предлагает найти легкую монету среди 8 двумя взвешиваниями. Это нам слишком просто. Одну легкую монету среди 9 можно найти тем же способом. А вот как насчет 10? Если можно — то как, если нельзя — надо доказать.
Tags:
fregimus: (Default)

RP Feynman. Simulating Physics with Computers. International Journal of Theoretical Physics, v. 21, Nos. 6/7, 1982. pp 467—488. Стенограмма лекции на 1-й конференции по вычислителной физике, MIT, 1981 г.

Замечательная статья с объяснениями того, почему для квантово-механических вычислений требуются квантовые компьютеры. Отличное объяснение парадокса Эйнштейна-Подольского-Розена и теоремы Белла. Фейнман великолепно объясняет сложные вещи; лекция очень понятна.

Говорили, будто, мол, Фейнман доказал, что физика невычислима на обычных логических компьютерах — это неверно; он показывает только, что эти вычисления требуют экспоненциального времени и квадратичной памяти:

Хочу ввести такое ограничение, чтобы число элементов вычислительной машины, необходимых для моделирования физической системы, было прямо пропорционально объему пространства-времени системы. Мне не нужно экспоненциальное расширение [объема вычислений]… Если удвоение [объема] пространства-времени означает, что мне требуется экспоненциально больший вычислитель, то это против правил (я устанавливаю правила, так что мне — можно).

Выдеру цитату об истолковании квантовой механики:

Должен здесь сразу заметить, что там, куда мы направляемся [в объяснение парадокса ЭПР], у нас всегда были проблемы — секрет, секрет, закройте дверь! — у нас всегда были проблемы с пониманием картины мира, описываемой квантовой механикой. У меня, во всяком случае, потому что я уже слишком стар [Фейнману 63 года], чтобы говорить, что это все для меня очевидно. Да, меня это состояние дел беспокоит. Поэтому, некоторые из молодых студентов… знаете, как это всегда бывает: каждая новая идея, ей требуется поколение-другое, чтобы всем стало очевидно, что там нет настоящей проблемы. А мне еще не ясно, что там нет настоящей проблемы. Я не могу определенно сказать, что это за проблема, я подозреваю, что там нет никакой проблемы, но до конца я не уверен.

К вычислимости нашей сознания особого отношения не имеет, но введение в тему очень хорошее.

Tags:
fregimus: (Default)
Дж. В. Харт. Как разрезать бублик на две равные сцепленные половинки.



Рецепт... )

Задача. Найти отношение площади разреза к площади сечения того же бублика плоскостью z=0 (иными словами, насколько большую площадь придется вымазать сыром, если намазывается только рассеченная хлебная поверхность, а корка не намазывается).

Доб. Очевидно, можно разрезать 2-крендель (то есть крендель в форме 2-тора), чтобы части остались сцепленными через одно ушко. А можно ли его разрезать так, чтобы половинки были сцеплены дважды?

Доб. http://l-i-d-y-a.livejournal.com/151310.html
Tags:
fregimus: (Default)
[livejournal.com profile] fregima сегодня все-таки решилась обзавестись ЖЖ, а подвигло ее на это внезапно ею наблюденное родство треугольников Паскаля и Серпинского. А я что-то тоже растерялся и не знаю, почему так выходит. Биномиальные коэффициенты задают клеточные правила (чет + нечет = нечет; белое черное => черное), но почему из них получается треугольник Серпинского?

Если только удобно, комментируйте у нее в журнале, чтобы все комментарии вместе собрались, а не разбредались по двум журналам.
Tags:
fregimus: (Default)
Что-то у меня на работе завал дел, так что и написать для журнала не успеваю. Давайте я лучше пока картинки покажу. Вот такую фрактальную жирафку:



И еще расскажу немного о фрактальной еде! )
Tags:
fregimus: (Default)
Чувак в «Хьюлит-Паккарде» работает, как бы не должен быть уж совсем уж фриком. Зовут Бинай Деолаликар (Vinay Deolalikar) — имя мне ни о чем не говорит. Утверждает, будто доказал P ≠ NP. Черновик (120 стр.) разослан коллегам, в журнал еще не отправлен.

Абстракт я читал, глядя как корчеватель на новые ворота — ничё не понял. Дальше, понятно, не совался. Скажите мне что-нибудь умное, а?

Доб. Небольшой начальный разбор в веб-журнале Ричарда Липтона.

Доб. http://kolokolca.livejournal.com/67206.html

Доб.Последняя запись Липтона вносит больше ясности:
I think there are several levels to the basic question “Is the proof correct?”:

1. Does Deolalikar’s proof, after only minor changes, give a proof that P ≠ NP?

2. Does Deolalikar’s proof, after major changes, give a proof that P ≠ NP?

3. Does the general proof strategy of Deolalikar (exploiting independence properties in random {k}-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?

After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No”, [...] and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are added.” But I think the question #3 is still not completely resolved, and still worth pursuing…
Tags:
fregimus: (Default)
Нечаянно прочитал одну кислую книгу, которую немедленно пришлось закусывать чем-то сладким. Сладкое — вот:

Б. Л. ван дер Варден. Пробуждающаяся наука. Математика Древнего Египта, Вавилонии и Греции. М., 1959. Пер. с голл. И. Н. Веселовского по изданию: Waerden, B. L. van der. (1950): Ontwakende wetenschap, Egyptische, Babylonische en Griekse wiskunde.

http://www.onlinedisk.ru/file/492170/ (9 МБ, djvu)

Замечательный обзор древней математики, выполненный несомненным профессионалом как в математике, так и в истории.

Кое-что о Пифагоре... )
fregimus: (Default)
Этот парадокс приписывают Р. Смаллиану.

Теорема. В любой компании (компанией будем называть множество из одного или большего числа людей, наделенных шевелюрами) найдется такой человек, что, если он рыжий, то и все в компании рыжие.

Доказательство. В компании либо все рыжие, либо не все рыжие. Рассмотрим компанию из одних рыжих, и докажем индукцией, что для такой компании это верно. Для компании из одного это верно: если один рыжий, то и все в компании (из одного) рыжие. Теперь возьмем компанию из нескольких рыжих, и предположим, что в ней такой человек есть. Теперь добавим к ней еще одного рыжего. Этот предполагаемый человек, само собой, остался рыжим, и все в компании тоже по-прежнему рыжие. Таким образом, мы заключаем, что в компании из одних рыжих такой человек найдется.

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

Поскольку утверждение верно для двух исчерпывающих частных случаев (компании из одних рыжих и смешанной компании), то оно верно для любой компании.∎

Ваш ход. Кто догадался, говорите, только тихо, а кто гуголит, того Баба Яга съест.

_____________________________
1. «если А, то Б» можно эквивалентно записать в виде «если не Б, то не А». Например, утверждения «если идет дождь, я беру зонтик» и «если я не взял зонтик, значит, дождя нет» эквивалентны.
Tags:
fregimus: (Default)
Все видели фракталы, вычисленные на компьютере. А как насчет природных фракталов, которые можно увидеть и сфотографировать? Все, наверное, знают, что естественные береговые линии проявляют самоподобие на большом интервале масштабов карт. Смешивание подкрашенных жидкостей также порождает, при определенных условиях, видимые фрактальные структуры. Еще один пример «видимого» фрактала, и, пожалуй, один из «самых фрактальных», почти случайно обнаружил физик — исследователь хаотических процессов Дэвид Суит из университета Мериленда1. В 1999 году он заказал для украшения своего садика четыре зеркальных шара размером чуть меньше волейбольного мяча каждый. Может быть, случайно, а может быть, поняв, какой оптический инструмент неожиданно оказался у него в руках, он сложил их пирамидкой… и сделал потрясающие фотографии, попавшие на обложки «Нейчер» и «Сайентифик америкен»[см].


Впрочем, начнем с начала. Бильярд... )
Tags:
fregimus: (Default)
http://fregimus.livejournal.com/100995.html?thread=2364547#t2364547

[livejournal.com profile] yarikas wrote:
Математика, как и любой язык, - инструмент. Его предназначенье - решать задачи.
Так вот "эффективность" преподавания определяется именно в отношении умения учениками потом решать задачи с его помощью…
Вы написали коммент, я ответил - это ведь не вопрос веры? Компьютеры, электричество, оптоволоконные каналы - не плод воображения? Как не вопрос - отправка чел-ка в космос - сделали раз, а потом "повторить".
Такие вот повторы и помогут "заговорить" :/

Rainaldo Anonimato [isopenid.ru]:
Гм... С написанным в первом абзаце - нет смысла не согласиться (хотя это "определение" не полно, но вполне конструктивно:)).

Ну, так тем более - совершенно невозможным становится "приписать математике" - что-либо из упомянутого в абзаце втором. Да - один из множества "инструментов", не более, причём - далеко не из самых важных. Ведь ключевыми - являются инструменты, специфические к решению конкретной задачи, которые именно для неё надо создать и развить. А с развитием математики - это всё практически не коррелирует.
Математика - может всё в том же виде существовать хоть за сотни лет до "отправки в космос" (которая сама по себе - к чистым сферам науки уже не относится, но может тоже стать "инструментом") - никакую в отдельности математику к указанной "отправке" не приравняешь, и уж тем более - отправку в качестве "инструмента" математикой не заменишь.

Нужна ли нам математика? - кто же спорит? - конечно. Только при этом её надо (как той "Тени" у Андерсона и Шварца) - "знать своё место", очень узкое и служебное. А она порой пытается собою - что бы то ни было не "обслужить", а подменить. Это не хорошо. Это (пользуясь подхваченной Вами метафорой) - как если бы "литература" (и прочие свойства языка в широком смысле) - вместо описательных функций попытались бы - вытеснить для человека реальность (то, что так отчасти - и даже для большинства - происходит, не является оправданием:)). Да - придуманное и описанное в книжке - тоже может затем "оправдаться", - но это опять же не порождение и не заслуга языка (хотя язык подходящего качества для этого требуется).



Так для чего нужна математика?
Tags:
fregimus: (Default)
Мне не раз приходилось слышать, будто моделирование биологических процессов клеточными автоматами не более чем игра в бирюльки. К сожалению, мощный инструмент в неумелых руках может наделать много бед, но, конечно, это не говорит о том, что плох сам инструмент. Мне хочется показать на примере, как строится хорошая, достоверная биологическая вычислительная модель.

Много букв и кин, а формул совсем нет. )

И вот еще очень красивый короткий фильм, где показывается, в том числе, и образование плодовых тел слизевика:


____________________________________
1. S. Camazine et al. Self-Organization in Biological Systems. Princeton Univ. Press, 2001. Ch. 8.
Tags:
fregimus: (Default)
Вопрос тем, кто не читает веб-журнал И. Весеннего «Привычка не думать» (трансляция в ЖЖ [livejournal.com profile] rss_my_tribune): за что ж вы себя так не любите?

А мы сегодня построим полярную кривую каннабиноиду. Недавно она промелькнула где-то в ссылках, но без объяснений (спасибо за наводку [livejournal.com profile] olgapavlova). А мы разберем, как эта кривая устроена, да еще и свою, покрасивее сделаем!

Пять промежуточных шагов… )

Теперь добавим тем же способом зубчики на краях «листьев». Можно поэкспериментировать с разными порядками кривых и константы c; самый красивый результат у меня получился вот какой:

PolarPlot[(1 + Sin[9 x]) (1 + Sin[x]) (1 + 0.03 Sin[9*5 x]) (1 + 0.04 Sin[9*33 x]), {x, 0, 2 Pi}]



Конечно, это всего лишь математическая шутка, но она заставляет задуматься и над серьезным вопросом: имеет ли отношение эта кривая к настоящей форме листа конопли? Если и так, то отношение это очень и очень отдаленное. Формирование листа — очень сложный процесс, где превалируют локальные клеточных явления; иными словами, делящаяся клетка, само собой, не действует в зависимости от своих глобальных координат θ и r, а «знает» состояние только соседних клеток. Так что если мы и найдем подобную функцию в природе, то ее появление будет не причиной, а результатом иного процесса. Какого же? Вспомним, что центральная часть хаотического множества Мандельброта имеет форму приблизительно кардиоиды. На определенных масштабах хаотических процессов появляется порядок, и иногда этот порядок бывает достаточно прост, чтобы приближенно описываться аналитическими функциями. В таком рассмотрении, кардиоидальная форма листа конопли не случайна, и может быть ключом к описанию характера локальных процессов деления клеток в растущем листе. Но это рассуждение стоит целой заметки, и мы обязательно рассмотрим одну очень интересную вычислительную биологическую модель в следующий раз.
Tags:
fregimus: (Default)
Очень многие «находки» шаблонов нейронной активности, будто бы обнаруженных исследованиями методом ФМРТ, на самом деле не имеют правильного обоснования. Кажется, что ФМРТ уже стала френологией XXI века, настолько низок процент интересных работ, теряющихся в потоке явной нелепости. Удивительно, но такое впечатление, что статистика, методологически, для экспериментаторов является чем-то вроде бытовой магии: формулы применяются без понимания того, что в них можно подставить, так что несуразности результата не удивляют отнюдь. Э. Вул и Н. Кэнвишер описывают, с примерами из настоящих, сравнительно недавних статей, как нельзя применять статистику при анализе результатов ФМРТ[1]. Вводное рассуждение уж очень мне понравилось, хочу его пересказать.

Представьте, что перед вами колода из 52 перетасованных карт. Вы достаете одну карту — десятка бубен. Случилось событие с вероятностью 1/52.

Примечательно.

Открываете следующую карту — восьмерка пик. Вероятность появления восьмерки пик вслед за десяткой бубен равна 1/52 × 1/51 = 1/2652.

Невероятно.

Дальше идут валет червей, туз треф… Вероятность того, что карты оказались именно в таком порядке, равна 1/52! ≈ 1,2×10−68. И это событие с вами все-таки случилось.

Потрясающе!

Вывод о том, что событие с подобной вероятностью все-таки приключилось, несомненно, абсурден. Тем не менее, подобные рассуждения вы встретите сплошь и рядом. На этом основании рассуждают, например, что вероятность возникновения жизни на Земле настолько мала, что без «разумного дизайна» дело ну просто никак не могло обойтись…

И, в качестве легкой задачки: а в чем ошибка-то?

_____________________________
1. Edward Vul, Nancy Kanwisher. Begging the Question: The Non-Independence Error in fMRI Data Analysis (in press)
Tags:
fregimus: (bed)
Нет ничего проще, чем представить себе тринадцатимерный гиперкуб: представьте сперва N-мерный гиперкуб, а потом положите N=13.

Эта бородатая шутка мне вспомнилась только что, когда я наткнулся на фразу в одной статье: «легче всего визуально представить себе область значений функции σ как k-мерное полугиперпространство». Ну, легче, так легче. А я уж было пятимерную дырку от бублика начал себе живо воображать. Это гораздо труднее.

Не читать, не читать статей в ночь с субботы на воскресенье! Надо себя заставлять.
fregimus: (Default)
1  2  3  4  5  6   7 

XIV. Мышление математика

Рассмотрим теперь второй вопрос, в рассуждениях о котором часто упоминают ТГ, и где это упоминание часто кажется, хотя бы на первый взгляд, уместным. Речь идет об отношении математики и сознания работающего человека-математика. Встречается такая точка зрения, что математическому уму некоторые математические факты доступны как истинные непосредственно, минуя доказательство — в виде интуитивных «откровений». В числе аргументов за эту точку зрения часто выдвигают как теоремы Геделя о неполноте, так и невычислимость в смысле Черча-Тьюринга. Среди них часто повторяются аргументы Дж. Лукаса и Р. Пенроуза. Подробный анализ этих рассуждений имеется в книге [3], главы 2 и 6; здесь мы рассмотрим два примера.

Рассуждение Лукаса... )
Tags:
fregimus: (Default)
1  2  3  4  5   6   7

XIII. Искусственный интеллект

Искусственный интеллект — понятие чрезвычайно широкое. Когнитивную науку, как и многие другие, по решаемым задачам можно условно разделить на фундаментальную и прикладную. Задача фундаментальной науки — теоретическое описание природы, прикладной — применение моделей, взятых у фундаментальной, к решению технологических задач. Под искусственным интеллектом понимается чаще всего прикладной аспект когнитивных исследований, позволяющий техническими средствами решать задачи, которые не решаются простыми механическими методами.

Весьма часто приходится видеть «убежденных противников» ИИ... )
Tags:
fregimus: (Default)
Открываю комментарии с вашими ответами к задаче. Спасибо всем, кто откликнулся на мою просьбу: пришло почти 100 ответов! Задача совершенно несложна, но чрезвычайно интересна тем, что решают ее существенно разными путями. Мне известны три способа такого решения. Все три представлены в ответах, а четвертого, к сожалению, не появилось. Три этих пути таковы.

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

Второе решение графическое. Рисуются графики высоты монаха в зависимости от времени дня. Поскольку и подъем, и спуск происходили в течение светового дня, то один график будет спускаться от полной высоты горы до уровня подножия, а другой, наоборот, будет подниматься от последнего к первому в том же интервале времени на оси абсцисс. График следует без разрывов (монах не телепортируется), следовательно, графики непременно пересекутся.

Третий путь еще более абстрактный. Пусть f(t) высота монаха в день подъема, а g(t) высота в день спуска. Определим d(t)=f(t)−g(t) — это будет разница высот положения монаха во время дня t. Утром d(tу)<0, так как поднимающийся монах был у подножия, а спускающийся на вершине. Вечером знак d(tв) поменялся. Поскольку обе функции f(t) и g(t) всюду дифференцируемы, то этим свойством обладает и d(t), следовательно, согласно теореме Больцано-Коши, она принимает все промежуточные значения на интервале от tу до tв. В интервал промежуточных значений входит и 0, следовательно, есть такая точка, в которой d(t)=0, а, значит, и f(t)=g(t).

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

Пока забудем о существовании второго и третьего решений и попытаемся «точно доказать» ответ с помощью математики. Пусть мы построили какую-то модель, из функций, графиков, тензоров или квартернионов — неважно. Пусть в нашей модели мы не смогли доказать, что точка встречи есть. О чем это говорит? Лишь о том, что мы построили неверную модель: мы же знаем уже, что монахи встретятся. Если же мы доказали, что точка встречи есть, то мы получили лишь тавтологическое подтверждение понятого нами факта. Можно сказать, что мы лишь не опровергли правильности модели.

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

Таким образом, здесь очень легко угодить в логическую ловушку «математизирования модели». Любая модель, какую бы мы здесь ни построили, окажется лишь описанием той самой встречи монаха на спуске с его фантомом из времени его подъема — она ничего не добавит и не прибавит, а полученное из нее доказательство будет лишь доказательством ее собственной правильности.

Интересно, что я решил ее третьим способом, и лишь позже, к ужасу и потрясению своему, догадался о первом. Не буду здесь доводить дело до крайности и соглашаться с г. Фурсенко о том, что математика портит мышление, но замечу, что, возможно, я здесь оказался рабом дурной умственной привычки сначала безыскусно превращать все в функции, а потом уже начинать ими оперировать. Намного интереснее все-таки сначала охватить умом суть задачи, а заученные математические приемы привлекать только тогда уже, когда они очевидно «просятся» в решение. Берегите голову.
Tags:
fregimus: (Default)
Есть такая задачка (Koestler 1964), которую разные люди решают по-разному. Если не трудно, отпишите, каким путем вы шли. Если даже не дошли до решения, все равно скажите, каким, как вы думаете, методом ее надо решать. Комментарии мне придется скрыть, но через несколько дней я обязательно их открою. Задача формулируется так:

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

Для зануд поясняю условие. Как хорошо известно, солнце восходит и заходит каждый день в одно и то же время. Вернее даже, не восходит и не заходит: его включают и выключают. Буддийские монахи ходят на гору по рельсам, никуда не сворачивая.

Внимание: комментарии открыты и больше не скрываются. Разговор о решениях здесь.
Tags:
fregimus: (Default)
[livejournal.com profile] falcao пишет о Геделевой теореме о полноте (обсуждать здесь). Мне было интересно коснуться логики и полноты формальных систем только в прикладном (к вопросам о сознании) аспекте; falcao же — математик-теоретик и наиопытнейший преподаватель, и, несомненно, его математическое изложение будет одновременно и глубже, и проще для понимания, чем мое.
Tags:
fregimus: (Default)
1  2  3  4   5   6  7

XII. O чем не говорят теоремы Геделя

Когда мы имеем дело с математическими объектами и утверждениями о них, важно помнить, что в теоремах математики нет ни одного лишнего слова. Давайте вернемся к формулировке теорем Геделя и рассмотрим их внимательно.

Первая ТГ: Фундаментальная система теорем, выводимых формальной системой, не может быть одновременно полной и непротиворечивой.

Вторая ТГ: Если фундаментальная система теорем, выводимых формальной системой, содержит доказательство собственной непротиворечивости, то она противоречива.

Слово фундаментальная здесь, напомню, говорит о том, что интерпретация, выражает элементарную арифметику: натуральные числа, сложение и обязательно умножение, а также элементы логики, чтобы можно было об этих числах и выражениях что-то утверждать. Итак, обе теоремы Геделя ограничивает полноту и непротиворечивость только ФСС, говорящих об арифметике. Две этих теоремы совокупно называют теоремами о неполноте арифметики (ТГНП) — именно, обратите внимание, арифметики.

Это ограничение чрезвычайно существенно, хотя о нем и забывают те, кто применяет теорему Геделя ко всему подряд. Хороший пример такого нелепого высказывания есть в [3]: «Поскольку Библия учит всему, она полна. Следовательно, по ТГНП, Библия противоречива». Это рассуждение было бы верным, если бы условие фундаментальности было соблюдено — но Библия не является формальной теорией, утверждающей о сложении и умножении натуральных чисел, и не содержит аксиом или правил вывода теорем! Здесь применено слишком емкое понятие «все». Математики говорят обо «всем» в некоторой области. Арифметика говорит «все», но только о натуральных числах. То «все», о котором говорит Библия, есть такое же ограниченное «все». Для кого-то она может быть и учебником жизни на каждый день, но ежедневная жизнь все же чрезвычайно удалена от строгих идеальных пространств арифметики.

Интересно, что даже теория действительных чисел не попадает под понятие фундаментальной арифметики, хотя натуральные числа и являются подмножеством действительных. В теории действительных чисел нельзя говорить о натуральных — внутри теории они никак не выделяются, «ничем не отличаются» от других, нецелых чисел. Поэтому даже такой «близкой» теоретической системе, как действительная математика, теорема Геделя не запрещает быть одновременно полной и непротиворечивой. Она и в самом деле одновременно и полна, и непротиворечива.

Геометрия не «подчиняется» ТГНП по той же причине: геометрию можно отобразить на некое подмножество действительной теории, но в геометрии нельзя работать с целыми числами отдельно от прочих. Геометрия тоже может быть и полной, и непротиворечивой.

Арифметика Пресбургера — самая обычная арифметика, только лишенная понятия об умножении — тоже недостаточно сильна, чтобы удовлетворять требованиям ТГНП. Она в точности совпадает с обычной арифметикой, но только не делает ни понятия умножения, ни одного утверждения о нем. Доказано, что она полна и непротиворечива — но это не противоречит выводам Геделя, потому что и эта система не является фундаментальной арифметикой.

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

Рассмотрим такой пример (Кирьянов Д. Исповедание великого логика. Интервью журналу Нескучный сад, сентябрь 2009):
Гедель исследовал арифметику и показал в своих теоремах, что ее непротиворечивость не может быть доказана, исходя из ее самоочевидных принципов: аксиом сложения, вычитания, деления, умножения и проч. Нам требуются для ее обоснования некоторые дополнительные допущения. Это на самой простейшей теории, а что говорить о более сложных (уравнениях физики и т. п.)!
Первое утверждение следует понимать как верное, хотя и построено оно, скажем, чрезмерно популярно; никаких аксиом вычитания или деления в арифметике нет. А вот о более «сложных» теориях ТГНП как раз не утверждают ничего! Уравнения физики, в частности, опираются не на арифметику, а на вещественные и комплексные числа, к основополагающим теориям которых ТГНП неприменимы в принципе. Более того, еще важнее осознавать здесь, что физика отнюдь не выводится из аксиом — физические формулы появляются из математического аппарата теорий, описывающих наблюдаемую реальность.

Бывает, что ТГНП приписываются утверждения, и вовсе ей противоречащие. Рассмотрим теперь такое утверждение:
теорема Гёделя… показыва[ет], что негуманитарий… не способен осознать всех аксиом своего мышления.
Если понимать здесь «негуманитария» как некую вычислительную систему, то утверждение это будет о том, что формально-теоретическая система будто бы не может сформулировать своих собственных аксиом. Это неверно не только для арифметически фундаментальной системы — это неверно для любой ФС! Например, в интерпретации системы ХИХИ, строка ХИ, верная по положению, является аксиомой. Система ХИХИ «произносит», или, в терминах этого утверждения «осознает» строку ХИ. Впрочем, об «осознании» системой себя, точнее, о выводе ею утверждений о себе самой, мы еще поговорим.

Эту же ошибку мы видим и в следующей цитате (Бойко В. С. Йога. Искусство коммуникации, 2-е испр.):
В контексте данной работы теоремы Гёделя показыва[ю]т, что любую жизненную ситуацию человек принципиально не способен понять, находясь в ней.
Ни о каких «человеках» ТГНП не говорят, речь идет только лишь о формально-теоретических построениях. В отличие от человека, формальные системы в принципе не способны попадать в ситуации: все, что происходит в ФС, происходит внутри нее. Это верно в контексте любой работы, а не только цитируемой.

Тут можно было бы остановиться, ибо ничего более о применимости ТГНП мы здесь добавить не сможем, но позволю себе проговорить небольшое отвлечение, которое нам важно будет в дальнейшем. Математика, будучи дисциплиной глубоко формальной, позволяет нам отринуть любые понятия о затратах времени, энергии, денег и прочих ограниченных ресурсов на вычисления. Мы формулируем правила вывода таким образом: если мы вывели строку X, то мы выведем из нее и строку Y, и все это мы производим вневременным образом, ни мало не считаясь с тем, что рост числа выведенных строк будет экспоненциальным, что их число превысит возможности любого компьютера, попытайся мы проделать этот сугубо мысленный процесс на реальной вычислительной машине. Условие, которое мы ставим, мысленно направляя процесс порождения теорем в теории, касается только бесконечности: мы не можем дать нашему воображаемому вычислителю задание «перенумеровать все числа, а затем…» — по правилам игры, мы можем запустить его в такое бесконечное путешествие лишь однажды, — но и это ограничение лишь правило математической игры, а вовсе не исходит из трудностей реального мира.

Человек поставлен в ситуацию непрерывного взаимодействия со средой, поэтому никакая «внутренняя» формальная система не опишет поведения человека полностью. Здесь мы возвращаемся к тысячу раз прожеванному, но так многими и не впитанному вопросу о проведении границ. В любой человеческой ситуации всегда оказывается задействована вся вселенная; что нам отсечь, назвать неважным, а что оставить внутри — всегда вопрос произвола исследователя, его опыта, интуиции; если сделать это сразу неверно, то все теоретизирование, скорее всего, пойдет насмарку. Но, в любом случае, граница, по которой мы отсекаем «жизненную ситуацию человека», должна проходить намного дальше его мозговых оболочек.

Букалов А.В. Мышление и квантовая физика: теоремы Геделя, Тарского и принцип неопределенности. Физика сознания и жизни, космология и астрофизика, 2, 2001:
[1-я ТГ] утверждает принципиальную невыразимость или невозможность вербализации (т.е. ненаблюдаемость) математических объектов (или объектов математического, да и любого другого, мышления). Любопытно отметить, что Гедель при доказательстве своей теоремы исходил из парадокса лжеца (некто говорит: «Я лгу»...).
Первое утверждение говорит о том, будто бы арифметика вообще не содержит ни одного утверждения о числах. Это, конечно же, нелепость — каждый, изучавший в школе арифметику, думаю, приведет одно-другое арифметическое утверждение, чем и опровергнет смелый софизм д-ра Букалова. Спорить с эквивалентностью вербализации и наблюдаемости, пожалуй, выходит за рамки нашего разговора. Любопытно, однако, отметить, что Гедель при доказательстве своих теорем из «парадокса лжеца», как мы уже видели, не исходил. Более того, то, что Геделево утверждение G: G недоказуемо в теории T не может быть переформулировано как G': G' ложно, то есть что оно не эквивалентно парадоксу лжеца, как раз и говорит теорема Тарского, тоже склоняемая д-ром Букаловым на все лады.

Сокал, Брикмон (А. Сокал, Ж. Брикмон. Интелектуальные уловки. М. : Дом интеллектуальной книги, 2002) приводят такой невероятный пример постмодернистски-фривольного обращения с теоремами Геделя и с логикой вообще, цитируя дискурс социального философа Р. Дебрэ из его «Критики политического разума» (1981):
Открытие «секрета» коллективных бедствий, то есть условия a priori всякой прошедшей, настоящей и будущей политической истории, содержится в нескольких простых детских словах. Но если мы заметим, что определения прибавочного труда и бессознательного состоят из одной фразы (а в физических науках уравнение общей теории относительности состоит из трех букв), то мы остережемся смешивать простоту с упрощенчеством. Этот секрет имеет форму логического закона, обобщения теоремы Геделя: нет организованной системы без закрытия и никакая система не может быть закрытой при помощи только лишь её внутренних элементов.
Ну что ж, ежели такой закон является неким обобщением теоремы Геделя (речь идет о 2-й теореме, как я понимаю) — доказательство обобщения в студию, гг. философы! Ни о чем таком в ТГНП и близко речи не идет.

Как видно из этой небольшой подборки примеров, любое применение ТГНП в гуманитарных выкладках — почти наверняка ошибка. Нам, однако, следует рассмотреть два более глубоких случая применения арифметической полноты к сознанию. Логические ошибки в этих случаях далеко не так очевидны, как в приведенных выше.

1  2  3  4   5   6  7
Tags:
fregimus: (Default)
1  2  3   4   5  6  7

XI. Математические последствия

Хорошо или плохо для математики открытие Геделя? С одной стороны, надежды математиков на самообоснованность математики, на существование единственной верной математической системы, которую можно «открывать», но не «выдумывать», испарились. Можно подумать, что это плохо. С другой же стороны, оказалось, что математика не сводится к механической процедуре доказательств, что в математике всегда останется место для нового не автоматизированного творчества. Проще говоря — математика не заканчивается, как она бы завершилась с изобретением полностью механизированной математической системы. Математики без работы не останутся, и их, в отличие от рабочих на сборочном конвейере, не заменят роботы. И это как будто бы хорошо.

Диалектическую сущность открытия Геделя хорошо сформулировал К. Подниекс в [2]:

Всякая формальная теория с методологической точки зрения является моделью некоторой застывшей системы мышления. С учетом этого основной вывод из теоремы о неполноте можно переформулировать так: всякая достаточно всеобъемлющая, но застывшая система мышления неизбежно оказывается несовершенной — в ней содержатся либо противоречия, либо проблемы, для решения которых данной (застывшей!) системы недостаточно. Именно в строгом доказательстве принципиального несовершенства всякой застывшей системы мышления состоит подлинный диалектический смысл достижений Геделя.

Итак, с философской точки зрения, теорема Геделя радикально поменяла математические воззрения на основания математики.Математика не может быть одновременно полной и непротиворечивой. Противоречие — много худший дефект теории, чем неполнота: она сводит на нет всю доказательную силу теории. Поэтому математика, какой мы ее разрабатываем, не должна быть противоречивой. Если мы придем к противоречию, нам придется отступить на несколько шагов назад, чтобы изъять из системы те положения, аксиомы, которые к этому противоречию привели. Наша непротиворечивая математика всегда будет неполной. Но каковы же практические — то есть, важные для ежедневной математической работы — последствия этой неполноты?

По всей видимости, они невелики. В некоторых областях математики, наиболее абстрактных, например, теории категорий, они более ощутимы, и на них необходимо оглядываться; в других же геделевы утверждения являются сами по себе предметом математического поиска. Они достаточно редки, и их обнаружение само по себе является достижением. Например, относительно недавно было доказано, что теорема Гудстайна является геделевым утверждением арифметики, и не может быть в ней доказана. Гудстайн описывает особую манипуляцию над числами; утверждение его состоит в том, что, с какого бы числа мы ни начали, повторяя алгоритм конечное число раз, мы в конце концов получим в результате ноль. Хоть эти действия можно проделать в ЭА для наперед взятого числа, доказательство того, что так будет для любого, лежит за пределами ЭА.

Кроме того, в математике имеется определенное число подобных «наблюдательных» предположений. В некотором смысле, это сближает математику с естественными науками: мы делаем наблюдения над поведением математических объектов, затем строим гипотезы, пытаемся построить теории, подвести солидные доказательства под эти гипотезы — и это не всегда получается. С другой стороны, это подкрепляет, в определенном смысле, платонистический-пифагорейский подход к математике. Математика, какой мы ее придумали, существует и ведет себя как объект, поведения которого мы не понимаем до конца, и открываем его свойства — хоть это сложное поведение и задано простыми правилами, которые следуют из еще более простых, установленных произвольно.

Часто бывает, что математика отставляет недоказанность некоторых утверждений в сторону, и развивается, будто они были доказаны. Так же ведут себя и естественные науки. Все, что мы знаем в физике, так же «доказано» наблюдениями и сведением их в теории. В физике нет аксиом, есть только наблюдения. Математика, разумеется, предпочитает аксиомы, но в некоторых случаях и принимает — предварительно, в силу своей строгости — недоказанные утверждения, от которых можно отталкиваться и двигаться вперед.

В число таких недоказанных утверждений входят не только «курьезы» — интересные теоремы, из утверждений которых не делается никаких дальнейших выводов, к каким, например, относится Великая теорема Ферма, доказанная всего несколько лет назад. Существуют гораздо более «серьезные» теоремы, с помощью которых математики доказывают новые теоремы. В их число входит гипотеза Римана.

Гипотеза Римана говорит о значениях нулей комплексной дзета-функции Римана. Разъяснение этой гипотезы лежит далеко за пределами нашего повествования, но нам, безусловно, интересно, что происходит в математике вокруг нее. Доказательства этой гипотезы не найдено уже 150 лет. Говорят, будто, когда у Гильберта спросили, что он сделает, если заснет и проснется через 500 лет, он ответил, что первый вопрос, который он задаст, будет о том, была ли доказана гипотеза Римана. Дело в том, что гипотеза Римана используется во многих доказательствах, как если бы это была доказанная теорема. В этом ее отличие от теоремы Ферма, которая была и остается просто интересным фактом о числах, но не используется в доказательствах так широко. Институт Клэя назначил приз в 1 миллион долларов США за доказательство Римановой гипотезы, потому что ее доказательство чрезвычайно важно для арифметики, в частности, в области факторизации чисел на простые сомножители. Выходит, что и криптостойкость современных шифров зависит от верности предположения Римана, и, таким образом, она оказывает влияние на материальный мир через ежедневные компьютерные операции в нем.

Гипотеза эта доказана для некоторых частных случаев, и, кроме того, разумеется, производились масштабные компьютерные проверки ее истинности. Проверено огромное число (около 10 триллионов!) нулей дзета-функции, и все их значения соответствуют утверждению гипотезы. Общее же число этих нулей бесконечно велико, поэтому полная компьютерная их проверка невозможна. Требуется доказательство, но его нет.

Что будет с математикой, если выяснится, что гипотезу Римана нельзя доказать в существующих даже самых сильнх, самых внешних математических теориях? Конечно, можно сделать ее утверждение аксиомой, просто объявить, что, раз она недоказуема, то мы будем полагать ее истинной по положению. Но, кроме этого, возможен и другой путь. Мы могли бы объявить гипотезу ложной, и считать ее ложность аксиомой15. В принципе, это не вызвало бы в математике противоречий, но, тем не менее, такое положение шло бы вразрез с уже накопленным математическим знанием. Здесь опять проявляется некоторое сходство математики и естественных наук — сходство, возникающее от того, что думают над теориями в этих науках люди, пользуясь родственными мыслительными системами. Мы наблюдаем, что гипотеза Римана верна для огромного количества случаев, и предполагаем — очень уверенно предполагаем! — что она верна всегда в построенной нами системе математики. Поэтому, если нам случится полагать ее аксиомой, расширяющей эту систему, то естественным будет положить аксиомой ее утверждение, а не его отрицание.

Отвлечение наше на гипотезу Римана было не случайным. На этом примере будет интересно рассмотреть положения о том, что сознанию человека будто бы доступна «истина», не достижимая вычислительным алгоритмом.

1  2  3   4   5  6  7
__________________________________
15. Например, так: существует хотя бы один нетривиальный нуль дзета-функции, вещественная часть которого отлична от 1/2.
Tags:
fregimus: (Default)
1  2   3   4  5  6  7

VIII. Машина доказательств

ФСС элементарной арифметики (ФСЭА), как мы уже знаем, производит строки, интерпретируемые как утверждения арифметики. Она содержит аксиомы, начальные верные строки, и выводит новые строки — теоремы. Мы не будем рассматривать конкретные аксиомы8 и правила вывода новых строк из уже выведенных; нам достаточно помнить, что они заданы. В алфавит ФСЭА входят символы для кодирования чисел и переменных, операции + и ×, сравнение =, скобки, кванторы существования E и всеобщности A (мне придется обозначить их латинскими буквами из-за типографских ограничений), и логическое отрицание ~. Числа кодируются в такой же «единичной» системе, какую мы уже рассматривали, количеством «звездочек». Так же кодируются и переменные, только начинаются они со специального символа переменной x: вместо x, y, z, a, b система выдает x•, x••, x••• и т. д. В примерах ниже мы, однако, будем записывать числа в десятичной записи, а переменные буквами.

Примеры утверждений, которые выводит ФСЭА:

Ex:x×2=6

Здесь говорится, что число 6 четно (найдется такое число x, что 2×x=6)

~Ex:Ey:(x+1)×(y+1)=13

13 простое число: не существует таких x и y, что (x+1)×(y+1)=13. Прибавление единицы требуется, чтобы каждый сомножитель был больше 29.

Ax:Ea:~Eb:Ec:(x+a)=(b+1)×(c+1)

Здесь утверждается, что существует бесконечно много простых чисел. Следует читать это так: для любого x найдется a такое, что не существует таких b и c, чтобы равенство (x+a)=(b+1)×(c+1) выполнялось. Иными словами, для каждого x найдется такое a, что (x+a) будет простым числом. Поскольку a>0, то и x+a>x: какое число x ни возьми, найдется простое число, еще большее.

В образовании смысла строк мы следуем правилам, которые мы же сами установили для их интерпретации. Например, «~» мы читаем «неверно, что», A как «для всех», E как «для одного или более», «:» как «верно следующее:», и так далее. Тогда утверждения, выводимые ФСЭА, становятся теоремами. Являются ли они «истинными»? Здесь нужно задуматься о понятии истинности.

Мы изначально полагаем аксиомы истинными, верными утверждениями. Их запись в виде строк ФСЭА интерпретируется именно так, как мы того хотим, с тем смыслом, которые мы в них закладывали, когда придумывали эти строки10. Являются ли истинными в этом смысле и теоремы? Ровно настолько, насколько мы можем доверять формальному механизму вывода, аппарату формальных систем.

На поверхности кажется, что этот механизм работает надежно. Можно увидеть, как выводятся приведенные выше утверждения, которые мы понимаем как верные в арифметике. Но ведь теорем, которые производит ФСЭА, бесконечно много. Поэтому мы должны поставить вопрос «доверия» к нашей механике вывода. В ФСС сложения чисел доказательство было довольно простым, однако, ФСЭА намного сложнее, и ее «правильность» отнюдь не очевидна.

Вопросы касательно ФСЭА, которыми мы зададимся, следующие. Во-первых, нас интересует, все ли возможные теоремы арифметики выведет наша машина? Например, будет ли среди ее строк доказательство Великой теоремы Ферма? Предположения Гольдбаха? Свойство, которое нас интересует, мы назовем полнотой системы: система полна, если она выводит, в интерпретации смысла, все истинные утверждения в некоей области.

Второй, еще более важный вопрос, который нас волнует: не произойдет ли так, что два утверждения, полученных ФСЭА, будут противоречить одно другому? Например, одним путем мы получим утверждение, что предположение Гольдбаха истинно, а другим — что оно ложно. Такое нарушение будет фатальным для всей системы арифметики: из противоречия можно вывести все, что угодно! Это легко показывается в формальной логике. Из такого противоречия следует, что 0=1, что 2×2=5, что простых чисел не существует, что их существует конечное количество, что количество простых чисел бесконечно — все, что пожелаете. Противоречия в выведенных теоремах ни в коем случае быть не должно. Свойство системы не выдавать противоречивых (в интерпретации смысла) утверждений назовем непротиворечивостью.

Является ли элементарная арифметика полной и непротиворечивой теорией? Над этим вопросом работали великие математики начала XX в. Попытка вывести самообоснованность теории множеств тогда потерпела неудачу11. В ответ на это Давид Гильберт сформулировал в начале 20-х гг. программу по поиску способа вывода всех математических утверждений из аксиом путем механической вычислительной процедуры. Формулировка требований, заданных Гильбертом к аксиомам и процедурам математики, такова: требуется найти (а) процедуру, которая бы выводила все без исключения истинные математические утверждения, и только истинные, из заданного однажды набора аксиом; (б) самый набор этих аксиом и (в) алгоритм доказательства любого наперед заданного утверждения, чтобы определить за конечное время, возможно ли вывести это утверждение из аксиом (в таком случае, оно истинно) или нет (и тогда оно ложно).

Таким образом, Гильберт сформулировал задачу поиска, в наших терминах, полной и непротиворечивой формальной системы арифметики, и дополнил ее требованием конструктивной вычислимости 12принадлежности лексически верной строки множеству синтаксически верных строк.

Над реализацией этой программы математики работали еще 10 лет, до тех пор, пока Курт Гедель не обнаружил фундаментальное свойство формальных систем, которое предопределило неудачу программы Гильберта и невозможность аксиоматизации математики.

IX. Бета-код Геделя

Рассуждение Геделя основано на арифметическом кодировании алфавита, строк и правил ФС. В самом деле, мы можем закодировать алфавит ФС числами. Когда мы это сделаем, правила переписывания строк ФС можно записать в виде арифметических операций над числами. О любом числе можно задать вопрос, является ли это число кодом лексически верной строки в данной ФС. Если ответ на него положительный, далее можно спросить, является ли это число также и кодом синтаксически верной строки. Если да — то мы имеем дело, на семантическом уровне, с кодом теоремы арифметики. Таким образом, выходит, что среди чисел есть подмножество кодов теорем арифметики. Множество всех остальных чисел можно назвать множеством не-теорем арифметики (либо они лексически недопустимы, либо не выводимы системой). Будем называть числа вычислимыми формальной системой, если они выводимы нашей закодированной числами ФС.

Для примера, закодируем нашу первую систему ХИХИ в виде чисел: заменим Х на 1, И на 2, А на 313. Начальная верная строка ХИ тогда первращается в число 12. Теперь перепишем на языке чисел правила системы.

1. К любому числу, заканчивающемуся на 2, можно дописать в конец 3. Математически это можно выразить так: если n вычислимое число, и остаток от деления его на 10 равен 2, то 10×n+3 тоже вычислимое число.

2. Любую «подстроку», следующую за 1, можно «удвоить». Операции «взятия подстроки» и «удвоения», разумеется, следует записать арифметически. Пусть наше число содержит в середине или в начале 1 (пример 23132). Часть, заканчивающуюся 1 (231 в примере) запишем как m×10+1, где m≥0 (в нашем примере m=23). Чтобы приписать к этому числу «хвост» (32), умножим его на 10n, где n — длина «хвоста» (у нас n=2, 10n=102=100): (m×10+1)×10n, в нашем примере это будет 23100, а затем просто прибавим «хвост», то есть запишем формулу как (m×10+1)×10n+j, где j обозначает «хвост» (у нас j=32). Чтобы он поместился в отведенное ему разрядное место, мы должны ввести ограничение j<10n. «Удвоить хвост» можно, еще раз умножив результат на 10n и прибавив j. Таким образом, правило (2) можно сформулировать так:

Если (m×10+1)×10n+j, где j<10n, вычислимое число, то и (m×10+1)×10n+j)×10n+j вычислимое число.

Запись правил (3) и (4) в арифметической форме оставим как упражнение читателю.

Все это выглядит чрезвычайно запутанным и искусственным, но нас сейчас не интересует сложность и «неинтересность» этого вывода. Самое главное здесь, что путем формального, механического преобразования можно перейти от записи правил операций над строками к записи правил в виде операций над их кодами, числами. А как только мы переведем описание ФС на язык арифметики, мы сможем сформулировать и задачи, ставящие вопросы об этой ФС, на том же языке арифметики. Например, задача о выводимости ХА переформулируется в таком виде: входит ли число 13 во множество чисел, вычисляемых данной, описанной в виде арифметических действий, ФС?

X. Теоремы Геделя

Ничто не препятствует нам распространить рассуждения о кодах ФС на самое арифметику, вернее, ее формальную систему — ФСЭА. Переписав ее правила в виде арифметических алгоритмов, мы закодируем каждое утверждение, получаемое ФСЭА, натуральным числом.

Что интересного произойдет, когда мы сделаем это? ФСЭА достаточно мощна, чтобы порождать язык арифметики. В тоже самое время, мы переписали ее правила на тот же самый язык! Иными словами, в таком выражении ФСЭА формулирует утверждения о себе. Например, мы можем спросить, входит ли число X во множество чисел-кодов утверждений ФСЭА? Тем самым, мы задаем вопрос, является ли число Х кодом верного утверждения, то есть теоремы, арифметики. Понятно, что число мы можем теперь рассматривать двояко: как собственно число, и как код утверждения о числах.

Гедель доказывает, что возможно (и показывает, как) сконструировать в ФСЭА утверждение «Число G не входит во множество кодов теорем, выводимых ФСЭА», таким образом, чтобы код этого утверждения в точности совпал с самим числом G14. Каковы последствия существования такого числа?

Попробуем «спросить» арифметику об истинности этого утверждения. Верно ли на самом деле, что число G не входит во множество кодов теорем, выводимых ФСЭА?

Предположим, что ответом арифметики на этот вопрос будет «да». Это означает, что утверждение это выводимо в ФСЭА, а это в свою очередь, означает, что число G, его код, входит во множество кодов выводимых теорем… Но позвольте-ка, ведь если это так, то в арифметике оказывается противоречие: получается, что число G и входит во множество кодов теорем, и не входит в него — результат получается разным в зависимости от пути формального вывода, которым мы идем.

Предположим теперь, что число G, код утверждения о том, что G не является кодом теоремы, и на самом деле не является кодом теоремы. В таком случае, противоречие снимается. Однако, в этом случае арифметика оказывается неполной! У нас есть верное утверждение (о том, что G не является кодом теоремы), которое, хоть и верное, но не входит в число теорем арифметики. Получается тогда, что арифметика «не знает» всех верных утверждений о натуральных числах.

Это рассуждение и является основным в первой теореме Геделя о неполноте. Формулировка этой теоремы была в дальнейшем значительно усилена Россером; когда говорят о теореме Геделя, имеют в виду обычно первую теорему о неполноте арифметики в формулировке Россера.

Обратите внимание, что такое замыкание нашего рассуждения возможно не в любой ФС. Например, утверждения системы ХИХИ не являются таковыми о натуральных числах; строку системы ХИХИ нельзя интерпретировать как «x не входит во множество Z», ведь у нас нет отображения этих строк на утверждения о числах. Кроме того, она не описывает и системы кодирования утверждений на языке, который она производит. Таким образом, ФС, попадающая под обсуждение теоремы Геделя, должна быть достаточно мощна, чтобы выражать, в некоей интерпретации смысла, действия элементарной арифметики. Системы, для которых такая интерпретация в принципе возможна, мы, вслед за Подниексом [2] назовем фундаментальными.

Давайте теперь проговорим суть вывода теоремы Геделя-Россера:

Фундаментальная система теорем, выводимых формальной системой, не может быть одновременно полной и непротиворечивой.

Этот вывод остается верным применительно к любой фундаментальной системе (то есть, с различными наборами аксиом и правил), не только к конкретной ФСЭА. Например, вполне естественно включить G в число аксиом нашей системы. Раз уж мы знаем, что утверждение G истинно, давайте добавим его к списку аксиом нашей ФСЭА. К сожалению, это не снимает противоречия. Сделав это, мы получим другую формальную систему, ФСЭА′, в которой, по теореме Геделя, есть свое геделево число G′. Можно и его добавить к аксиомам ФСЭА′ — мы получим новую систему ФСЭА′′, но и в ней будет свое геделево число G′′ — и так далее до бесконечности.

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

Здесь можно увидеть некоторое сходство с геометрией. Изменяя пятый Евклидов постулат о том, что через заданную точку проходит ровно одна прямая, параллельная заданной прямой, мы получим разные непротиворечивые системы геометрии. Существенная разница в том, что геометрия, в отличие от арифметики, не порождает языка, на котором можно выразить аксиомы и правила геометрии. Тем не менее, общая картина арифметического состояния дел нам ясна: имеются некоторые истинные, в смысле более сложных, «внешних» теорий, утверждения, которые не могут быть ни доказаны, ни опровергнуты в арифметике. В то же время, эти внешние теории страдают тем же недостатком: в них имеются свои геделевы утверждения — и так, опять же, до бесконечности. Единой совершенной теории арифметики не существует. Есть более сильные фундаментальные теории и более слабые — например, аксиоматическая теория множеств ZFC сильнее аксиоматической арифметики Пеано в том смысле, что первая доказывает утверждения, недоказуемые в последней, но «абсолютной» фундаментальной теории все-таки существовать не может,

Стоит, для полноты картины, привести здесь, без доказательства или рассуждения, формулировку второй теоремы Геделя о неполноте арифметики:

Если фундаментальная система теорем арифметики, выводимая формальной системой, содержит доказательство собственной непротиворечивости, тогда и только тогда эта система противоречива.

Далее нам следует порассуждать о последствиях результатов, полученных Геделем, для математики, и лишь затем мы рассмотрим различные аргументы о применимости этих результатов к моделям и сущности сознания и мышления.

1  2   3   4  5  6  7
__________________________________
8. Множество аксиом ЭА счетно-бесконечно, они тоже выводятся правилами.

9. В ЭА рассматриваются натуральные числа, поэтому переменная может принимать значения 1, 2, 3 и так далее. Если x переменная, то (x+1) будет иметь значения 2, 3, 4 — иными словами, 2 или больше.

10. Совсем уж строго говоря, и это сомнительно, потому что аксиомы порождаются схемой, и их бесконечно много, поэтому все их проверить нельзя.

11. Парадокс, обнаруженный Бертраном Расселом в теории множеств, популярно сформулирован в википедии (англ.) так. Введем признак «нормальности»: нормальное множество не является своим собственным подмножеством. Например, множество всех квадратов нормально, потому что оно само не есть квадрат. Его дополнительное множество, множество всех неквадратов, не нормально, потому что оно само не квадрат и, следовательно, должно включать и себя. Теперь возьмем множество всех нормальных множеств, и зададимся вопросом, нормально оно или нет? Это парадокс. Если мы предположим, что оно нормально, то оно входит само в себя, и, следовательно, не нормально. Если предположить, что оно не нормально, то его не будет среди всех нормальных множеств, и, значит, оно не подмножество себя — то есть, нормально. Противоречие возникает при любом предположении.

12. Конструктивной в математическом смысле: требуется не только доказать существование алгоритма, доказывающего теоремы, но и отыскать сам этот алгоритм.

13. Бета-код Геделя основан на взаимно-простых числах и формулируется сложнее, но делает дальнейшие доказательства более эффективными. Для наших качественных рассуждений, однако, конкретный способ кодирования не важен.

14. Замечательное неформальное описание этого вывода дается в [1], глл. XIII и XIV, а формальный вывод в [2].
Tags:
fregimus: (Default)
1   2   3  4  5  6  7

V. Кубики со смыслом

Никакого смысла в строках системы ХИХИ нет. Математика — игра ума. Математики любят играть в кубики и смотреть, как ведет себя система из кубиков, правила которой придуманы произвольно, но жестко соблюдаются. Эта игра интересна сама по себе; никакой другой ценности от нее математику не требуется.

Интересно, однако, понять, какое место занимают ФС в ряду прочих математических инструментов. Чтобы ФС «заговорила» о математике, нам потребуется наделить строки ФС смыслом. Смысл этот мы присваиваем только результату работы ФС; на самом процессе ее работы он не сказывается. Смысл этот, таким образом, определяется снаружи ФС.

Как осмыслить результат работы системы ХИХИ, я не представляю. Это не значит, что смысла нет, или что он есть, но неизвестен. Смысл мы придаем строкам по желанию, любые утверждения о его существовании бессодержательны. Возможно, что кто-то сопоставит строки этой системы с другим математическим объектом, и это даст толчок какой-то новой его идее.

Мы же сейчас рассмотрим другую ФС. Ее алфавит состоит из трех символов: { •, §, # }. Единственную строку •§•#•• будем считать верной по определению. Введем следующие два правила получения новых верных строк:

1. К верной строке можно приписать слева и справа по •, например, из верной строки •§•#•• выйдет по этому правилу ••§•#•••
2. Слева и справа от символа # в верной строке можно вставить по •: из строки •§•#•• получится •§••#•••

Применяя эти правила по очереди в разных сочетаниях, можно получить, например, такие строки (все они будут верными):

••§•••#•••••
••••§•#•••••
•••§•••#••••••

Вы наверняка уже заметили, что если заменить число звездочек на натуральное число и понимать § как операцию сложения, а # как равенство, строки эти можно осмыслить как 2+3=5, 4+1=5, 3+3=6. Я нарочно не сделал + и = символами алфавита нашей системы, а выбрал для этого § и #, чтобы подчеркнуть, что мы осмысливаем § как +, а # как = вне системы.

Кроме того, возможно и иное осмысление. Введем операцию «отнять от» и обозначим ее ÷, например, 1 отнять от 5 даст 4: 1÷5=4. Теперь мы можем задать иной смысл формальному результату: заменим § на =, а # на ÷, и получим тогда верные арифметические выражения: 2=3÷5, 4=1÷5, 3=3÷6.

Формальную систему можно осмыслить множеством способов — насколько хватит фантазии играющего в кубики.

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

VI. Семантика

До сих пор, мы четко разграничивали формальную («внутреннюю») и интерпретационную («внешнюю») стороны ФС. Сейчас мы с вами построим из ФС и ее избранной интерпретации новый объект, формальную систему со смыслом, или семантикой (ФСС). Каждый раз, когда вы читаете фразу «ФС говорит, что…», «ФС утверждает…», вы имеете дело с ФСС, включающей некоторую интерпретацию ее строк. Такие выражения — совершенно общее место в литературе. Мы, тем не менее, не случайно заострили внимание на различении синтаксиса системы (механических правил преобразования символов) и ее семантики — слоя, положенного поверх синтаксиса и предназначенного для осмысления результата ее работы.

Синтаксис ФС заключен в себе. Это означает, что нам ничего не стоит написать компьютерную программу, которая выполнит все преобразования строк. Семантика ФСС, с другой стороны, не замыкается на себя, но неизбежно обращается к другим понятиям. Чтобы осознать это, рассмотрим осмысление нашей предыдущей ФС в виде ФСС, описывающей сложение натуральных чисел.

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

Теперь определим § как операцию сложения, а # как равенство, как мы уже делали ранее. Это привнесет новые, уже знакомые нам арифметические понятия сложения натуральных чисел и сравнения их между собой. Результатом сложения является натуральное же число, например, складывая 3 и 4, получим 7. Результатом сравнения чисел может быть одно из двух значений: истина или ложь. Например, утверждение 2=2 истинно, а 2=5 ложно.

Легко показать, что наша ФСС производит все верные выражения для сложения натуральных чисел, и не выдает ни одного неверного7.

Давайте взглянем внимательно, как проходит наша новая, семантическая граница, что находится теперь внутри и вовне ФСС. Утверждение 2+2=4 выводится внутри семантики ФСС, той предметной области, в которой определена наша смысловая интерпретация. Однако, утверждение «2+2=4 истинно» лежит вовне нашей новой системы. Когда мы говорим о семантической интерпретации, следует отличать истинность, которую мы определяем для себя, сравнивая результат осмысления строк системы с «внешним миром», и выводимость, возможность получения строки-утверждения в ФС. Выводимость утверждения (в семантической области мы называем строки утверждениями) определяется формализмом системы. Истинность же «на самом деле» система сама по себе не утверждает; любое «на самом деле», какой бы смысл ни вкладывался в эти слова, находится всегда вовне системы.

Это утверждение, если мы с вами рассуждаем о такой простой системе, конечно же, тривиально. В дальнейшем, однако, когда мы рассмотрим более сложную ФСС, вынесение «истинности» за границу системы создает серьезные диалектические вопросы в понимании математики.

VII. Элементарная арифметика

ФСС, которую мы рассмотрели, порождает результат чрезвычайно тривиальный: перечисление всех выражений вида a+b=c с конкретными числами. Однако, далеко не все формальные системы так просты. Назначая правила синтаксиса и базовую семантику символов, мы можем получить и систему, которая, как оказывается, выводит теоремы элементарной арифметики!

Тоже мне, скажете вы, особое достижение — элементарная арифметика! Это ведь то, что мы к третьему классу уже все знали, сложение-умножение? Нет, неверно. Младшеклассникам, изучающим арифметику в школе, показывают даже не краешек, а тень этой математической горы! К элементарной арифметике (ЭА) относятся, например, задачи решения диофантовых уравнений, изучение простых чисел, и очень многое другое. К примеру, Великая теорема Ферма, остававшаяся недоказанной несколько веков, тоже относится к области арифметики. Вся современная компьютерная криптография имеет в своей научной основе арифметику. А элементарной мы называем такую систему арифметики вовсе не потому, что она очень простая, а потому, что она не требует основания в других разделах математики, строится на основе своих собственных аксиом. Геометрия Эвклида тоже будет в этом смысле элементарной геометрией, потому что она не требует для основания ничего, кроме своих собственных понятий и аксиом.

Так же, как и в геометрии, где не определяются некоторые понятия, например,точки или прямой, в арифметике тоже есть неопределимые понятия. Одно из них — интуитивно знакомое всем натуральное число. Хоть нам все интуитивно известно, что такое число, никакого определения числа арифметика не дает. Аксиомами задаются лишь их свойства, такие, как «для каждого числа есть ровно одно последующее число», «1 не следует ни за каким числом» и прочие. Устройством своих основ ЭА напоминает геометрию; хотя последней уделяется в школе определенное внимание, аксиоматическое определение арифметики в школе не упоминается вовсе.

В число теорем арифметики включаются, разумеется, и утверждения, широко известные под именем собственно теорем («для любого натурального числа существует превышающее его простое число»), и более частные утверждения, возникающие при решении отдельных задач («не существует трех простых чисел, больших 3, подряд через одно», т. е. для любого простого числа p>3, по крайней мере одно из p+2 и p+4 не является простым), и совсем уж тривиальные, не интересные, на первый взгляд, утверждения (например, «для любого числа а, 0+а=а»).

В этом популярном изложении не найдется места детальному описанию ФСС, производящей теоремы ЭА. Если вас интересуют подробности ее работы и устройства, лучше обратиться к [1] за популярным изложением или к [2] за глубоким математическим изъяснением предмета. Мы ограничимся только общими принципами ее построения, и сама теорема Геделя будет объяснена лишь «на пальцах», без надлежащих стройных формулировок и строгих доказательств.

1   2   3  4  5  6  7
__________________________________
6. Подумайте, как можно пронумеровать строки, порождаемые нашей системой.

7. Попробуйте, в качестве упражнения, доказать это.
Tags:

Profile

fregimus: (Default)
fregimus

March 2014

S M T W T F S
       1
2 3456 78
910 1112 131415
16171819202122
23242526272829
3031     

Syndicate

RSS Atom

Most Popular Tags

Page Summary

Page generated 2017-09-23 02:06

Expand Cut Tags

No cut tags