Теореми Геделя про неповноту. Теорема Пенроуза

У 1900 році в Парижі пройшла Всесвітня конференція математиків, на якій Давид Гільберт (David Hilbert, 1862-1943) виклав у вигляді тез сформульовані ним 23 найважливіші, на його думку, задачі, які належало вирішити вченим-теоретикам. Під другим номером у його списку значилася одна з тих простих задач, відповідь на яку здається очевидною, поки не копнеш трішки глибше. Говорячи сучасною мовою, це було питання: чи математика є самодостатньою? Друге завдання Гільберта полягало в необхідності суворо довести, що система аксіом — базових тверджень, які приймаються в математиці за основу без доказів, — досконала і повна, тобто дозволяє математично описати все, що існує. Треба було довести, що можна задати таку систему аксіом, що вони будуть, по-перше, взаємно несуперечливими, а по-друге, з них можна вивести висновок щодо істинності чи хибності будь-якого твердження.

Візьмемо приклад із шкільної геометрії. У стандартній Евклідовій планіметрії(геометрії на площині) можна беззастережно довести, що твердження сума кутів трикутника дорівнює 180» істинне, а твердження «сума кутів трикутника дорівнює 137» помилкове. Якщо говорити по суті, то в Евклідовій геометрії будь-яке твердження або хибне, або істинне, і третього не дано. І на початку ХХ століття математики наївно вважали, що така ж ситуація має спостерігатися у будь-якій логічно несуперечливій системі.

І тут у 1931 році математик Курт Гедель — опублікував коротку статтю, що просто перевернула весь світ так званої «математичної логіки». Після довгих та складних математико-теоретичних преамбул він встановив буквально таке. Візьмемо будь-яке твердження типу: «Припущення №123 в даній системі аксіом логічно недоводиться» і назвемо його «твердженням A». Так от, Гедель просто довів таку дивовижну властивість будь-якої системи аксіом:

«Якщо можна довести твердження A, то можна довести і твердження не-A».

Іншими словами, якщо можна довести справедливість твердження «припущення 123 неможна довести», то можна довести і справедливість твердження «припущення 123 не можна довести». Тобто, повертаючись до формулювання другої задачі Гільберта, якщо система аксіом повна (тобто будь-яке твердження в ній може бути доведено), вона суперечлива.

Єдиним виходом із такої ситуації залишається прийняття неповної системи аксіом. Тобто, доводиться миритися з тим, що в контексті будь-якої логічної системи у нас залишаться твердження «типу А», які є свідомо істинними чи хибними, — і ми можемо судити про їхню істинність лише поза рамками прийнятої нами аксіоматики. Якщо ж таких тверджень немає, значить наша аксіоматика суперечлива, і в її рамках неминуче будуть присутні формулювання, які можна одночасно і довести, і спростувати.

Отже, формулювання першої, або слабкої теореми Геделя про неповноту: «Будь-яка формальна система аксіом містить недозволені припущення». Але на цьому Гедель не зупинився, сформулювавши і довівши другу, або сильну теорему Геделя про неповноту: «Логічна повнота (або неповнота) будь-якої системи аксіом може бути доведено у межах цієї системи. Для її доказу чи спростування потрібні додаткові аксіоми (посилення системи)».

Спокійніше було б думати, що теореми Геделя мають абстрактний характер і стосуються не нас, а лише областей абстрактної математичної логіки, проте фактично виявилося, що вони безпосередньо пов'язані з пристроєм людського мозку. Англійський математик і фізик Роджер Пенроуз (Roger Penrose, р. 1931) показав, що теореми Ґеделя можна використовувати для доказу наявності важливих відмінностей між людським мозком і комп'ютером. Сенс його міркування простий. Комп'ютер діє строго логічно і не здатний визначити, істинне чи хибне твердження А, якщо воно виходить за рамки аксіоматики, а такі твердження, згідно з теоремою Геделя, неминуче є. Людина ж, зіткнувшись з таким логічно недоведеним і незаперечним твердженням А, завжди здатна визначити його істинність чи хибність — виходячи із повсякденного досвіду. Принаймні у цьому людський мозок перевершує комп'ютер, скований чистими логічними схемами. Людський мозок здатний зрозуміти всю глибину істини, укладеної в теоремах Ґеделя, а комп'ютерний — ніколи. Отже, людський мозок є не просто комп'ютер. Він здатний приймати рішення і тест Т'юрінга на інтелектуально обумовлену поведінку пройде успішно.

Парадокс брехуна

Популярний варіант парадокса такий. Припустимо, хтось каже, що він бреше. Що він стверджує насправді - правду чи брехню? Якщо допустити, що він говорить правду, тоді те, що він стверджує–істина, і отже, він бреше. Якщо ж він бреше, то, що він стверджує, брехня, і тим самим він стверджує істину. Парадокс вбачають у тому, що неможливо однозначно визначити значення істинності висловлювання «Я брешу».

Теорема Геделя Т'юрінга

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

Теорема Пенроуза про штучний інтелект (повний доказ)

1. Припустимо, що деякий комп'ютер, що має архітектуру кінцевого автомата, має всі інтелектуальні здібності всього людства (є сильним ШІ у вузькому сенсі). 2. Тоді, будь-який математик, використовуючи свої математичні здібності, на основі теореми Геделя-Т'юрінга може побудувати істинне твердження, істинність якого не може бути перевірена цим комп'ютером, але яка зрозуміла для математика (за побудовою). Побудова завжди можлива, оскільки доказ теореми Геделя-Т'юрінга має конструктивний характер. 3. Отже, припускаючи, що комп'ютер має всі здібності людей, ми негайно вказуємо здатність людини, якої цей комп'ютер не має. 4. Це є протиріччя, і це доводить, що такий комп'ютер (сильний ШІ) не може існувати. Сильний ШІ неможливий для жодних комп'ютерів на основі архітектури кінцевого автомата.

Те, що мозок - це не комп'ютер, НЕ є думкою Пенроуза–це теорема, доведена Пенроузом!

Пенроуз:

Теорема Пенроуза: мозок – не комп'ютер, мозок реалізує необчислювану активність.
Необчислювана активність реалізується завдяки необчислюваній фізиці, використовується мозком.
Оскільки вся відома фізика, включаючи квантову фізику, – обчислювана, то робота мозку заснована на невідомій незрахунковій фізиці.

Критика:

Квантова фізика таких складних систем, як мозок, фізично необчислювана у нашому Всесвіті у сенсі космологічного горизонту обчислюваності.
Отже, щоб ефективно проявляти необчислювану активність, мозку достатньо використовувати квантові процеси.
Сенси, якими оперує мозок, можуть представлятися не інформацією, а квантовою інформацією.