Головна |
« Попередня | Наступна » | |
Конструктивна математика Маркова і Бішопа |
||
Зараз, коїда гігантська робота, виконана і самим Кантором, і рядом інших працювали слідом за ним видатних математичних мислителів, таких як JI. Е. Брауер, Д. Гільберт і А. А. Марков, відійшла в минуле і результати її стали загальним надбанням, нам все більш природною починає здаватися та - тепер уже дійсно проста - думка, що подібно кожному іншому складно влаштованому «творінню розуму і рук людських », математика - для доцільного, правильного і природного її функціонування - повинна бути розумно, по детально продуманим планом« зведена »на досить міцному« фундаменті »з використанням належно підібраного« будівельного матеріалу ». / /. Нагорний 81 Класичні математики вважають базисним для побудови всієї математики поняття безлічі. Інтуіціоністи - поняття вільно що стає послідовності. У 40-і рр.. XX в. виник новий напрям в обгрунтуванні математики, яке визнало поняття вільно що стає послідовності туманним, заснованим на суб'єктивістським витлумачувати понятті інтуїції, і замінило його поняттям алгорифма. Цей напрямок конструктивної математики очолив вітчизняний вчений - А. А. Марков (1903-1979). На становлень конструктивізму Маркова певний вплив справила робота А. Н. Колмогорова, присвячена переінтерпретації интуиционистской логіки як обчислення завдань (проблем) "3. Колмогоров показав, що кожне завдання, що виводиться з інтуїционістського числення висловів, має рішення. Значить, інтуїціоністське числення завдань можна було інтерпретувати як числення вирішуваних проблем. Конструктивна математика Маркова представляє «гілка интуиционистской математики, для якої характерне дослідження конструктивних об'єктів алгоріфміческімі методами» 82. Поняття конструктивного об'єкта і алгорифма є в цьому визначенні вирішальними. Конструктивний об'єкт - результат здійснення конструктивного процесу. Простим прикладом конструктивного процесу є «побудова ряду вертикальних рисочок ПІНІ шляхом писання однієї такої рисочки, приписування до ній праворуч її копії - другий рисочки, приписування до отриманих рискам ще однієї рисочки, потім ще однієї рисочки, потім ще однієї і ще однієї »83. Результатом конструктивного процесу є конструктивний об'єкт, зображений п'ятьма рядками вище. Під алфавітом у конструктивній математиці Маркова розуміється будь-який кінцевий набір чітко відмітних один від одного графічних символів (букв), а під словом в даному алфавіті - довільна кінцева ланцюжок букв цього алфавіту, включаючи порожнє слово (що не містить жодного знака і еквівалентне операції стирання знака). Більш точно, конструктивними математичними об'єктами називаються слова в алфавіті А, задовольняють наступним породжує правілам84: (а) якщо а - буква алфавіту А, то а являє собою слово в алфавіті А; (б) якщо Р - слово в алфавіті А і а - буква алфавіту А, то результат приписування букви а праворуч до слова Р є словом в алфавіті А; (в) порожнє слово А є словом в алфавіті А. Кожне слово - результат деякого побудови, до якого може бути застосовано нове побудова, а до отриманого ре-док - наступне побудова і т. д. Тому конструктивний математичний об'єкт - це не тільки актуально існуючі слова алфавіту, але і всі потенційні результати їх перетворень. Поняття алгорифма (такий транскрипцією слова «алгоритм» Марков відділяв свою теорію від інших теорій алгоритмів) представляє подальше уточнення поняття ефективного методу, обчислюваною (рекурсивної) функції. алгорифм створюється для вирішення якогось класу однотипних задач (проблем). Абстракція потенційної здійсненності - ідейна основа теорії алгорифм. «Здійснюючи конструктивні процеси, ми часто натрапляємо на перешкоди, пов'язані з браком часу, місця і матеріалу ... Проте ми надалі не будемо рахуватися з цими перешкодами в наших міркуваннях про конструктивні об'єктах. Ми будемо міркувати так, як якщо б цих перешкод не існувало, тобто як якби в кожен момент в нашому розпорядженні були і простір, і час, і матеріал, потрібні для здійснення чергового кроку розглянутого конструктивного процесу. Поступаючи так, ми будемо відволікатися від обмеженості наших можливостей в просторі, часу і матеріалі. Це відволікання прийнято називати абстракцією потенційної здійсненності »85. Теорія алгорифм Маркова - модель. математики, що реалізує дану абстракцію. Все конструктивісти виходять з того, що обчислювальні процеси в математиці здійснюються на основі певної символіки - слів деякого штучного алфавіту А - і являють перетворення одних буквених комплексів інші відповідно з точними приписами, званими алгорифм. «алгорифм є общепонятном припис, що однозначно визначає хід деяких конструктивних процес-сов». алгорифм повинні відповідати наступним загальним критеріям. По-перше, вони зобов'язані бути певними, тобто точними і зрозумілими для всіх людей або автоматів, які їх виконують, розпорядженнями. В таких приписах кожен новий крок однозначно (з точністю до однаковості одержуваних станів) детермінується попереднім йому кроком. По-друге, вони повинні допускати застосування для всього класу проблем, однотипних з розв'язуваної. По-третє, всякий алгорифм повинен бути результативним - закінчуватися породженням деякого слова. Всякий алгорифм будується за певною схемою, що складається з детермінованою послідовності дискретних (переривчастих) кроків, званих підстановками, на кожному з яких виходить нове слово в алфавіті А: Р] -> Q \, Рг -> Qi, ..., де Д, Qi - слова, побудовані з букв алфавіту А. Припустимо, дана підстановка СМ -> ГР. Якщо цю підстановку застосувати до слову СМОГ, виникне слово ГРОГ. Іншими словами, алгорифм - це припис, що дозволяє здійснити детермінований процес переробки слів. Кожна формула в конструктивній математиці Маркова символізується у вигляді впорядкованої пари (U, V) слів в алфавіті А. Слово U називається лівою частиною цієї формули, а V - се правою частиною. Серед формул деякі виділяються як заключних. У схемі алгорифма заключна формула записується у вигляді U - *? * V, а проміжна - у вигляді U -? V. Коли процес закінчується, то це називається застосуванням даного алгорифма до слова Ь \ взятому за вихідне. Результатом застосування алгорифма до слова U є слово Q, яке виходить на останньому кроці розпочатого нами процесу. алгорифм називається нормальним, якщо він представляє стандартне припис, що задається схемою підстановок і визначальне процес послідовного (крок за кроком) перетворення одного конструктивного об'єкта в інший конструктивний об'єкт. Формально нормальний алгорифм? задається трьома об'єктами: алфавітом А, схемою Z, що складається з деякої безлічі формул підстановок, і технічного трьохбуквені алфавіту що не входить в алфавіт А (і виконує функцію «знаків пунктуації» для відділення один від одного формул підстановок; знак у відокремлює один від одного формули підстановок, знаки а я fi-ліві частини формул від правих, вказуючи одночасно на тип формули підстановки: а у простих формул, /? - у заключних). При-нити нормальний алгорифм? до слова Р означає застосувати до Р схему алгорифма Z. Наприклад, схема yaabayacacayafiyaay в алфавіті а'с складається з чотирьох формул підстановок ababa, ас аса, а / 7, аа, які можуть бути також представлені таким чином: ab -? Ьа; ас -> са \ я-. *; -> а. Нормальний алгорифм? являє припис з побудови, починаючи з довільного слова Р в алфавіті А, послідовності слів Pi згідно з наступним правилом. Виберемо слово Р в якості першого члена Ро. Нехай для деякого і> 0 слово Р, побудовано, і процес побудови потрібної послідовності слів ще не завершився. Якщо в схемі нормального алгорифма? немає формул, ліві частини яких входили б до РІ, то Р, +1 думають рівним Pj, і процес побудови послідовності на цьому закінчується. Якщо ж у схемі? маються формули з лівими частинами, які входять в Д то в якості Р, + 1 береться результат підстановки правій частині першій з таких формул замість першого входження її лівій частині в слово Р,; при цьому процес; побудови послідовності вважається завершившимся, якщо застосована на цьому кроці формула підстановки була заключній, і триваючим в іншому випадку. Очевидно, що якщо приймається абстракція потенційної здійсненності, то процес побудови може продовжуватися як завгодно довго. І щодо його результату завжди можна з уве-тю сказати: процес завершено (потрібний об'єкт побудований) або процес не завершений (потрібний об'єкт ще не побудований). Для тих випадків, коли процес побудови не може бути завершений в кінцевий час, конструктивісти приймають наступне припущення {принцип Маркова) '19 : Якщо пропозиція про необмежену продолжаемості процесу застосування алгорифма Z до слова Р спростовано приведенням до безглуздості, то? застосуємо до Р. Іншими словами, якщо процес застосування алгорифма до деякого слову не є безмежно застосовним, то алгорифм застосуємо до цього слова. Звідки випливає, що даний об'єкт є конструктивним. Принцип Маркова радикально відрізняє конструктивну логіку від интуиционистской, так як вводить непрямий спосіб доведення твердження існування. Це не відповідає канонам интуиционистской логіки, в якій дозволяється доводити непрямим способом тільки заперечення суджень існування. Виправдовуючи даний принцип, Марков і Нагірний пишуть: «Ми не бачимо розумних підстав відкидати цей спосіб міркування, так як ніякого виходу за рамки конструктивного напряму при цьому не відбувається: абстракція актуальної нескінченності не застосовується, існування продовжує розумітися як потенційна здійсненність побудови. Якщо ми стверджуємо на підставі доведеною неможливості необмеженої продолжаемості детермінованого процесу, що цей процес закінчиться, то при цьому дається абсолютно певний спосіб побудови: продовжувати процес до його завершення. Та обставина, що при цьому число кроків процесу може не бути 'заздалегідь' обмеженим, нічого тут по суті не змінює. До того ж вимога, щоб це число було заздалегідь обмеженим, навряд чи може бути точно і об'єктивно сформульовано »86. Марков формулює принцип нормалізації, що зв'язує теорію нормальних алгорифм з відомими результатами Геде-ля, 2 \ Кліні87, Поста88, Тьюрінга89 і Черча90. алгорифм, застосовуваний до слів і званий вербальним, має більшою мірою спільності, ніж нормальний алгорифм. Постає питання: чи всякий вербальний алгоритм нормалізуємо, т. е . висловимо у вигляді нормального алгорифма? Позитивну відповідь на це питання так-ет принцип нормалізації: Всякий вербальний алгорифм в алфавіті А цілком еквівалентний відносно А певного нормальному алгорифм над А (всякий вербальний алгорифм нормалізуємо). Марков і Нагірний відзначають, що принцип нормалізації «представляє собою варіант тези Черча, що відноситься до нормальних алгорифм» 91. Теза Черча відноситься до так званих арифметичним функціям, для обчислення значень яких є які-небудь алгоритми і які прийнято називати вичіслімих. Буквально він говорить: «... Для кожної функції позитивних чисел, яка ефективно вичіслімих у щойно певному сенсі (тобто є рекурсивної функцією. - В. С), існує алгоритм обчислення її значень. Зворотно, при цьому ж визначенні ефективної вичіслімості вірно, що кожна функція, алгоритм обчислення значень якої відомий, ефективно вичіслімих »92. Значення принципу нормалізації полягає в наступному. Після того як у 30-і рр.. XX в. було розроблено безліч спеціальних видів алгоритмів, «для кожного з цих видів виникла впевненість у тому, що він з точністю до еквівалентності вичерпує всі алгорифм. Інакше кажучи, математики перейнялися переконанням у тому, що всякий алгорифм еквівалентний деякому алгорифм даного виду. Ця ідея стандартизації алгорифм лежить в основі їх сучасної теорії. Незабаром після того, як були вироблені перші стандартні поняття алгорифма, вдалося встановити, що всі запропоновані стандартизації в певному точному сенсі слова рівносильні один одному, і коли в подальшому були запропоновані деякі нові стандартизації, вони також виявилися рівносильними раніше визначеним. Тому при побудові загальної теорії алгорифм в кінцевому рахунку виявляється байдужим, який саме їх стандартизацією користуватися. Ми будемо використовувати найбільш звичні нам 'нормальні алгорифм' »93. Слова в заданому алфавіті визначаються як можливі результати здійснення процесів побудови. Тому судження класичної математики виду «Існує слово, що задовольняє умові ф» визнається конструктивістів неточним і замінюється таким конструктивним судженням: «Потенційно здійсненно побудова слова, що задовольняє умові ф» або «Слово, що задовольняє умові ф, є конструктивним математичним об'єктом». Різниця між класичним і конструктивистским судженнями існування полягає в тому, що з докази «класичного» судження існування не завжди слід істинність «конструктивного»: перше може бути істинним, але друге проте хибним. Абстракція потенційної здійсненності як головна ідеалізація конструктивної математики допускає не тільки практично здійсненне в даних матеріальних умов побудова, а й потенційно здійсненне побудова, тобто здійсненне в припущенні, що після кожного кроку процесу побудови необхідного слова завжди можливо виконати наступний крок. В цілому до конструктивного напряму в математиці відносяться всі дослідження, що задовольняють наступним условіям94: (1) в якості об'єктів вивчення (об'єктів суджень) фігурують тільки конструктивні об'єкти, що представляють собою слова деякого алфавіту; (2) при розгляді конструктивних об'єктів допускається абстракція потенційної здійсненності і виключається застосування абстракції актуальної нескінченності; (3) використовується особлива конструктивна логіка і виключаються всі докази, засновані на законі виключеного третього. Нехай приписування вертикальної «рисочки» праворуч від даного натурального числа позначає нове натуральне число, відмінне від нього на одиницю. Тоді алфавіту А = {0, |} достатньо для породження ряду натуральних чисел згідно з такими правилами: - 0 є натуральне число. - Якщо п - натуральне число, слово п | також є натуральне число. Згідно із зазначеним алгорифм, для отримання нового натурального числа досить приписати праворуч до даного вертикальну риску. Таким чином, натуральними числами є слова 0 (нуль), 0 | (одиниця), 011 (два), 0 (11 (три), ... Для визначення раціональних чисел алфавіт А = {0, |} досить розширити, включивши в нього додаткові слова (коса риса відокремлює чисельник від знаменника, знак «-» позначає «мінус»): А = {О, |, /, -}: Про | / 01 j | (одна третина); - О | / 011} (мінус одна третина). Для визначення дійсних чисел будується алгоритмічна інтерпретація критерію збіжності Коші, за допомогою якого Кантор будував теоретико-множинне визначення дійсних чисел. Згідно Кантору, всяка послідовність раціональних чисел, що виконує критерій збіжності Коші, визначає деяке дійсне число. Іншими словами, для даного значення дробу \ / к, як би вона не була мала, завжди знайдеться п-й член послідовності, за яким будь-які два члени послідовності відрізняються один від одного менше, ніж на Ilk. Дійсне число в теоретико-множині сенсі визначається як безліч всіх еквівалентних послідовностей Коші. Нормальний алгорифм? в розширеному алфавіті називається конструктивною послідовністю раціональних чисел, якщо він застосовний до всякого натуральному числу і переробляє його в деяке раціональне число. Число? (W), де N - довільне натуральне число, називається jV-м членом послідовності?. Нехай? - Конструктивна послідовність раціональних чисел. Конструктивна послідовність натуральних чисел 0 називається регулятором збіжності послідовності?, Якщо для будь-яких натуральних чисел L, М і N з М, N> 0 (?) Випливає, що Конструктивне дійсне число є всяке слово виду? 0, де? - Конструктивна послідовність раціональних чисел, © - її регулятор сходімості95. Таким чином, для побудови дійсного числа потрібно два алгорифма. Перший - для завдання послідовності раціональних чисел? (JV), другий - для доказу можливості побудови числа © (Л7) по даному натуральному числу L. Головний результат теорії алгорифм Маркова полягає в наступному: існує перечислимого, але не можна розв'язати безліч слів. Таким безліччю, наприклад, є безліч натуральних чисел. У алгоритмічних термінах даний результат звучить так: «Може бути побудований нормальний алгорифм? в алфавіті А, задовольняє наступній умові: неможливий нормальний алгорифм над А, застосовний до всякого слову в А і переробний в порожнє слово ті і тільки ті слова в А, до яких застосовується »96. Наведена теорема стверджує, що для деякого конкретного нормального алгорифма? в Л проблема розпізнавання застосовності (незастосовності) до слів в А нерозв'язна: шуканий в цій проблемі нормальний алгорифм неможливий. Результат Маркова відповідає аналогічним негативним доказам А. Тьюринга і А. Черча, отриманим раніше (в 1936 р.). Деякі пояснення до основної теоремі Маркова дають такі визначення і результати. ? Безліч М слів в алфавіті А називається розв'язаним в А, якщо існує нормальний алгорифм? над А, перевіряючий приналежність слів в А до М. ? Безліч М слів в алфавіті А називається перелічуваних, якщо існує алгорифм? над А такий, що для будь-якого слова Р в А 1 {Р) визначено тоді і тільки тоді, коли Ре М. ? Усяке розв'язати безліч слів є перелічуваних. ? Існує перечислимого, але не можна розв'язати безліч слів в алфавіті. тивная, як і интуиционистская, математика має справу з рахунковими, хоча і неперечіслймимі множинами. Реалізація школою Маркова програми обгрунтування математики привела до результатів, схожим, хоча й не в усьому, отриманим раніше школою Брауера. Радикально змінилося поняття функції. Було доведено, що монотонно зростаюча і обмежена зверху послідовність конструктивно дійсних чисел може не мати межі, що суперечить одному з основних положень класичного аналізу. Було також доведено, що конструктивна функція дійсно змінного не може мати конструктивного розриву ні в одній точці і, крім того, вона завжди безперервна. Разом з цими результатами стало ясно видно, що «ніякого спрощення теорії не виходить. Навпаки, дослідження конструктивних аналогів навіть вельми елементарних теорій звичайного аналізу зажадало великих зусиль і рідкісної винахідливості. Що ж до відділів аналізу, що стосуються найбільш абстрактних властивостей банахових, Гільбертових і топологічних просторів, то тут найчастіше не вдається побудувати конструктивних аналогів з причин великих технічних труднощів. Коротше кажучи, конструктивний аналіз як по необхідному для його осмислення розумової напруги, так і по громіздкість застосовуваного апарату виявляється не більш простим предметом, ніж класичний аналіз, а, мабуть, навіть більш складним ... »97. Що ж може тоді змусити математика пожертвувати простотою методів класичної математики і віддати перевагу їм методи конструктивної? Конструктивісти одностайно відповідають: тільки надійність алгоріфміческіх міркувань дозволяє підвести під математику міцний фундамент. Однак труднощі конструктивного аналізу, про які говорять все частіше і частіше, залишають питання про перспективи розвитку конструктивної математики, її відносин з класичної та интуиционистской, багато в чому відкритими. Нова версія конструктивізму, незалежна від інтуїционізма Брауера, конструктивізму Маркова, покликана врятувати класичну математику, пов'язана з ім'ям американського математика Еррет Бі- шопа (1928-1983) 98. У першому розділі свого монументальної праці «Конструктивний аналіз», названої «конструктивістських маніфестом», Бішоп формулює основні положення нового бачення математики в послебрауеровскую і послегільбертовскую епоху99. Математика, вважає Бішоп, - вільне створення нашого розуму, представляє ту частину інтелектуальної діяльності, яка перевершує нашу біологію і наше фізичне оточення і яка все ж менш довільна, ніж будь-яка друга наука. Математика має властивість трансцендентності. Ця властивість пояснює нашу впевненість у тому, що створення, що живуть в інших світах, користуються тією ж математикою, що й ми. Первинний об'єкт математики - натуральне число. Ми осягаємо число тим же способом, яким, згідно Канту, сприймається простір. Існування натуральних чисел разом з арифметикою обумовлено природою нашого інтелекту і, можливо, розуму як такого. Теорія натуральних чисел створюється з понять одиниці, додавання одиниці і принципу повної індукції. Всі інші «поверхи» математики будуються за допомогою послідовного сходження від базисної теорії натуральних чисел. Таким способом створюється велика частина математики. Але існує й інший спосіб «трансценденції математики». Можна сходити від фактично сконструйованого об'єкта до нового, гіпотетичному за своєю суттю. Так, можна вводити гіпотетичні множини з гіпотетичними операціями на них, що виконують певні аксіоми. Виправданням такого способу побудови математики стає можливість вирішення конкретних математичних проблем, виражених в термінах натуральних чисел. Гіпотетичні об'єкти можна будувати на підставі інших гіпотетичних об'єктів, тобто можлива ієрархія гіпотетичних конструкцій. Який би висоти не було всю будівлю, його підставою служить натуральний ряд чисел. Значить, будь-яка математична проблема при такій побудові отримує надійний обчислювальний базис. На 70-і рр.. минулого сторіччя припала нова хвиля інтересу до конструктивної математики. Виник своєрідний ренесанс конструктивізму. «Існують дві принципові причини цього ренесансу: Бішоп і комп'ютер. У 60-ті тт. комп'ютер використовувався для чисельного вирішення певних математичних проблем, найбільш вражаючою з яких можна назвати розрахунок орбіт для космічних кораблів. Це викликало значний прогрес у розвитку методів чисельного аналізу і чисельної алгебри, були побудовані необхідні алгорифм і досліджено їх застосування. Поширення цих методів і алгорифм на інші області і проблеми породило несподіваний інтерес до того способу розв'язання математичної проблеми, який пов'язаний з її обчисленням. Неминучим результатом всього цього стало переосмислення проблеми, щодо якої сперечалися Брауер і Гільберт. Воно було зроблено Еррет Бішопом з Каліфорнії ... Головним вражаючим відкриттям Бішопа стало доказ, що як Гільберт, так і Брауер помилялися саме в тому пункті, щодо якого у них не було розбіжностей. А саме, вони обидва припускали, що якщо прийняти конструктивну (інтуіціоністскую. - BC) математику серйозно, то необхідно буде 'відмовитися' від найважливіших частин сучасної математики (таких, наприклад, як теорія міри або комплексний аналіз). Бішоп довів, що це було звичайним помилкою і що не було ніякої необхідності вводити екстравагантні допущення, що здаються суперечливими усім необізнаним. Що тривав довгий час конфлікт між потужністю і безпекою математичного мислення був насправді ілюзорним! .. Бішоп знайшов спосіб представити математику як 'мова високого рівня програмування', в якому слід записувати докази. Кожний доказ існування має супроводжуватися побудовою алгорифма »100. Таким чином, новим пріоритетом, який надихає сучасних конструктивістів, служить розкриття фундаментальної зв'язку теоретичної математики з обчислювальними процедурами і програмуванням в цілому. Комп'ютер стає реальним засобом конструювання нових математичних об'єктів і умовою розвитку самої математики. Потен- альна нескінченність постає як можливість обчислення в принципі. При цьому базисної структурою математики визнається ряд натуральних чисел, всі інші структури розглядаються як гіпотетичні. Таким чином, мрія раціоналістів створити небудь універсальна мова для заміни природних міркувань точними обчислювальними процедурами набула в наш час форму респектабельної метаматематичних програми конструктивізму.
|
||
« Попередня | Наступна » | |
|
||
Інформація, релевантна "Конструктивна математика Маркова і Бішопа" |
||
|