Числовые множества (стр. 3 )

 

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

Теперь возникает риторический вопрос: свойство быть импредикабельным будет ли само по себе импредикабельно? Нетрудно показать две ветки рассуждений:

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

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

Итак, напрашивается неутешительный вывод: свойство быть импредикабельным импредикабельно тогда и только тогда, когда оно не импредикабельно. С виду нелепость, на самом деле серьезный и даже в некотором смысле плачевный вывод. Возникает невольное ощущение, что сами законы мышления по сути противоречивы.

Далее приведем итоги многолетних исследований в этой сфере. Причинами появления парадоксов считаются:

·  Допущения теорией сверхобширных множеств типа «множества всех множеств».

·  Сверхобширные множества допускаются в качестве элементов некоторых объектов.

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

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

·  Включение в теорию всех основных достижений канторовской теории множеств.

·  Непротиворечивость.

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

Итак, ни для одной из созданных теорий непротиворечивость не была доказана, хотя показано что известных парадоксов они не содержат. В частности, в 1908 году немецкий математик Эрнст Цермело предложил формальную систему аксиом для теории множеств, которая охватывает все современные математические рассуждения и при этом считается свободной от парадоксов. Ранее, в 1889г, такая система аксиом для обычной арифметики была предложена итальянским математиком Джузеппе Пеано. Пеано впервые сформулировал аксиомы арифметики, казавшиеся до смешного очевидными (существует нуль; за каждым числом следует еще число и т. д.), но на самом деле абсолютно исчерпывающие. Они играли ту же роль, что и постулаты великого Евклида в геометрии. Исходя из подобных утверждений, с помощью логических рассуждений, можно было получить основные арифметические теоремы.

В тот же период немецкий математик Готлиб Фреге выдвинул еще более амбициозную задачу. Он предложил не просто аксиоматически утвердить основные свойства исследуемых объектов, но и формализовать, кодифицировать сами методы рассуждений, что позволяло записать любое математическое рассуждение по определенным правилам в виде цепочки символов. С именем и научными изысканиями Фреге связана, пожалуй, одна из самых драматических историй в развитии науки о числах. Когда второй том его трудов был уже в печати, ученый получил письмо от молодого английского математика Бертрана Рассела. Поздравив коллегу с выдающимися результатами, Рассел, тем не менее, указал на одно обстоятельство, прошедшее мимо внимания автора. Коварным «обстоятельством» был получивший впоследствии широкую известность «парадокс Рассела», рассмотренный выше под названием Теорема 2.6.(2) и по сути представлявший собой вопрос: будет ли множество всех множеств, не являющихся своими элементами, своим элементом? Фреге не смог немедленно разрешить загадку, очень расстроился, взял академический отпуск в своем университете, потратил массу сил, пытаясь подправить свою теорию, но все было тщетно. Он прожил еще более двадцати лет, но не написал больше ни одной работы по арифметике.

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

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

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

В первой половине 20-х гг. Гильберт, вокруг которого сложилась к тому времени школа блестящих последователей, в целой серии работ наметил план исследований в области оснований математики, получивший впоследствии название «Геттингенской программы». В максимально упрощенном виде ее можно изложить следующим образом: математику можно представить в виде набора следствий, выводимых из некоторой системы аксиом, и доказать, что:

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

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

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

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

Однако в 1931 году венский математик Курт Гёдель разрушил все надежды. Он опубликовал короткую статью, попросту опрокинувшую весь мир так называемой «математической логики». После долгих и сложных математико-теоретических преамбул он установил буквально следующее удивительное свойство любой системы аксиом: «Если можно доказать утверждение A, то можно доказать и утверждение не-A». То есть, возвращаясь к формулировке второй задачи Гильберта, если система аксиом полна (то есть любое утверждение в ней может быть доказано), то она противоречива.

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

Т.2.6.(4) Слабая теорема Геделя о неполноте

(без доказательства)

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

Но на этом Гёдель не остановился, сформулировав и доказав вторую, или сильную теорему Гёделя о неполноте: «Логическая полнота (или неполнота) любой системы аксиом не может быть доказана в рамках этой системы. Для ее доказательства или опровержения требуются дополнительные аксиомы (усиление системы)». Её можно сформулировать иначе.

Т.2.6.(5) Сильная теорема Геделя о неполноте

(без доказательства)

Пусть T — корректная формальная система. Тогда можно построить конкретное утверждение G, обладающее следующим свойством: G истинно, но недоказуемо в T.

Формальная система аксиом называется консистентной, если она не может доказать одновременно какое-то утверждение и его отрицание, т. е. доказать противоречие.

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

Т.2.6.(6) Третья теорема Геделя о неполноте

(без доказательства)

Пусть T — консистентная формальная система. Тогда T не является полной системой, т. е. существует утверждение G такое, что T не может его ни доказать, ни опровергнуть; более того, мы можем построить такое конкретное G (называемое "гёделевым утверждением").

Неполнота системы T утверждается в качестве результата только в третьей версии, но легко видеть, что она сразу следует из заключения и в первых двух теоремах. Уже в них видно, что существует какое-то истинное, но недоказуемое утверждение. Такое утверждение T не доказывает, но и опровергнуть его — доказать его отрицание — система не может, т. к. его отрицание ложно, а T (в первых двух вариантах теоремы) корректна и доказывает только истинные утверждения. Поэтому T не может ни доказать, ни опровергнуть такое утверждение G и, следовательно, T неполна.

Спокойнее было бы думать, что теоремы Гёделя носят отвлеченный характер и касаются лишь областей возвышенной математической логики, однако фактически оказалось, что они напрямую связаны с устройством человеческого мозга. Английский математик и физик Роджер Пенроуз показал, что теоремы Гёделя можно использовать для доказательства наличия принципиальных различий между человеческим мозгом и компьютером. Смысл его рассуждения прост. Компьютер действует строго логически и не способен определить, истинно или ложно утверждение А, если оно выходит за рамки аксиоматики, а такие утверждения, согласно теореме Гёделя, неизбежно имеются. Человек же, столкнувшись с таким логически недоказуемым и неопровержимым утверждением А, всегда способен определить его истинность или ложность — исходя из повседневного опыта. По крайней мере, в этом человеческий мозг превосходит компьютер, скованный чистыми логическими схемами. Человеческий мозг способен понять всю глубину истины, заключенной в теоремах Гёделя, а компьютерный - никогда.

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

Предположим, что математические способности некоторого математика, назовем его Человек_Разумный, полностью описываются некоторой формальной системой F. Это означает, что любое математическое утверждение, которое Человек_Разумный признает "неоспоримо верным", является теоремой, доказываемой в F, и наоборот. Предположим, также, что Человек_Разумный знает, что F описывает его математические способности. Человек_Разумный также полагает, что тот факт, что F описывает его математические способности, эквивалентен вере в непротиворечивость и непогрешимость F. В противном случае мы должны были бы поставить под сомнение истины, которые представляются нам "неоспоримо истинными". Согласно теореме Геделя о неполное формальных систем, поскольку F непротиворечива, существует геделевское предложение G(F), которое должно быть истинным, но которое не является теоремой в системе F. Однако, поскольку Человек_Разумный верит, что F - непротиворечивая система и знает, что F представляет его способность к математическим рассуждениям, он должен прийти к выводу, что G(F) является "неоспоримой истиной". Таким образом, мы получаем математическое утверждение G(F), которое Человек_Разумный признает истинным, но которое не является теоремой в F , что противоречит первоначальному предположению, что F представляет целиком и полностью математические способности Человека_Разумного.

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

Первый вариант теста, опубликованный в 1950 году, был несколько запутанным. Современная версия теста Тьюринга представляет собой следующее задание. Группа экспертов общается с неизвестным существом. Они не видят своего собеседника и могут общаться с ним только через какую-то изолирующую систему - например, клавиатуру. Им разрешается задавать собеседнику любые вопросы, вести разговор на любые темы. Если в конце эксперимента они не смогут сказать, общались ли они с человеком или с машиной, и если на самом деле они разговаривали с машиной, можно считать, что эта машина прошла тест Тьюринга.

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

Сирл, преподаватель философии Калифорнийского университета в Беркли, разработал воображаемую систему, которая показывает, что ответ на этот вопрос отрицательный. Эта система под названием «Китайская комната» работает следующим образом. Вы сидите в комнате. В стене этой комнаты есть две щели. Через первую щель вам передают вопросы, написанные по-китайски. (Предполагается, что Вы, как и Джон Сирл, не знаете китайского. Если это не так, выберите какой-нибудь другой язык, неизвестный Вам). Затем вы просматриваете книги с инструкциями типа: «Если вы получили такой-то набор символов, напишите на листке бумаги такой-то (отличный от исходного) набор символов и передайте его обратно через другую щель».

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

§ 2.7. Вычислимые числа

 

Действительное число вычислимо, если существует алгоритм его вычисления с любой степенью точности.

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

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

Важно отметить, что все рациональные числа суть алгебраические, т. к. они могут быть представлены как корни уравнения a0+a1x=0, где a0 , a1 – целые числа.

Т.2Теорема

Множество вычислимых действительных чисел счетно.

Доказательство

Вычислимые числа включают в себя все алгебраические и некоторые трансцендентные числа. Так как каждому вычислимому действительному числу соответствует хотя бы одна машина Тьюринга, а машин Тьюринга - À0, то значит вычислимых чисел никак не больше, чем À0. С другой стороны, поскольку все алгебраические числа вычислимы, а их тоже À0, то вычислимых действительных чисел никак не меньше, чем À0. Значит мощность множества вычислимых действительных чисел равна À0 и, следовательно, это множество счетно, Q. E.D.

Т.2Теорема

Существуют невычислимые действительные числа и их несчетное множество.

Доказательство

Существование невычислимых чисел следует хотя бы из того факта, что всего действительных чисел несчетное множество, а вычислимых – счетное. Значит должно существовать несчетное множество невычислимых действительных чисел, Q. E.D.

Пример невычислимого действительного числа:

Пусть имеются Тi,……,Тn,…, где i – i-ая машина Тьюринга.

Действительное число Х можно представить так:

Х= 0,a1,……,an…., где:

1, если Тi останавливается на чистой ленте

ai=

0, в противном случае

Такое число является невычислимым, так как задача об остановке машины Тi на чистой ленте алгоритмически не разрешима.

Задачи к Главе 2

Установление взаимно-однозначных соответствий

Задача 2.1. 

Установить взаимно-однозначное соответствие между промежутком 0<х<1 и всей числовой прямой.

Задача 2.2.   

Установить взаимно-однозначное соответствие между промежутком a≤х≤b и c≤х≤d.

Задача 2.3.   

Установить взаимно-однозначное соответствие между промежутком 0≤х<1 и 0≤x<∞.

Задача 2.4.   

Установить взаимно-однозначное соответствие между промежутком -1<х<1 и 0≤x<∞.

Задача 2.5.   

Установить взаимно-однозначное соответствие между промежутком -1<х≤1 и 0<x<∞.

Задача 2.6.   

Установить взаимно-однозначное соответствие между промежутком 0≤х≤1 и множеством иррациональных чисел того же отрезка.

Задача 2.7.   

Установить взаимно-однозначное соответствие между всеми точками плоскости и точками сферы радиуса 1.

Задача 2.8.   

Установить взаимно-однозначное соответствие между точками открытого квадрата 0<х<1, 0<y<1 и точками плоскости.

Задача 2.9.   

Установить взаимно-однозначное соответствие между множеством всех рациональных чисел отрезка 0≤х≤1 и множеством всех точек плоскости, обе координаты которых рациональны.

Задача 2.10.   

Установить взаимно-однозначное соответствие между точками окружности радиуса a и b, a≥b.

Счетность множеств

Задача 2.11.   

Является ли счетным множество всех конечных подмножеств счетного множества?

Задача 2.12.   

Является ли счетным любое множество попарно непересекающихся букв Т на плоскости?

Задача 2.13.   

Является ли счетным любое множество попарно непересекающихся букв Г на плоскости?

Задача 2.14.   

Является ли счетным любое множество попарно непересекающихся открытых интервалов на действительной прямой?

Задача 2.15.   

Является ли счетным множество точек разрыва монотонной функции на действительной прямой?

Задача 2.16.   

Можно ли построить на плоскости несчетное множество попарно непересекающихся окружностей?

Задача 2.17.   

Можно ли построить на плоскости несчетное множество попарно непересекающихся букв N?

Задача 2.18.   

Можно ли построить на плоскости несчетное множество попарно непересекающихся букв Б?

Мощность множеств

Задача 2.19.   

Найти мощность множества всех четырехугольников на плоскости, координаты всех вершин которых рациональны.

Задача 2.20.   

Найти мощность множества всех многоугольников на плоскости, координаты всех вершин которых рациональны.

Задача 2.21. 

Найти мощность множества всех многочленов с действительными коэффициентами.

Задача 2.22. 

Найти мощность множества всех действительных чисел, в десятичном разложении которых встречается цифра 3.

Задача 2.23. 

Найти мощность множества всех действительных чисел, в десятичном разложении которых не встречается цифра 6.

Задача 2.24. 

Найти мощность множества всех действительных чисел 0<х<1, в десятичном разложении которых после запятой стоит цифра 4 и больше эта цифра не встречается.

Задача 2.25.   

Найти мощность множества всех непрерывных функций на действительной прямой.

Задача 2.26. 

Найти мощность множества всех функций, определенных на сегменте a≤х≤b при a<b и разрывных хотя бы в одной точке.

Глава 3. Арифметические вычисления

§ 3.1. Арифметические функции

Расширенное множество натуральных чисел, помимо обычного множества натуральных чисел, включает также число ноль (ранее это множество обозначалось N*). Далее в этой главе и в последующих главах слово «расширенное» для краткости будет опускаться, и под терминами «N», «натуральный ряд», «натуральное число», «множество натуральных чисел» следует понимать «N*», «расширенный натуральный ряд», «натуральное число или 0», «расширенное множество натуральных чисел» соответственно.

Арифметическая функция – функция, определенная на множестве натуральных чисел и принимающая значения из множества натуральных чисел.

 

Т.3.1.(1) Теорема

Множество арифметических функций n-переменных несчетно.

Доказательство

Для доказательства несчетности множества достаточно доказать несчетность какого-нибудь его подмножества. Рассмотрим арифметические функции одной переменной вида f i(x). Эти арифметические функции одной переменной образуют подмножество множества арифметических функций n переменных.

Предположим противное. Пусть арифметических функций одной переменной счетное множество, т. е. их можно перечислить. Тогда их можно расположить в виде бесконечной последовательности f0(x), f1(x), f2(x), … , fn(x),…

Построим новую функцию g(x)=fx(x)+1.

Это так называемая диагональная функция, например:

g(0)= f0(0)+1, g(1)= f1(1)+1, g(2)= f2(2)+1, …

g(x) отлична от всех перечисленных функций, т. к. от каждой из функций она отличается хотя бы в одной точке. Например, от функции f0(x) функция g(x) отличается в точке х=0, от функции f 1(x) функция g(x) отличается в точке х=1 и т. д. Однако по построению g(x) принадлежит множеству арифметических функций одной переменной, значит должна быть в списке перечисления fi(x), т. е. совпадать с одной из перечисленных функций. Получили противоречие, следовательно, исходное предположение неверно, и функций одной переменной несчетное множество.

Поскольку множество арифметических функций одной переменной является подмножеством множества арифметических функций n переменных, то значит множество арифметических функций n переменных несчетно, Q. E.D.

Арифметическая функция называется вычислимой, если существует алгоритм для ее вычисления в каждой точке.

В силу тезиса Тьюринга это означает, что функция вычислима, если существует машина Тьюринга, ее вычисляющая.

Т. 3.1.(2) Теорема

Множество вычислимых арифметических функций счетно.

Доказательство

Так как каждой вычислимой арифметической функции соответствует хотя бы одна машина Тьюринга, а машин Тьюринга À0, то значит вычислимых арифметических функций никак не больше чем À0. Получим: |ВАФ| ≤À0.

С другой стороны, подмножеством множества вычислимых арифметических функций являются, например, функции вида f(x)=n, где n – натуральное число. Поскольку натуральных чисел À0, то вычислимых арифметических функций никак не меньше чем À0. Получим: |ВАФ|≥À0. Значит, мощность множества вычислимых арифметических функций равна À0, а значит оно счетно, Q. E.D.

Т. 3.1.(3) Теорема Тьюринга

Множество вычислимых арифметических функций n переменных не поддается эффективному перечислению.

Доказательство

Предположим противное. Пусть множество вычислимых арифметических функций n переменных эффективно перечислимо. Тогда существует алгоритм, по которому его можно перечислить. Применим этот алгоритм. Получим последовательность:

f0(x1,…,xn), f1(x1,…,xn),…, fn(x1,…,xn),…

Построим диагональную функцию:

 

fx1(x1,…,xn)+1, при x1=…=xn

g(x1,…,xn)=

0, в противном случае

Пример (пусть n=3)

g (0,0,0)=f0(0,0,0)+1

g (0,0,1)=0

g (0,1,0)=0

g (1,1,1)=f1(1,1,1)+1

g (1,1,2)=0

По построению видно, что функция g(x1,…,xn) – арифметическая. Докажем, что, кроме этого, она является вычислимой. Для этого должен существовать алгоритм её вычисления. Укажем алгоритм вычисления g(x1,…,xn). Для любых значений x1,…,xn мы можем сначала провести операцию сравнения.

1) Если x1=…=xn, запускаем алгоритм перечисления вычислимых арифметических функций fi(x1,…,xn). Этот алгоритм существует в силу нашего предположения. Находим функцию с номером x1, т. е. fx1(x1,…,xn). Далее применим к ней алгоритм вычисления в точке (x1,…,x1), т. е. вычислим fx1(x1,…,x1). Такой алгоритм существует в силу вычислимости функций вида fi(x1,…,xn). Прибавление к результату вычисления единички есть тривиальная арифметическая операция, т. о. при одинаковых значениях аргументов g(x1,…,xn) = fx1(x1,…,x1) +1 вычислима.

2) Если условие x1=…=xn не выполняется, т. е. не все значения аргументов равны, то значение g(x1,…,xn) приравнивается нулю, т. о. при различных значениях аргументов g(x1,…,xn)=0 тоже вычислима.

Т. о. видно, что диагональная функция g(x1,…,xn) принадлежит множеству вычислимых арифметических функций n переменных.

Раз построенная функция принадлежит к множеству вычислимых арифметических функций, то она должна быть среди ранее эффективно перечисленных функций, но по построению она не может быть среди них, так как от каждой функции она отличается хотя бы в одной точке. Получили противоречие, следовательно, исходное предположение неверно и вычислимые арифметические функции n переменных нельзя эффективно перечислить, Q. E.D.

Т. 3.1.(4) Теорема

Множество невычислимых арифметических функций несчетно.

Доказательство

Ранее доказаны два утверждения:

·  АФ (арифметических функций) несчетное множество.

·  ВАФ (вычислимых арифметических функций) счетное множество.

Но при этом ВАФ есть подмножество АФ, а значит дополнение ВАФ до АФ (т. е. множество невычислимых функций) является несчетным. Значит, множество невычислимых арифметических функций несчетно, Q. E.D.

Т. о. доказано, что невычислимые арифметические функции существуют. Более того, их очень много – несчетное множество. Приведем пример невычислимой функции одной переменной.

Пусть T0 ,T1 ,T2 … ,Tx - машины Тьюринга. Определим функцию f1(x) следующим образом:

 

1, если Tx остановится на чистой ленте

f1(x) =

0, в противном случае

Эта функция везде определена, но алгоритма для решения проблемы остановки произвольной машины Тьюринга на чистой ленте не существует, значит, не существует алгоритма вычисления f1(x).

По большому счету, при построении такого рода функций (невычислимых) необходимо соблюдать два основных правила:

·  Следить за тем, чтобы значение функции в каждой точке было определено и являлось числом натуральным (значит, функция принадлежит множеству арифметических функций);

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

Тогда полученная функция будет являться невычислимой арифметической функцией.

Важно понимать, что могут существовать различные функции, которые не являются вычислимыми ни в одной точке. Например, приведенная ниже функция также не вычислима ни в одной точке:

8, если Tx напечатает бесконечное число нулей на ленте f2(x) =

3, в противном случае

С фактической точки зрения ничего не изменится: по-прежнему ни в одной точке функция f2(x) не может быть вычислена, точно также, как ни в одной точке не может быть вычислена функция f1(x). Но, тем не менее, f1(x) и f2(x) - это совсем разные функции, так как они имеют различные описания.

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

Т. 3.1.(5) Теорема

Множество арифметических функций, описываемых конечным числом слов, счетно и эффективно перечислимо.

Доказательство

Среди функций, описываемых конечным числом слов, содержатся ВСЕ вычислимые функции (алгоритм их вычисления и есть описание) и еще какие то иные, типа приведенных выше примеров f1(x) и f2(x). Однако на примере нумерации Гёделя, рассмотренной в ходе доказательства Теоремы 1.7.(2), видим, что множество функций, описываемых конечным числом слов (понятий / терминов / идей и т. д.), тоже может быть сопоставлено с рядом натуральных чисел, т. е. является счетным и даже эффективно перечислимым множеством, Q. E.D.

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

§ 3.2. Частичные арифметические функции

Частичная арифметическая функция (ЧАФ)– это функция, определенная на некотором подмножестве М множества натуральных чисел N и принимающая значения из множества N.

Класс частичных арифметических функций шире класса арифметических функций, т. к. любая арифметическая функция является всюду определенной частичной арифметической функцией и, кроме того, существуют не всюду определенные арифметические функции. Диаграмма вхождения рассмотренных множеств друг в друга представлена на рис.3.2(1).

Рис.

Примеры:

f(n) = n – 1

Для этой функции область определенности: М= [1, ∞), область значений: N. Т. о. функция строит соответствие {1, 2, …} ® N.

f(n) = 1 – n

Для этой функции область определенности: М= [0,1], область значений: [0,1]. Т. о. функция строит соответствие {0, 1} ® {0, 1}.

Можно выделить два крайних случая множества частичных арифметических функций f(n): M ® N:

1)  Всюду определенные функции. M = N. Множество всюду определенных частичных арифметических функций совпадает с множеством арифметических функций. Все остальные частичные арифметические функции имеют точки неопределенности.

2)  Нигде неопределенные функции. M = Æ. Например, f(n) = 0 – (n + 1). Нигде не определенные функции также являются подмножеством множества частичных арифметических функций.

Для задания области определенности или множества значений частичных арифметических функций удобно использовать способ задания подмножества А множества натуральных чисел N* через характеристическую функцию.

Характеристической функцией χA какого-нибудь подмножества А множества натуральных чисел N* называется функция от одной переменной, равная 1 в точках множества A и равная 0 в точках, не принадлежащих A.

Например:

·  Характеристическая функция χØ=0 (для пустого множества характеристическая функция всюду равна 0)

·  Характеристическая функция χN=1 (для множества натуральных чисел характеристическая функция всюду равна 1)

·  Характеристическая функция χA=unsg(|x-a1|∙|x-a2|∙…∙|x-an|) для множества A={a1,a2,..,an} : a1<a2<,..,<an

Т. 3.2.(1) Теорема

Множество частичных арифметических функций несчетно.

Доказательство

Поскольку множество АФ есть подмножество ЧАФ, и множество АФ несчетно, то и множество ЧАФ также несчетно, Q. E.D.

Вычислимая частичная арифметическая функция (ВЧАФ) – это функция, для которой существует алгоритм вычисления ее значения в любой точке области определенности.

Т. 3.2.(2) Теорема

Множество вычислимых частичных арифметических функций счетно и эффективно перечислимо.

Доказательство

Рассмотрим произвольную функцию f(x), принадлежащую множеству ВЧАФ. Раз функция вычислима – значит, ее можно вычислить на машине Пусть на входной ленте будет записан параметр функции x в унарном коде: | | | … | (х+1 палочка). Результат вычисления – значение f(x) также выдается в унарном коде: | | | … |. Если для данного x такой результат получен, значит, в точке х функция определена. Однако, если произошли следующие события:

·  машина испортила исходный параметр,

·  машина не остановилась,

·  машина напечатала нечитаемый результат,

то будем считать, что в данной точке х функция f(x) не определена.

Если именно так интерпретировать «неудобное» для нас поведение конкретной машины Тьюринга, то тогда можно утверждать, что любая машина Тьюринга вычисляет какую-нибудь ВЧАФ. Даже если машина при любом входном значении аргумента работает по совершенно не похожему на вычисление алгоритму, например, стирает любое слово на ленте, то мы просто считаем, что функция, которую вычисляет машина, вообще нигде не определена.

С другой стороны, для вычисления одной и той же функции может существовать несколько алгоритмов. Т. о. любой ВЧАФ может соответствовать несколько машин Тьюринга.

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

По сути, вычислимая частичная арифметическая функция задается не более и не менее, чем алгоритмом её вычисления в любой точке области определенности. Этот алгоритм может быть задан любым удобным образом: в виде аналитической формы (формулы), в виде набора инструкций машины Тьюринга, в виде алгоритма Маркова, в виде эффективного описания с помощью заранее согласованного языка и т. д. В этой связи, например, функция f(x)=x+1 может быть задана различными способами, и даже если сосредоточиться только на описании алгоритма в терминах набора инструкций (программы) машины Тьюринга, таких программ тоже можно составить несколько (точнее счетно-бесконечное множество) в силу хотя бы того факта, что добавление набора «холостых» инструкций (типа «напечатать число n в унарном коде и затем его стереть) к работающей программе не изменит её смысла, если таковым смыслом считать напечатанный после остановки результат.

При такой интерпретации термина «вычислимая частичная арифметическая функция» все становится совсем «чисто» и при перечислении машин Тьюринга мы действительно строго один раз перечисляем каждую вычислимую частичную арифметическую функцию, т. о. доказано что множество ВЧАФ является счетным и эффективно перечислимым, Q. E.D.

§ 3.3. Эффективное распознавание и сравнение функций

 

Эффективным распознаванием функций называется процедура, позволяющая при помощи некоторого алгоритма определить, относится ли данная функция к рассматриваемому классу.

Т. 3.3.(1) Теорема

Невозможно эффективно распознать функции-константы среди вычислимых арифметических функций.

Доказательство

Общая идея.

Пусть машина Тьюринга Т вычисляет некоторую функцию f(x). Если существует такая процедура эффективного распознавания – значит, существует и машина Тьюринга F, ее реализующая. В ходе своей работы машина F должна поочередно подставлять в качестве входных значений для машины Т натуральные числа и сравнивать результат работы машины Т с заданным числом (константой). Поскольку натуральных чисел – счетно-бесконечное множество, процесс сравнения может продолжаться бесконечно, а значит, однозначного ответа дать нельзя.

Строгое доказательство.

Без ограничения общности возьмем в качестве константы число 0. Построим функцию:

0, если машина T не остановится за первые (x+1) шагов

f Т(x)=

1, в противном случае

Например, если Т остановится на n–ом шаге, значения функции будут выглядеть так:

x f(x)

0 0

1 0

2 0

… …

n-1 0

n 1

n+1 1

… …

Т. о. функция f(x) окажется константой - ноль только в том случае, если машина T никогда не остановится на чистой ленте.

Предположим противное: пусть мы можем распознать константу - ноль среди ВАФ. Тогда для произвольной машины Тьюринга мы сможем с уверенностью сказать, остановится ли она когда-нибудь в ходе своей работы. Подобный вывод прямо противоречит теореме о неразрешимости проблемы остановки, следовательно, предположение неверно и константа-ноль (а также любые другие константы) не распознается эффективно среди вычислимых арифметических функций, Q. E.D.

Эффективным сравнением арифметических функций называется процедура, позволяющая при помощи некоторого алгоритма определить, совпадают ли значения функций во всех точках.

Т. 3.3.(2) Теорема

Вычислимые арифметические функции не поддаются эффективному сравнению.

Доказательство

Пусть имеются две вычислимые арифметические функции f1(x) и f2(x). Построим функцию g(x) = |f1(x) - f2(x)|. Данная функция является арифметической (т. к. определена на всем множестве натуральных чисел) и вычислимой (в силу вычислимости f1(x) и f2(x), а также вычислимости процедуры нахождения модуля разности их значений).

Функция g(x) является функцией константой-ноль, если сравниваемые функции равны. Далее продолжим доказательство теоремы методом «от противного».

Предположим противное. Пусть существует алгоритм эффективного сравнения двух функций. Это значит, что существует алгоритм распознавания функции-константы ноль среди всех вычислимых арифметических функций, что противоречит доказанной ранее теореме. Значит, исходное предположение неверно, и вычислимые арифметические функции не поддаются эффективному сравнению, Q. E.D.

Т. 3.3.(3)Теорема

Невозможно эффективно распознать функции-тождества среди вычислимых арифметических функций.

Доказательство

Построим функцию

 

х, если машина T не остановится за первые (x+1) шагов

fТ(x) =

х+1, в противном случае

Т. о. значения функции будут выглядеть так:

x fТ(x)

0 0

1 1

2 2

… …

n n+1

n+1 n+2

…

Т. о. функция f(x) окажется функцией-тождеством только в том случае, если машина T никогда не остановится на чистой ленте.

Предположим противное. Пусть мы можем распознать функции-тождества среди ВАФ. Тогда для произвольной машины Тьюринга мы сможем с уверенностью сказать, остановится ли она когда-нибудь в ходе своей работы. Подобный вывод прямо противоречит теореме о неразрешимости проблемы остановки произвольной машины Тьюринга на чистой ленте – следовательно, сделанное предположение неверно и функции-тождества не распознаются эффективно среди вычислимых арифметических функций, Q. E.D.

Т. 3.3.(4)Теорема

Невозможно эффективно распознать вычислимые арифметические функции среди вычислимых частичных арифметических функций.

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

Доказательство

1.  По теореме Поста (применительно к множествам ВАФ и ВЧАФ) множество ВАФ эффективно распознается в ВЧАФ тогда и только тогда, когда ВАФ эффективно перечислимо и ВЧАФ\ВАФ эффективно перечислимо.

2.  Предположим противное. Пусть ВАФ можно эффективно распознать в ВЧАФ. Тогда ВАФ эффективно перечислимо, а это противоречит Теореме 3.1.(3), согласно которой ВАФ эффективно не перечислимо.

Следовательно, исходное предположение неверно и ВАФ эффективно не распознаваемо в множестве ВЧАФ, Q. E.D.

Т. 3.3.(5)Теорема Черча

Невозможно эффективно распознать точки неопределенности вычислимой частичной арифметической функции.

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

Доказательство

1. Поскольку множество ВЧАФ n переменных эффективно перечислимо по Теореме 3.2.(2) , то перечислим их:

f1(x1, ..., xn), f2(x1, ..., xn), …

2. Построим диагональную функцию

 

0, если fx1(x1,...,xn) не определена

g(x1,...,xn)=

не определена, если fx1(x1,...,xn) определена

Видно, что g(x1,...,xn) является частичной арифметической функцией.

3.  Предположим противное, а именно что теорема Черча не верна и существует алгоритм эффективного распознавания точек неопределенности ВЧАФ. Тогда g(x1,...,xn) становится вычислимой частичной арифметической функцией, то есть ВЧАФ.

4.  Значит g(x1,...,xn) должна была попасть в перечисление множества ВЧАФ n переменных. Однако по построению g(x1,...,xn) отличается от всех перечисленных функций, т. о. в перечислении ее нет.

5.  Получили противоречие. Значит предположение неверно, т. е. не существует алгоритма эффективного распознавания точек неопределенности ВЧАФ, Q. E.D.

Задачи к Главе 3

Условие для задач 3.1.-3.6.

Пусть задана частичная арифметическая функция ƒ(x). Множество А - её область определенности, а множество В – её область значений. Найти характеристические функции множеств А и В.

Задача 3.1.

ƒ(x) = x–15

Задача 3.2.

ƒ(x) = 2x+5

Задача 3.3.

ƒ(x) = 3x–5

Задача 3.4.

ƒ(x) = x – 5

Задача 3.5.

ƒ(x) =(x-6) / (9-x)

Задача 3.6

ƒ(x) = 3x+4

Условие для задач 3.7.-3.12.

Пусть задана функция ƒ от одного или двух аргументов. Укажите все множества (АФ, ВАФ, ЧАФ, ВЧАФ), к которым принадлежит функция ƒ.

Задача 3.7.

ƒ(x, y) = -x-1-y

Задача 3.8.

ƒ(x, y) = 2x-1+3y

Задача 3.9.

ƒ(x) = 2x+3

Задача 3.10

x+4, если машина Тх не остановится на чистой ленте

ƒ(x) = 1 если остановится за первые 15 тактов

3x-1 если остановится позднее 15-ого такта

Задача 3.11

1 если машина Тх остановится за первые 18 тактов

ƒ(x) =

x+2 если машина Тх остановится позднее 18-ого такта

Задача 3.12

3x-2y, если x > y

ƒ(x, y) = y-x, если x < y

(x+y)/2 если x=y

Условие для задач 3.13.-3.15.

Для некоторой частичной арифметической функции ƒ(x) заданы множество А (область определенности) и множество В (область значений). Найти аналитический вид функции ƒ(x) и задать множества A и B с помощью характеристических функций.

Задача 3.13

А: (x>=11)∩ (mod(x,2)=0)

В: N

Задача 3.14

А: mod(x,2)=1

В: y>=8

Задача 3.15

А: x=1,2,4,8

В: y=10,6,4,3