Тезис Гьоделя.
Теорему Черча

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Тезис Гьоделя. Теорему Черча

Реферат із дисципліни «Теорія алгоритмів та представлення знань»

Виконав студент 3-го курсу 36 групи Левицький Е. Г.

Європейський Університет

Уманська філія

Кафедра математики та інформатики

Умань — 2005

Вступ

Введение поняття машини Тьюринга уточнює поняття алгоритму і вказує шлях розв’язання якийсь масової проблеми. Проте машина Тьюринга буває неприйнятна до початковій інформації (вихідному слову алфавіту). Така ситуація повторюється щодо деяких завдань, на вирішення яких немає вдається створити машини Тьюринга. Одне з перших результатів подібного типу отримано Черчем в 1936 року. Він стосується проблеми розпізнавання выводимости в математичної логике.

1). Аксіоматичний метод у математиці у тому, що це теореми даної теорії виходять у вигляді формально-логічного виведення з кількох аксіом, прийнятих у даної теорії без доказів. Наприклад, в математичної логіці описується спеціальну мову формул, дозволяє будь-яке пропозицію математичної теорії записати як цілком певної формули, а процес логічного висновку з посилки слідства може бути описаний як процесу формальних перетворень вихідної формули. Це досягається шляхом застосування логічного обчислення, у якому зазначена система допустимих перетворень, що зображують елементарні акти логічного умовиводи, у тому числі складається будь-який, як завгодно складний формально-логічна вывод.

Вопрос про логічного выводимости слідства з посилки є політичним питанням про існування дедуктивної ланцюжка, провідною від формули до формули . У зв’язку з цим виникають проблеми розпізнавання выводимости: може бути обох формул і дедуктивна ланцюжок, провідна від до чи ні. Вирішення проблеми розуміється в сенсі питання про існування алгоритму, що дає відповідь за будь-яких і . Черчем ця проблема було вирішено отрицательно.

Теорема Черча. Проблема розпізнавання выводимости алгоритмічно неразрешима.

Проблема розпізнавання самоприменимости. Це друга проблема, позитивного рішення якої знайдено досі. Її суть ось у чому. Програму машини Тьюринга можна закодувати будь-яким певним шифром. На стрічці машини можна зобразити його ж власний шифр, записаний у алфавіті машини. Тут фокусуються як у разі звичайній програми можливі два случая:

1. машина застосовна до свого шифру, тобто вони переробляє цей шифр і після кінцевого числа тактів останавливается;

2. машина неприйнятна до свого шифру, тобто машина будь-коли перетворюється на стоп — состояние.

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

Теорема 2. Проблема розпізнавання самоприменимости алгоритмічно нерозв’язна.

3). Проблема еквівалентності слів для асоціативних исчислений.

Рассмотрим певний алфавіт і безліч слів у тому алфавіті. Будемо розглядати перетворення одних слів до інших з допомогою деяких допустимих підстановок , де і два слова у тому алфавіті Якщо слово містить як подслово, наприклад , можливі такі подстановк , , .

Ассоциативным обчисленням називається сукупність всіх слів у певному алфавіті разом із який-небудь кінцевої системою допустимих підстановок. Для завдання асоціативного обчислення досить буде задати відповідний алфавіт і системи подстановок.

Если слово то, можливо перетворено на слово шляхом однократного застосування певної підстановки, то і називаються суміжними словами. Послідовність слів таких, кожна пара слів є суміжними, називається дедуктивної ланцюжком, провідною від слова до речі . Якщо існує ланцюжок, провідна від слова до речі , то і називаються еквівалентними: ~.

Для кожного асоціативного обчислення виникає своя спеціальна проблема еквівалентності слів: для будь-яких двох слів у цьому обчисленні потрібно дізнатися еквівалентні вони або нет.

Теорема 3. Проблема еквівалентності слів у кожному асоціативному обчисленні алгоритмічно нерозв’язна.

Эта проблему Чечні вирішено лише деяких асоціативних численнях спеціального вида.

Математические теории.

Аксиоматические теорії діляться на формальні й неформальні. Неформальні аксіоматичні теорії наповнені теоретико — множинним змістом, поняття выводимости в них досить розпливчасте й у значною мірою спирається на здоровий смысл.

Формальная аксиоматическая теорія вважається певної, якщо виконані такі условия:

задан мову теории;

определено поняття формули у цій теории;

выделено безліч аксіом теории;

определены правила виведення у цій теории.

Среди математичних теорій виділяються теорії першого порядку. Ці теорії не допускають у своїй викладі предикати, які мають у своєму за аргументи інші предикати і функції. З іншого боку, не допускаються кванторные операції з предикатам і функцій. Теорії першого порядку називаються ще елементарними теориями.

1). Мова теорії першого порядку. Розглянемо певний алфавіт теорії Безліч слів цього алфавіту називається безліччю висловів теорії Кілька , що складається з алфавіту і багатьох висловів, називають мовою теории.

В алфавіт будь-якої теорії першого порядку входят:

символы логічних операцій

символы кванторных операцій

вспомогательные символи — дужки і коми;

конечное чи рахункове безліч — місцевих предикатных букв;

конечное чи рахункове безліч функціональних букв;

конечное чи рахункове безліч предметних констант.

В частковості під функціональної буквою можна розуміти ланцюжок логічних операцій.

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

Различные теорії першого порядку можуть бути різні друг від друга за складом літер у алфавите.

Термы і формулы.

В будь-який теорії важливе значення має визначення терма і формули. Фактично, це два класу слів множества.

Термом називається: а). предметна змінна і змінна константа;

Таким чином, крім предметних змінних і констант термами є ланцюжка, освічені з предметних змінних і констант у вигляді символів операций.

Примеры теорій першого порядку.

1). Геометрія (теорія рівності відрізків).

Логические аксіоми цієї теорії самі п’ять, що згадані вище. Первинні терміни  — безліч всіх відрізків і = - ставлення равенства.

2). Аксиоматическая теорія натуральних чисел.

Аксиоматическое побудова арифметики натуральних чисел пов’язані з іменами Пеано і Дедекинда. Мова теорії містить константу 0, числові перемінні, символ рівності, функціональні символи +,., (поповнення одиниці) і логічні зв’язки, тобто. Терми будуються з константи 0 і змінних з допомогою функціональних символів. Зокрема натуральні числа зображуються термами виду 0.

Элементарные формули у цій теорії - це рівності термов, інші формули виходять з елементарних з допомогою логічних зв’язок. Запроваджується одна предикатная літера і трьох функціональних буквы.

— ставлення рівності, — ставлення прямування (поповнення одиниці), — операція суми, — операція твори. Як спеціальних аксіом теорії натуральних чисел беруться такі аксиомы:

где — довільна формула теорії натуральних чисел. Дев’ята аксіома називається принципом математичної індукції. Аксіоми 1−2 забезпечують очевидні властивості рівності, аксіоми 5−8 уточнюють властивості операцій складання і умножения.

Для довільних теорій першого порядку теорема дедукції, доведена нами в обчисленні висловлювань, вимагає зміни. У початковому вигляді, причому ніяких обмежень на предметні перемінні, що входять до, не накладалося. Для справедливості теореми дедукції для довільних теорій першого порядку треба її змінити наступним образом.

Теорема Геделя про неповноті. У будь-якій несуперечливої формальної системі, що містить мінімум арифметики, отже, й у теорії натуральних чисел, знайдеться формально нерозв’язне судження, тобто така замкнута формула , що , ні є виведеними в системе.

Пусть ми маємо якась формальна система T, тобто. якийсь набір аксіом, з яких ми, користуючись фіксованих набором правил переходу і общелогических аксіом, можемо доводити якісь теореми. Поставимо забезпечити виконання умов: нехай, по-перше, наша система T буде сформульовано мовою арифметики. Це означає, що формули аксіом і теорем в T, крім общелогических символів (як-от перемінні, дужки,? «і «, «не- «й інші логічні операції, знак рівності =, і навіть кванторы існування? і загальності ?) можуть утримувати такі символи, як 0 (константа), + (бінарна операція), * (ще одна операція), < (ставлення «менше, ніж »), S (x) (функція, що означає «наступний за x елемент », тобто. x+1). По-друге, нехай система T буде на досить потужній, що в разі отже, що вона вміє доводити деякі досить прості формули відносин між натуральними числами (подробиці я пропускаю). Наприклад, коли ми не внесемо узагалі немає жодних аксіом в T, вона нічого нетривіального зможе довести, тобто. не вистачить потужної і теорема Гёделя до неї ставитися не буде. Але кожен досить повний перелік аксіом арифметики (наприклад, капітуляційний звичайні тривіальні властивості операцій множення і складання, відносини < і функції S (x)) вистачає потужним нашим цілей. По-третє, система T маєш бути у деякому технічному сенсі «легко описуваної «- у ній має бути чи кінцеве кількість аксіом, або нескінченне, але описуване з допомогою якогось заздалегідь відомого алгоритму. Будь-яку формальну систему, відповідальну цим трьом умовам, назвемо підходящої (це стандартна термінологія, просто для зручності лише у цього запису). З погляду формальних доказів система T немає «семантики », інакше кажучи, сенс які у ній символів нам байдужий. Формальне доказ є лише деяка довга ланцюжок рядків, де кожна рядок є аксіома T, общелогическая аксіома, чи отримана з попередніх рядків застосуванням однієї з дозволених правил переходу. Ми позначили, скажімо, жодну з операцій мови арифметики символом *, вона відповідає нашому розумінню множення; але з погляду формальної системи T * - лише символ, нічого значить. Замість нього могла бути будь-який інший символ, скажімо, %, і всі докази залишалися в силі; просто якщо б ми захотіли визначити сенс аксіом чи доказуваних нами теорем, ми мусили б розуміти % як «множення ».

Сказать, що якийсь твердження доказово в T — отже сказати, що є певна формальне доказ, який до нього наводить. Доказуемость — синтаксичне властивість, а чи не семантична. З іншого боку, сказати, що якесь істинне — отже, сказати, коли ми інтерпретуємо його відповідно до звичайній інтерпретації символів T (тобто. * усвідомимо як «множення », символ 0 — і кількість 0, итп.), то отримуємо справжнє твердження про натуральних числах.

Доказуемость необов’язково влечёт істинність. Припустимо для простоти, що кожного натурального числа n у нашій мові є константа n, що дозволяє «говорити «про кількість n в формулах нашої мови (практично ми можемо «симулювати «такі константи, не оголошуючи їх, з допомогою ланцюжка термінів: 0, S (0), S (S (0)), S (S (S (0))) итп.). Тепер візьмемо формальну систему T, яка має наступна аксіома: 2+2=5. Тоді твердження «2+2=5 «доказово у системі T (т.к. воно є аксіомою), але, природно, брехливо (бреше твердженням про натуральних числах). Є формальні системи, які доводять лише істинні затвердження. Такі системи, де всі аксіоми — істинні затвердження (можна довести, що всі правила переходу між аксіомами зберігають істинність). Такі формальні системи називаються коректними. Формальна система називається консистентної, якщо вона може довести одночасно якесь затвердження Кабміном і його заперечення, тобто. довести протиріччя. Неконсистентная формальна система — це погано й практично марно, т.к. можна легко показати, що з докази протиріччя можна було одержати доказ будь-чого. Неконсистентная формальна система доводить взагалі будь-яке твердження, отже нічого цікавого у ній немає. Якщо цю систему коректна, вона автоматично консистентна: вона ж доводить лише істинні затвердження, а якесь затвердження Кабміном і його заперечення що неспроможні одночасно бути істинними: одне з яких буде істинним, а інше хибним. Зауважимо, проте — це! — що «консистентность », як і «доказуемость «є властивість синтаксичне, яке залежить від змісту формул та його інтерпретації; тоді як коректність системи є властивість семантична, яка потребує поняття «істинності «. Нарешті, формальна система називається повної, для будь-якого затвердження? вони можуть довести або ?, або? («не-? »). Доказ? називається також спростуванням ?; в такий спосіб, повна система може або довести, або спростувати любою твердження. У певному сенсі вона «всі запитання дає відповідь «. Що скажеш про натуральні числа — вона зможе або довести це, або спростувати. Це властивість повноти — теж синтаксичне, не яке користується поняттям «істинності «.

Теперь ми можемо визначити три формулювання теореми Гёделя про неповноті наступним чином: 1. Нехай T — «підходяща «(див. вище) формальна система, і припустимо також, що T — коректна система. Тоді безліч тверджень, які T може довести, і безліч істинних тверджень не збігаються (а так й усе доказові з допомогою T затвердження істинними, звідси відразу слід, що таке справжні затвердження, недовідні в T). 2. Нехай T — «підходяща «формальна система, і припустимо знову, що T коректна. Тоді ми можемо побудувати конкретне твердження G (зване «гёделевым твердженням »), що має наступним властивістю: G істинно, але недовідно в T. 3. Нехай T — «підходяща «формальна система, і припустимо, що T консистентна. Тоді T перестав бути повної системою, тобто. існує твердження G таке, що T неспроможна де його довести, ані заперечити; більше, ми можемо побудувати таке конкретне G (зване «гёделевым твердженням »). Неповнота системи T стверджується як результату лише у третьої версії, але то зрозуміло, що вона відразу випливає з ув’язнення й у перших двох версіях. У них укладаємо, що є якесь справжнє, але недовідне твердження. Таке твердження T не доводить, а й спростувати його — довести його заперечення — вона може, т.к. його заперечення брехливо, а T (у перших двох варіантів теореми) коректна і доводить лише істинні затвердження. Тому T неспроможна ні довести, ані заперечити таке твердження G і, отже, T неповна. Але що справді відрізняє два версії від третьої: умова теореми. У у перших двох версіях не від системи T потрібно бути коректною; в третьої версії повинна бути лише консистентної - набагато більше слабке вимога. Є незліченну кількість консистентних, але некоректних систем. Ще важливіший те що, що у умови, й у укладанні третьої версії теореми задіяні лише синтаксичні поняття, які потребують поняття «істинності «, які потребують семантики. За третьою версіэю теореми це і є та, яку спочатку довів Гёдель на початку 1930-х уже минулого століття. коли бути зовсім точним, формулювання Гёделя включала додаткове синтаксичне умова для теорії T, що називається w-консистентностью (вимовляється «омега-консистентность »). Та через два п’ять багатьох років після публікації статті Гёделя Россер довів, від цього умови можна позбутися і однієї консистентности) Те, що у найсильнішої і загальної своєї формулюванні теорема Гёделя не накладає на T ніяких істотних семантичних умов, і висновок її також цілком синтаксично — дуже важливо зрозуміти. Важливо тільки й й не так оскільки інколи ми хочемо застосувати теорему Гёделя до некоректним системам, хоч і це теж вірно. Важливо переважно за такими двом причин. По-перше, перша теорема про неповноті Гёделя використовують у доказі другий теореми про неповноті Гёделя, яка доводить, що «підходяща «(у трохи іншому, але схожому з описаним вище, сенсі) формальна система T неспроможна довести власну консистентность, якщо вона консистентна (якщо вона неконсистентна, вона може довести все що велять, включаючи власну консистентность, як не парадоксально це навіть звучить). Не вдаватимуся деталі, але зазначу лише, у процесі докази другий теореми про неповноті необхідно показати, що доказ першої теореми про неповноті можна формалізувати всередині системи T. Інакше кажучи, не просто «якщо T консистента, вона неповна «(третя версія першої теореми про неповноті, див. вище), але й це твердження (точніше, його арифметичний аналог) можна довести про систему T. Але час, як можна формалізувати «всередині «системи T такі поняття, як «формальна система », «консистентность «і «повнота », виявляється, що правове поняття «істинності «формалізувати всередині T неможливо у принципі. Тому перше і друге варіанти теореми Гёделя, хоч і простішими як доказ, неможливо знайти використовуватимуться докази другий теореми Гёделя.

Во-вторых, теорема Гёделя про неповноті застосовна як до формальним системам, сформульованим у мові арифметики (тобто. що про натуральних числах), але також до незліченному безлічі інших формальних систем, яких потрібно лише, щоб були «підходящими «у властивому технічному сенсі; основну вимогу тут — щоб були щонайменше потужними, ніж теорія T в мові арифметики, на яку ми власне доводимо теорему Гёделя, але це вимога забезпечується можливістю інтерпретувати T у такому нову теорію. Наприклад, формальна система ZFC, використовувана для формалізації теорії множин, а із нею та практично всім сучасним математики, набагато більш мощна, ніж якась простенька арифметична T, на яку ми довели теорему Гёделя це можна суворо описати (пред'явивши інтерпретацію, тобто. спосіб перевести затвердження з мови T в затвердження мови ZFC, і показавши, що ZFC тоді доводить «переклад «всіх аксіом T) і потім із нього стане слідувати, як і ZFC теж неповна, тобто. у ній також є якесь гёделево твердження G, яке не можна ані довести, ані заперечити.

Проблема, проте, у цьому, що на відміну від арифметичних формальних систем, для тверджень яких ми є зручний й утворився звичайний спосіб визначити їх істинність (подивитися, вірні вони як твердження про натуральних числах), й інших формальних систем, таких, скажімо, як ZFC, поняття істинності взагалі визначено чи визначено дуже погано. Їх перша і друга версії теореми Гёделя виявляються невідповідними саме бо ці версії спираються на коректність даної системи та існувати певного поняття істинності тверджень. Підходить лише третя, суто синтаксична версия.

1. internet

2. internet

3. internet

ПоказатьСвернуть
Заполнить форму текущей работой