Гёдель, Туринг, Черч

 
1 2 3 4

Rada

опытный

AidarM и Iva посвящается.

Не могу обойти вниманием ваш интерес к проблемам неопределённости в математике. Iva постоянно напрашивается на разговор по теме в нескольких топах сразу :) , а AidarM ошивается в математических топах, и уже пополнил свои знания в теории множеств. :) Сразу оговорюсь - я не имею именно математического образования, а просто по специальности изучал немного эту тему, плюс читал одну очень хорошую книгу ("Гёдель, Эшер, Бах", Хофстадтер). Начнём пожалуй с Гёделя, а потом познакомимся с проблемами неопределённости в теории вычислений (Туринг, Черч).

Часть 1. Парадокс Рассела.
На рубеже 19-20 вв. теор. множеств основательно вошла в математику. На основе теор. множеств и аксиоматического метода возникли попытки формализовать основу основ математики – элементарную арифметику, также именуемой теорией чисел. Некто Гётлеб Фрег, немецкий математик, занимавшийся в то время такой формализацией арифметики, наряду с Джузеппе Пеано, направил результат своих трудов на критику Бертрану Расселу. Его формализация арифметики не содержала ничего, кроме логических правил дедукции и понятия множества. Именно из-за такой простоты такая теория чисел выглядела сильной – зная только простые правила логики и операций над множествами, мы можем обьять все факты о натуральных числах! После ознакомления с трудом Фрега, Рассел выдал следующую аллегорию, в которой он хотел показать проблему с определением понятия «множества».

В некотором городе живет брадобрей мужского пола, который бреет тех и только тех горожан мужского пола, которые не бреют самих себя. Бреет ли брадобрей самого себя?

В данной постановке задачи очевидно, что ответом не может быть ни «да» (потому что это будет противоречить условию «не бреют самих себя») ни «нет» (противоречие условию «бреет»). Нетрудно преобразовать данную аллегорию на язык математики. Условно разделим все множества на два класса – «хорошие множества» это те, которые не содержат себя в качестве своего элемента, и «нехорошие множества» это те, которые содержат. (Пример «нехорошего множества» - «все множества, определённые менее чем 1000 словами на русском языке». Как видно, определение имеет длину менее чем 1000 слов, поэтому такое множество содержит ко всему прочему и себя в качестве элемента). Теперь определим множество S как множество всех «хороших множеств». Содержит ли S себя в качестве элемента? Ответ «да» прямо противоречит условию, что S – суть множества, не содержащие себя как элемент. Ответ «нет» советует, что S всё же должен содержать себя, т.к. все множества, не содержащие себя как элемент должны быть в S. Итак, мы имеем парадокс вида S = {A: A не принадл. A}. Было сразу замечено, что с теор. множеств что-то не то, если её можно прибить таким вот лёгким и незамысловатым выражением. Проблема была «решена» в какой то мере самим Расселом, спустя годы в его труде «Principles of Mathematics» методом использования типов. Немного видоизменим парадокс на S = {A: A принадл. T ^ A не принадл. A}. То есть, если рассматривать не просто множества, а множества, принадлежащие некому известному множеству (типу) T, то ответом на вопрос содержит ли S себя будет просто «нет», потому что S не будет принадлежать типу T. Использование типов позволяет избегать ссылок математических обьектов на самих себя, тем самым избегая парадоксов, схожих с парадоксом Рассела. Логические противоречия в математике были устранены, и вот уже казалось, что математику можно полно и непротиворечиво описать множествами и логикой. Но через двадцать лет Гёдель доказал теорему о неполноте, а чуть позже Туринг и Черч пришли к похожему результату – о невычисляемости определённых задач.

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

Продолжение следует.
С себя можно начать когда все остальное будет в порядке.  
29.03.2004 14:06, AidarM: +1: За отзывчивость, желание помочь. :)

+
-
edit
 

-exec-

опытный

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

кстати добавлено ни каким-то deus ex machina, а именно формулировкой, которая приводит к противоречию. доказательство внутренней противоречивости некоего объекта является доказательством того, что этот объект не существует. доказательство самопротиворечивости предиката доказывает ложность предиката.
а парадокс возникает потому, что мы предполагаем верность предиката и существование объекта. и неожиданно видим невозможность упомянутого предиката и объекта.

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

но такой выход таки доказывает невозможность существования объектов в этом пространстве. зато позволяет существовать таким объектам вне этого пространства и не быть обязанными обладать его качествами.

мне стереть свой пост, если я неуместно влез? ;)
 
Это сообщение редактировалось 29.03.2004 в 03:55

Iva

аксакал

Я не возьмусь точно пересказывать книгу Клейна "Математика - утрата определнности" М.Наука 1982-84 года. Я ее тогда же и читал.

Там все рассматривается немного с другого конца.

К концу 19 века математика была близка к воему завершению.
Где-то в это время были сформулированы Гильбертом 10 проблемм, которые закрывали вопросы по математике. По ее непротиворечивости в частности.

После этого или немного до этого была доказана теорема, что вся математика непротиворечива, если непротиворечива арифметика.

Из 10 проблемм Гильберта к 20-м годам 20 века были решены 5 -6.
А потом Гедель доказал свою теорему :-).

Для меня лично этот результат послужил причиной пересмотреть мое отношение к ыфилософии, как науке и ее достижениям. Так как фактически Гедель подтвердил результат гносеологии Канта.

Или как сформулировал еще более древний философ - единственное, что я знаю, что я ничего не знаю.

Многие знания - многие печали (с) Эклезиаст 10в до н.э.  
+
-
edit
 

Mishka

модератор
★★☆

Давайте, все же приведем теорему Гёделя о неполноте - я уже приводил по памяти и пороюсь в книжках. Что-то мне кажется, что народ ее не так понимает. Хотя могу быть не прав.
 
+
-
edit
 

KBOB

опытный

Mishka, 29.03.2004 06:17:31 :
 


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


Гедель прости утверждает, что существуют высказывания (утверждениея), которые нельзя доказать за конечное или даже счетное количество шагов. Для меня в этом нет ни чего удивительного поскольку существуют множества с мощностью большей чем множество целых чисел.
И все прблема в том, что для человека процесс доказательства чего-либо разбивается на шаги. НЕОБХОДИМОСТЬ ЭТОГО НЕ ОЧЕВИДНА И НИ КАК НЕ ДОКАЗАНА, но тем немение так оно и есть, более того вычислительные машины, в том числе и абстрактные, производят свои вычисления пошагово (и каждый шаг может быть пронумерован), а не непрерывно (как расположенны точки на прямой).
Таким образом используюя дискретный способ логических рассуждений человек намеренно ограничивает себя в выборе средств достижения истины.

Раньше пользовался системой DOS и проблем с безопасностью не было, а тут поставил Windows и кто-то залез ко мне в компьютер!
 
+
-
edit
 

AidarM

аксакал
★☆
KBOB
>Таким образом используюя дискретный способ логических рассуждений человек намеренно ограничивает себя в выборе средств достижения истины.

ОК, приведите пример континуального способа логических рассуждений(не путать с рассуждениями о континууме). :)

Iva

>Или как сформулировал еще более древний философ - единственное, что я знаю, что я ничего не знаю.

Чего-то уж очень сильное утверждение. Что ентот философ имел в виду под знанием?

Провокационный вопрос к вам по поводу:

>Для меня лично этот результат послужил причиной пересмотреть мое отношение к ыфилософии, как науке и ее достижениям. Так как фактически Гедель подтвердил результат гносеологии Канта.

какие именно выводы вы из т. Геделя делаете?
Солипсизм не пройдёт! :fal:  
Это сообщение редактировалось 29.03.2004 в 15:48
+
-
edit
 

-exec-

опытный

это может подталкивать агностицизму например. или в более простом случае отталкивать от науки (логики аристотеля) в сторону непрерывной "логики" веры в бога сильном случае и церкви в слабом.
интересно, существует ли конечная система гипотез, полностью покрывающая поле доказанных знаний. количество дыр гедель не указывает.
 
+
-
edit
 

Mishka

модератор
★★☆

ИМХО, Гедель говорит, что одновременно доказать полноту и непротиворечиваость системы средствами системы невозможно. Это означает, что дырок может быть много, очень много.

КВОВ

Не согласен. Посмотрите на доказательства в теории чисел - за конечное число шагов доказываются многие теоремы для множеств мощности континуум. Для простоты рекомендую посмотреть доказательства Айдара того факта, что отрезок [0,1] и [0,2] равномощны - 1 шаг :P .
 
+
-
edit
 

Mishka

модератор
★★☆

Да, забыл спросить, а почему Туринг? В русскоязычной литературе (во всяком случае, когда я учился) он вроде Тьюринг. А Чёрч, вроде был Чорчем.
 
+
-
edit
 

-exec-

опытный

Mishka, 29.03.2004 20:02:30 :
ИМХО, Гедель говорит, что одновременно доказать полноту и непротиворечиваость системы средствами системы невозможно. Это означает, что дырок может быть много, очень много.
 


не понял почему
 
+
-
edit
 

Mishka

модератор
★★☆

Так вроде это качественная оценка. Поэтому может существовать одна, может много, а может ни одной. Нельзя сказать этого в рамках самой системы.
 
+
-
edit
 

-exec-

опытный

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

Iva

аксакал

AidarM, 29.03.2004 07:37:16 :
1. >Или как сформулировал еще более древний философ - единственное, что я знаю, что я ничего не знаю.

Чего-то уж очень сильное утверждение. Что ентот философ имел в виду под знанием?

2. Провокационный вопрос к вам по поводу:

>Для меня лично этот результат послужил причиной пересмотреть мое отношение к ыфилософии, как науке и ее достижениям. Так как фактически Гедель подтвердил результат гносеологии Канта.

какие именно выводы вы из т. Геделя делаете?
 


1. Возможно и сильное, для шокирования неподгоовленной публики.

2. О непознаваемости объекта, на основе ощущений субъекта.
"Кант показал большой скандал в философии" (с) Гегель?
Вопрос о познаваемости мира был закрыт и остался только для особо упертых товарищей типа ВИЛа, который переформулировал абсолютную истину в процесс прознания.
Многие знания - многие печали (с) Эклезиаст 10в до н.э.  

Rada

опытный

2 -exec-: предикат "множество А не содержит себя" чётко сформулирован, и следовательно, по "наивной" теор. множеств может определять множество. Парадокс Рассела просто положил конец такой вот "наивной" практике определения множеств. А что вы имеете ввиду под "ложностью предиката"? Для каких переменных?
С себя можно начать когда все остальное будет в порядке.  
+
-
edit
 

-exec-

опытный

если я говорю о том, что предикат ложный, то я имею в виду, что он является тождественным FALSE, вне зависимости от переменных, входящих в него.
предикат - утверждение о свойствах.


так я и говорю, что fool protection в языке нету и позволяет оксимороны.
 
+
-
edit
 

Mishka

модератор
★★☆

Iva, 30.03.2004 06:42:09 :
1. Возможно и сильное, для шокирования неподгоовленной публики.
 


:P Но ведь и это утверждение - гм - не истинное и не ложное. Т.е. никакое.
 

Rada

опытный

2 exec: если ~P(x) для всех x, то множество S - пустое. Что то не сходится. Надо бы доказать, что S не существует.
С себя можно начать когда все остальное будет в порядке.  
+
-
edit
 

-exec-

опытный

есть булевы функции, имеющие собственное имя.
X=0 Y=0 F(X,Y)=0 - тождественный ноль. в булевом смысле - ложь.
эта, можно сказать, первая по счёту функция среди функций от двух аргументов. последняя - тождественная единица. среди них есть известные вам "логическое и", "логическое или", "штрих шеффера", "стрелка пиркса", "исключающее или", "импликация".
табличку на форуме я рисовать не умею.

вас интересует пример предиката, соответствующего тождественному FALSE?
(A=B & A<>B) для всех A и B.

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

AidarM

аксакал
★☆
Iva
>О непознаваемости объекта, на основе ощущений субъекта.
>"Кант показал большой скандал в философии" (с) Гегель?

Если под познанием подразумевать добычу некоего высшего, абсолютного и окончательного знания, то да, тут все ОК, не придраться. :) Уж наука-то поиском подобных вещей не занимается. ИМХО. Если чьи-то красивые иллюзии при этом рассыпались - их проблемы. А серьезно, что там под познанием подразумевали эти достойные люди? Я серьезно спрашиваю, бо неуч в этой области и про поиск 'высшего и абсолютного' знания сам домыслил, ориентируясь на свой опыт по общению с 'гуманитариями'. :)

>Вопрос о познаваемости мира был закрыт и остался только для особо упертых товарищей типа ВИЛа, который переформулировал абсолютную истину в процесс прознания.

А хто ето? И нафига, пардон, вообще эта абсолютная истина, если она даже не определена толком? Или определена? Неужели ее кто-то в реале на приборах замерил? :lol: Я это к тому, что критерий истинности у нас с вами один, с вами мы уж как-нибудь договоримся. :) Хотя я, по видимому, как раз из 'особо упертых'.

Перефразируя Чебурашку с его гвоздями, имеем: для получения абсолютной истины нам необходим абсолютный эксперимент. :)
Требуемая степень абсолютности :lol: искомой истины задается при его постановке. :D:D:D
Солипсизм не пройдёт! :fal:  
Это сообщение редактировалось 30.03.2004 в 19:32
+
-
edit
 

Mishka

модератор
★★☆

-exec-, 29.03.2004 22:50:02 :
есть результат, который оценивает (или доказывает невозможность оценить) число дырок? или так, предчуствие такое? где один партизан, там их тыща.
 


В свете теоремы, он не может быть доказан. Поскольку проблемы с полнотой будут, вроде.
 
+
-
edit
 

Mishka

модератор
★★☆

-exec-, 30.03.2004 09:42:01 :
я не понял что вы называете S, потому, что я логику не изучал. не довелось, знаете-ли. задержался в развитии.
 


Рада использовал предикат как некоторое свойство членов множества S - т.е. само множество состоит из таких элементов, для которых он истинен. При этом в формуле вида A&B за А может скрываться некоторое утверждение. Например число четно. Построим множество Е такое, что: ( (е натуральное) или (е есть ноль) ) и (е четно) - получим неотрицательные четные числа.

Логика здесь выступает в качестве интструмента вывода.
 
+
-
edit
 

-exec-

опытный

да... с этим постом у меня какие-то проблемы - не могу понять. но я пропробую.
1.2.3... скипнуто.
4.Rada сказал, что из существования функции "тождественная ложь" следует существование S, хоть бы и пустого.
5.я показал пример такой функции (F(A,B)) для любых аргументов. и я имел в виду существующие аргументы.
6.ты объясняешь мне, что ЕСТЬ множество аргументов для которых, для которых F(A,B) верно. только что множество пустое.

я не вижу здесь противоречия, потому, что для меня пустое множество обозначает в данном контексте "ни при каких аргументах". "ни при каких аргументах F(A,B) истинно" ("не может быть" - это особенность русского языка - двойное грамматическое отрицание для обозначения одного отрицания).

моё утверждение было в том, что "не существует пары аргументов (A,B) при которых тождественная ложь F=TRUE". можете это переформулировать так, что мощность множества S решений F=TRUE равна нулю.
я НЕ утверждал, что множества S не существует.

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

по поводу множества E я вообще ничего не понял. ну да, построили. { {e enters_into N} union {0} } intersection {e, e divisible_by 2}
что из того?
 
Это сообщение редактировалось 30.03.2004 в 19:33

Rada

опытный

2 -exec-: да вы верно всё говорите, я просто хочу прояснить ход вашей мысли. Допустим, мы имеем предикат "множество не содержит само себя" как N(x). Вы ведь не будете утверждать, что ~N(x) для всех x (например, N({1,2,3}) = TRUE)? То есть, если вы даёте мне любое множество (кроме пресловутого S) то я дам вам ответ - истина или ложь. Проблема возникает при N(S).

Я что хочу сказать то - сам по себе предикат N(x) выглядит безобидно, пока в него не подставишь S. То есть возникают сомнения в "существовании" N(x) и как следствие S. Поэтому то и ввели понятие типа - в этом случае S существует, но вне типа, то есть, вне области определения N(x).
С себя можно начать когда все остальное будет в порядке.  
+
-
edit
 

-exec-

опытный

Mishka, 30.03.2004 19:00:34 :
-exec-, 29.03.2004 22:50:02 :
есть результат, который оценивает (или доказывает невозможность оценить) число дырок? или так, предчуствие такое? где один партизан, там их тыща.
 


В свете теоремы, он не может быть доказан. Поскольку проблемы с полнотой будут, вроде.
 


какие?
гедель говорит, что не существует полной непротиворечивой теории в которой всё доказано. если теория A будет содержать один истинный, но недоказуемый предикат (то есть неполная), то гедель ей существовать позволит. ведь он не обязывает, чтобы число дырок являлось именно бесконечной исчислимой или неисчислимой величиной.
 
1 2 3 4

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru