Алгоритмическая неразрешимость
Алгоритмическая разрешимость — свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем важнейшим случаем более общей проблемы разрешимости.
История вопроса и предпосылки
Понятия алгоритма и аксиоматической системы имеют давнюю историю. И то и другое известно ещё со времён античности. Достаточно вспомнить постулаты геометрии Евклида и алгоритм нахождения наибольшего общего делителя того же Евклида. Несмотря на это, чёткого математического определения исчисления и особенно алгоритма не существовало очень долгое время. Особенность проблемы, связанной с формальным определением неразрешимости состояла в том, что для того, чтобы показать, что некоторый алгоритм существует, достаточно его просто найти и продемонстрировать. Если же алгоритм не находится, возможно его не существует и это тогда требуется строго доказать. А для этого нужно точно знать, что такое алгоритм.
Большой прогресс в формализации этих понятий был достигнут в начале XX века Гильбертом и его школой. Тогда, сначала, сформировались понятия исчисления и формального вывода, а затем Гильбертом же, в его знаменитой программе обоснования математики была поставлена амбициозная цель формализации всей математики. Программа предусматривала, в том числе, возможность автоматической проверки любой математической формулы на предмет истинности. Отталкиваясь от работ Гильберта Гёдель впервые описал класс так называемых рекурсивных функций, с помощью которой доказал свои знаменитые теоремы о неполноте. Впоследствии был введён ряд других формализмов, таких как машина Тьюринга, λ-исчисление, оказавшихся эквивалентными рекурсивным функциям. В настоящее время каждый из них считается формальным эквивалентом интуитивного понятия вычислимой функции. Эта эквивалентность постулируется тезисом Чёрча.
Когда понятия исчисления и алгоритма были уточнены, последовал ряд результатов о неразрешимости различных теорий. Одним из первых таких результатов была теорема, доказанная Новиковым, о неразрешимости проблемы слов в группах. Разрешимые же теории были известны задолго до этого.
Интуитивно понятно, что чем сложнее и выразительнее теория, тем больше шансов, что она окажется неразрешимой. Поэтому, грубо говоря, «неразрешимая теория» — «сложная теория».
Общие сведения
Формальное исчисление в общем случае должно определять язык, правила построения термов и формул, аксиомы и правила вывода. Таким образом, для каждой теоремы T всегда можно построить цепочку A1, A2, … , An=T, где каждая формула Ai либо является аксиомой, либо выводима из предыдущих формул по одному из правил вывода. Разрешимость означает, что существует алгоритм, который для каждого правильно построенного предложения T за конечное время выдаёт однозначный ответ: да, данное предложение выводимо в рамках исчисления или нет — оно невыводимо.
Очевидно, что противоречивая теория разрешима, так как любая формула будет выводимой. С другой стороны, если исчисление не обладает рекурсивно перечислимым множеством аксиом, как например, логика второго порядка, оно, очевидно, не может быть разрешимым.
Примеры разрешимых теорий
Это пустой раздел, который еще не написан. |
Примеры неразрешимых теорий
Это пустой раздел, который еще не написан. |
Полуразрешимость и автоматическое доказательство
Разрешимость — очень сильное свойство, и большинство полезных и используемых на практике теорий им не обладают. В связи с этим было введено более слабое понятие полуразрешимости. Полуразрешимость означает наличие алгоритма, который за конечное время всегда подтвердит, что предложение истинно, если это действительно так, но если нет — может работать бесконечно.
Требование полуразрешимости эквивалентно возможности эффективно перечислить все теоремы данной теории. Иными словами, множество теорем должно быть рекурсивно-перечислимым. Большинство используемых на практике теорий удовлетворяют этому требованию.
Большое практическое значение имеют эффективные полуразрешающие процедуры для логики первого порядка, так как они позволяют (полу)автоматически доказывать формализованные утверждения очень широкого класса. Прорывом в этой области было открытие Робинсоном в 1965 году метода резолюций.
Связь разрешимости и полноты
В математической логике традиционно используется два понятия полноты: собственно полнота и полнота относительно некоторого класса интерпретаций (или структур). В первом случае, теория полна, если любое предложение в ней является либо истинным, либо ложным. Во втором — если любое предложение, истинное при всех интерпретациях из данного класса, выводимо.
Оба понятия тесно связаны с разрешимостью. Например, если множество аксиом полной теории первого порядка рекурсивно перечислимо, то она разрешима. Это следует из известной теоремы Поста, утверждающей, что если множество и его дополнение оба рекурсивно перечислимы, то они также разрешимы. Интуитивно, аргумент, показывающий истинность приведённого утверждения, следующий: если теория полна, и множество её аксиом рекурсивно перечислимо, то существуют полуразрешающие процедуры для проверки истинности любого утверждения, равно как и его отрицания. Если запустить обе эти процедуры параллельно, то учитывая полноту теории, одна из них должна когда-нибудь остановиться и выдать позитивный ответ.
Если теория полна относительно некоторого класса интерпретаций, это можно использовать для построения разрешающей процедуры. Например пропозициональная логика полна относительно интерпретации на таблицах истинности. Поэтому построение таблицы истинности по данной формуле будет примером разрешающего алгоритма для пропозициональной логики.
См. также
- Полнота формальной системы
- Непротиворечивость
- Тезис Чёрча — Тьюринга
- Вычислимая функция
- Разрешимое множество
- Алгоритмически неразрешимая задача
- Трансвычислительная задача
Литература
- Мальцев А. И. . Алгоритмы и рекурсивные функции. — М.: Наука, 1986.
- Ackermann, Wilhelm. Solvable cases of the decision problem. — Amsterdam: North-Holland Publishing, 1954.
- Handbook of Automated Reasoning (in 2 volumes) / John Alan Robinson, Andrei Voronkov. — Elsevier and MIT Press, 2001. — ISBN 0-262-18223-8.
У этой статьи есть несколько проблем, помогите их исправить: |
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Алгоритмическая неразрешимость, Что такое Алгоритмическая неразрешимость? Что означает Алгоритмическая неразрешимость?
Algoritmicheskaya razreshimost svojstvo formalnoj teorii obladat algoritmom opredelyayushim po dannoj formule vyvodima ona iz mnozhestva aksiom dannoj teorii ili net Teoriya nazyvaetsya razreshimoj esli takoj algoritm sushestvuet i nerazreshimoj v protivnom sluchae Vopros o vyvodimosti v formalnoj teorii yavlyaetsya chastnym no vmeste s tem vazhnejshim sluchaem bolee obshej problemy razreshimosti Istoriya voprosa i predposylkiPonyatiya algoritma i aksiomaticheskoj sistemy imeyut davnyuyu istoriyu I to i drugoe izvestno eshyo so vremyon antichnosti Dostatochno vspomnit postulaty geometrii Evklida i algoritm nahozhdeniya naibolshego obshego delitelya togo zhe Evklida Nesmotrya na eto chyotkogo matematicheskogo opredeleniya ischisleniya i osobenno algoritma ne sushestvovalo ochen dolgoe vremya Osobennost problemy svyazannoj s formalnym opredeleniem nerazreshimosti sostoyala v tom chto dlya togo chtoby pokazat chto nekotoryj algoritm sushestvuet dostatochno ego prosto najti i prodemonstrirovat Esli zhe algoritm ne nahoditsya vozmozhno ego ne sushestvuet i eto togda trebuetsya strogo dokazat A dlya etogo nuzhno tochno znat chto takoe algoritm Bolshoj progress v formalizacii etih ponyatij byl dostignut v nachale XX veka Gilbertom i ego shkoloj Togda snachala sformirovalis ponyatiya ischisleniya i formalnogo vyvoda a zatem Gilbertom zhe v ego znamenitoj programme obosnovaniya matematiki byla postavlena ambicioznaya cel formalizacii vsej matematiki Programma predusmatrivala v tom chisle vozmozhnost avtomaticheskoj proverki lyuboj matematicheskoj formuly na predmet istinnosti Ottalkivayas ot rabot Gilberta Gyodel vpervye opisal klass tak nazyvaemyh rekursivnyh funkcij s pomoshyu kotoroj dokazal svoi znamenitye teoremy o nepolnote Vposledstvii byl vvedyon ryad drugih formalizmov takih kak mashina Tyuringa l ischislenie okazavshihsya ekvivalentnymi rekursivnym funkciyam V nastoyashee vremya kazhdyj iz nih schitaetsya formalnym ekvivalentom intuitivnogo ponyatiya vychislimoj funkcii Eta ekvivalentnost postuliruetsya tezisom Chyorcha Kogda ponyatiya ischisleniya i algoritma byli utochneny posledoval ryad rezultatov o nerazreshimosti razlichnyh teorij Odnim iz pervyh takih rezultatov byla teorema dokazannaya Novikovym o nerazreshimosti problemy slov v gruppah Razreshimye zhe teorii byli izvestny zadolgo do etogo Intuitivno ponyatno chto chem slozhnee i vyrazitelnee teoriya tem bolshe shansov chto ona okazhetsya nerazreshimoj Poetomu grubo govorya nerazreshimaya teoriya slozhnaya teoriya Obshie svedeniyaFormalnoe ischislenie v obshem sluchae dolzhno opredelyat yazyk pravila postroeniya termov i formul aksiomy i pravila vyvoda Takim obrazom dlya kazhdoj teoremy T vsegda mozhno postroit cepochku A1 A2 An T gde kazhdaya formula Ai libo yavlyaetsya aksiomoj libo vyvodima iz predydushih formul po odnomu iz pravil vyvoda Razreshimost oznachaet chto sushestvuet algoritm kotoryj dlya kazhdogo pravilno postroennogo predlozheniya T za konechnoe vremya vydayot odnoznachnyj otvet da dannoe predlozhenie vyvodimo v ramkah ischisleniya ili net ono nevyvodimo Ochevidno chto protivorechivaya teoriya razreshima tak kak lyubaya formula budet vyvodimoj S drugoj storony esli ischislenie ne obladaet rekursivno perechislimym mnozhestvom aksiom kak naprimer logika vtorogo poryadka ono ochevidno ne mozhet byt razreshimym Primery razreshimyh teorij Eto pustoj razdel kotoryj eshe ne napisan Zdes mozhet raspolagatsya otdelnyj razdel Pomogite Vikipedii napisav ego 31 yanvarya 2017 Primery nerazreshimyh teorij Sm takzhe Algoritmicheski nerazreshimaya zadacha Eto pustoj razdel kotoryj eshe ne napisan Zdes mozhet raspolagatsya otdelnyj razdel Pomogite Vikipedii napisav ego 31 yanvarya 2017 Polurazreshimost i avtomaticheskoe dokazatelstvoRazreshimost ochen silnoe svojstvo i bolshinstvo poleznyh i ispolzuemyh na praktike teorij im ne obladayut V svyazi s etim bylo vvedeno bolee slaboe ponyatie polurazreshimosti Polurazreshimost oznachaet nalichie algoritma kotoryj za konechnoe vremya vsegda podtverdit chto predlozhenie istinno esli eto dejstvitelno tak no esli net mozhet rabotat beskonechno Trebovanie polurazreshimosti ekvivalentno vozmozhnosti effektivno perechislit vse teoremy dannoj teorii Inymi slovami mnozhestvo teorem dolzhno byt rekursivno perechislimym Bolshinstvo ispolzuemyh na praktike teorij udovletvoryayut etomu trebovaniyu Bolshoe prakticheskoe znachenie imeyut effektivnye polurazreshayushie procedury dlya logiki pervogo poryadka tak kak oni pozvolyayut polu avtomaticheski dokazyvat formalizovannye utverzhdeniya ochen shirokogo klassa Proryvom v etoj oblasti bylo otkrytie Robinsonom v 1965 godu metoda rezolyucij Svyaz razreshimosti i polnotyV matematicheskoj logike tradicionno ispolzuetsya dva ponyatiya polnoty sobstvenno polnota i polnota otnositelno nekotorogo klassa interpretacij ili struktur V pervom sluchae teoriya polna esli lyuboe predlozhenie v nej yavlyaetsya libo istinnym libo lozhnym Vo vtorom esli lyuboe predlozhenie istinnoe pri vseh interpretaciyah iz dannogo klassa vyvodimo Oba ponyatiya tesno svyazany s razreshimostyu Naprimer esli mnozhestvo aksiom polnoj teorii pervogo poryadka rekursivno perechislimo to ona razreshima Eto sleduet iz izvestnoj teoremy Posta utverzhdayushej chto esli mnozhestvo i ego dopolnenie oba rekursivno perechislimy to oni takzhe razreshimy Intuitivno argument pokazyvayushij istinnost privedyonnogo utverzhdeniya sleduyushij esli teoriya polna i mnozhestvo eyo aksiom rekursivno perechislimo to sushestvuyut polurazreshayushie procedury dlya proverki istinnosti lyubogo utverzhdeniya ravno kak i ego otricaniya Esli zapustit obe eti procedury parallelno to uchityvaya polnotu teorii odna iz nih dolzhna kogda nibud ostanovitsya i vydat pozitivnyj otvet Esli teoriya polna otnositelno nekotorogo klassa interpretacij eto mozhno ispolzovat dlya postroeniya razreshayushej procedury Naprimer propozicionalnaya logika polna otnositelno interpretacii na tablicah istinnosti Poetomu postroenie tablicy istinnosti po dannoj formule budet primerom razreshayushego algoritma dlya propozicionalnoj logiki Sm takzhePolnota formalnoj sistemy Neprotivorechivost Tezis Chyorcha Tyuringa Vychislimaya funkciya Razreshimoe mnozhestvo Algoritmicheski nerazreshimaya zadacha Transvychislitelnaya zadachaLiteraturaMalcev A I Algoritmy i rekursivnye funkcii M Nauka 1986 Ackermann Wilhelm Solvable cases of the decision problem Amsterdam North Holland Publishing 1954 Handbook of Automated Reasoning in 2 volumes John Alan Robinson Andrei Voronkov Elsevier and MIT Press 2001 ISBN 0 262 18223 8 U etoj stati est neskolko problem pomogite ih ispravit V state est spisok istochnikov no ne hvataet snosok Bez snosok slozhno opredelit iz kakogo istochnika vzyato kazhdoe otdelnoe utverzhdenie Vy mozhete uluchshit statyu prostaviv snoski na istochniki podtverzhdayushie informaciyu Svedeniya bez snosok mogut byt udaleny 18 maya 2014 Pozhalujsta posle ispravleniya problemy isklyuchite eyo iz spiska parametrov Posle ustraneniya vseh nedostatkov etot shablon mozhet byt udalyon lyubym uchastnikom
