Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 301

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 295 296 297 298 299 300 < 301 > 302 303 304 305 306 307 .. 316 >> Следующая

естандартне модели, которые потребовали явного различения языка и метаязка, привели к следуим двум парадоксам.
Множество всех стандартных действительных чисел является частью нестандартного конечного множества. Таким образом, бесконечное может быть частью конечного.
-
ют все свойства стандартных множеств. Множество стандартных действительных чисел ограничено сверху любым положительным бесконечно большим числом. Значит, должно быть либо наибольшее стандартное действительное число, либо наименьшее бесконечно большое. Но для любого стандартного x x + 1 также стандартно, а для бесконечно большого x x — 1 также бесконечно.
Оба этих парадокса основаны на том, что свойство "быть стандартным" при-надлеит метаязку. ервый из них послу ил основой теории полумножеств, в которой классы могут быть подклассами множеств.
§ B.3. ИДЕАЛЬНЫЕ И РЕАЛЬНЫЕ ПОНЯТИЯ ПО ГИЛЬБЕРТУ
естандартне модели явно и бескомпромиссно высветили то, что понималось ведуими мыслителями ее до их построения. Часто м строим в математике идеальные понятия, которые не имеют никакой (вычислительной) интерпретации, и при их помощи получаем реальные результаты.
Это наблюдение Д. Гильберт сделал основой своей методологической концепции математического знания. Согласно методологии Гильберта, основная часть математических понятий идеальна, и не стоит да е птаться дать им пряму интерпретаци . о идеальные понятия могут привести к реаль-нм результатам, которе, на самом деле, и составля т основну ценность математики для приложений. Гильберт считал, что без идеальных понятий
868
ПРИЛОЖЕНИЕ B. МЕТОДОЛОГИЧЕСКИЕ РЕЗУЛЬТАТЫ
практически невозмо но было бы достичь больинства ценнх реальных результатов современной математики (смотрите, например, фракталы и их применение в машинной графике; этот пример, конечно же, еще не был известен Гильберту, но он исключительно ярко демонстрирует роль идеальных понятий и полученных при их помощи реальных следствий). Hо Гильберт был уверен в возможности хотя бы в принципе устранить идеальные понятия из математических рассуждений. Развитие логики опровергло эту его слишком оптимистичную надежду. Его трезвый и жесткий взгляд оказался все-таки недостаточно естким.
Если посмотреть чуть пристальнее, то видно, что оппозиция идеальности и реальности не является бинарной и абсол тной. ля вычислителя действительные числа являются идеальными объектами, поскольку в принципе они могут быть вычислены сколь угодно точно, а у реального вычислителя точность вычислений, да и исходных данных, ограничена. о в сопоставлении с нестандартными числами действительне числа выглядят реальнми объектами.
§ B.4. ПАРАДОКС ИЗОБРЕТАТЕЛЯ
Д. Пойа ввел понятие парадокса изобретателя независимо от концепции идеальных объектов . Гильберта. н использовал набл дение, что при доказательстве по индукции часто необходимо усиливать доказваемое пред-ло ение, и индуктивное утвердение становится намного сло нее конечного результата. Эта необходимость усиливать результат, чтобы его строго обосновать, на первый взгляд кажется парадоксальной.
арадокс изобретателя связан со следуей логической и методологической проблемой. В доказательствах поро встреча тся вспомогательне утвердения, более сло ные, чем извлекаемые из них следствия. о но ли хотя бы в принципе устранить окольные пути в доказательствах, когда мы доказываем лемму лишь затем, чтобы в дальнейшем применить ее в частных случаях? Доказательства без окольных путей называют также прямыми.
Логические корни парадокса изобретателя оказались искл чительно глубоки и связыва т его с концепцией идеальнх понятий и с современнми методологическими рассмотрениями.
Первым в данном ряду явился результат Хао Вана (1954 г.). Он построил последовательность примитивно-рекурсивных функций fn, таких, что для доказательства утверждения Vxfn(x) = 0 необходимо воспользоваться индукцией по формулам, содержащим не менее чем n кванторов. Таким обра-
B.5. ТИПЫ И ПОРЯДКИ
869
зом, даже в принципе в математических доказательствах внешне про стах предложений нельзя обойтись без сложных лемм.
В. Оревков (1970) показал, что, хотя, как было известно ранее, в принципе в чистой логике мо но устранить все лемм и пользоваться прямми доказательствами, проигры от их устранения непоправимо больой. н построил последовательность формул, таку , что длина доказательства n-ной формулы с окольными путями пропорциональна 13n, а длина прямого вывода не может быть меньше
Естественно, что сложность лемм при продвижении по данной последовательности быстро возрастает.
В дальнейшем Р. Л. Гудстейн (1974) показал, что чем эффективнее программа, тем более высокие теоретические концепции могут понадобиться для доказательства ее правильности.
арадокс изобретателя показывает полну методологическу несостоятельность редукционизма и эмпиризма (в том числе и такой его философской профанации, как утилитаризм). Без концепций и идей высих уровней человек обречен на умственное и духовное пресмыкание!
§ B.5. ТИПЫ И ПОРЯДКИ
арадокс изобретателя остро ставит вопрос о критериях измерения сло -ности формул и, в более обем виде, об иерархии идеальных концепций. Простой, но весьма действенный, способ оценки уровня понятий и объектов дал Б. Рассел. Он предложил классифицировать объекты по типам. И сходные данные — объекты нулевого типа. Множества исходных данных и функции над ними — объект первого типа. но ества и функции над объектами первого типа — объекты второго типа.
Предыдущая << 1 .. 295 296 297 298 299 300 < 301 > 302 303 304 305 306 307 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100