Показано с 31 по 60 из 64
-
08.12.2005, 17:44 #31
- Регистрация
- 25.11.2005
- Сообщений
- 690
(замечу, что требование "объяснять каждое слово" является принципиально недостижимым, и предлагаю начать тогда со слова "мама")
мама - "яя"
-
08.12.2005, 18:44 #32
- Регистрация
- 03.12.2005
- Сообщений
- 177
Сообщение от Сахават
Константин, не обижайтесь, пожалуйста.
Вы не заметили (можете проверить), но в моем посте №26 в самом начале, при цитировании Вашего высказывания из №23, я в нем походя исправила опечатку в слове "парадоксам", которая попалась мне на глаза. И при этом не сделала Вам никаких замечаний. И у меня бывают ошибки, что здесь такого, поправляйте или уточняйте, да и дело с концом. Люди - не роботы, и от опечаток никто не застрахован. Мы же идеи обсуждаем, а текст пусть спеллинг проверяет - такова моя позиция. Мы, к примеру, корректоров для таких работ нанимаем, когда надо, чтобы серьезных людей такой ерундой не грузить.
-
08.12.2005, 21:36 #33
- Регистрация
- 02.12.2005
- Сообщений
- 10
Сообщение от Сергей_Рубцов
Да, сам вывод "аксиомы" (условно назовем ее так) здесь не предъявляется. Это щепитильный момент (то, какого рода он должен быть), потому что при выводе возникает «крамольная» ситуация: чтобы провести вывод аксиомы, нужно использовать ее же как средство при этом выводе (т.е. исходить из предположения, что она уже доказана). Мягко говоря, в формальных теориях это, как известно, запрещается.
Все-таки я прибег к крамоле и попытался разрешить эту ситуацию (http://www.trinitas.ru/rus/doc/0012/001a/00120080.htm ). Такой ход оправдан тем, что принципиального запрета на образование логических кругов и замкнутых причинно-следственных цепочек в природе нет. (Например, в программировании используются циклические конструкции и рекурсивный вызов, в которых логическая связь реализуется циклически, замкнутая петля причинности используется в контуре обратной связи в технике.). Однако замкнутые круги как таковые считаются теоретиками недостойными рассмотрения (этому есть неформальные причины). Это с одной стороны.
С другой стороны, эта «аксиома» является и своей собственной "мета-аксиомой" (формально неотличимой) и из-за разности уровней мета-аксиома может «манипулировать» такой же аксиомой (как бы самой собой), находящейся уровнем «ниже»: в контексте уже не мета-, а предметного уровня – из-за различия в контекстах смысл у них получается разный (т.е. фигурируют два разных "объекта"). Поэтому их отношение (подчиненость) не является банальной тавтологией и такое взаимодействие между ними в выводе, как я полагаю, допустимо.
Конечно, это воспринимается очень странно, не не более того.
-
08.12.2005, 23:07 #34
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Ysto
2. Обратная всязь в технических системах (часто говорят "отрицательная" обратная связь, - в этом есть определенный смысл, когда речь идет об устойчивости систем) относится к теории автоматического регулирования, - причем здесь "циклические конструкции"? Здесь нет никаких циклов.
3. Использование в алгоритмах так называемых вложенных циклов неминуемо приводит к проблемме N-полноты (т.е. к ситуации, когда такой алгоритм не может быть реализован на вычислительных машинах за разумное время).
О чем Вы толкуете, уважаемый Ysto?
-
08.12.2005, 23:16 #35
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Адепт_КАиП
-
09.12.2005, 00:44 #36
- Регистрация
- 03.12.2005
- Сообщений
- 177
Константин, мне все понятно, что Вы пишете (и в статьях и в постах), и я не имею никаких возражений по существу. Более того, сама имею ровно такие же представления.
С Рубцовым в словоперекладывании состязаться бесперспективно, поверьте. Но если доказать формально, то он, быть может, поймет.
Но я не люблю «слова», они все путают. То есть статейную форму подачи такого сложного содержания я считаю непригодной, недопустимой и неудовлетворительной, вносящей дополнительное непонимание. Это не к Вам претензия, это потребность в переводе на формальный язык, которую я испытываю. То есть хочется просто взять и всю «воду» вычеркнуть :-).
Поэтому предлагаю перейти к определению "самовыводящегося формализма" в формальной форме. Для этого надо договориться, из чего мы все строим, что такое «формализм», что такое «содержание», «интерпретация», «вывод формализма», что такое уровни, метауровни и т.д. (или другие названия подходящие закрепить).
Пожалуйста, перейдите к критике моих предварительных предложений по именованию и существу базисных схем (пост 26).
Несколько комментариев (в первую очередь не к Вам обращенных) по Вашим статьям. Возможно, на своем языке Вы об этом уже писали, но я на своем, с Вашего позволения.
Сообщение от Ysto
Не лукавые – только натуральные числа и порядковые числа, так как выводимы напрямую из числа элементов множеств и порядка.
Сообщение от Ysto
А формальный ввод этого принципа (только частного, конкретного) в виде соответствующей аксиомы в изначальный формализм при прецеденте несоответствия – это изменение формализма. Или, по другому – при нахождении несоответствия оно может быть формально устранено при помощи общего принципа соответствия.
Вы, Константин, в статье писали и приводили примеры, что почему-то существуют не только парадоксы (а их напридумали не так уж много), а существует масса систем, в которых проблем не возникает. А не возникают они потому, что многие разработчики догадываются о существовании этого принципа («соответствия»), и вводят соответствующие ограничения. К примеру, при рекурсивном определении обязательно должно быть условие выхода из рекурсии для всех возможных значений, при всех возможных условиях.
При нахождении несоответствия я вижу 3 основных базовых варианта (могут быть и производные) - как дойдем, может, еще какие-то базовые появятся:
· система ограничивается (снимается противоречие), урезается (например, установление «жесткого» ограничения на число итераций в цикле самый примитивный вариант);
· система размножается (по числу возникающих вариантов несоответствия – получается много формальных систем);
· система расширяется на один из формальных вариантов условно «субъектно» (то есть вариант выбирается по какому-то другому принципу, в том числе и предустановленному («по умолчанию»), или хаотичному – бессубъектно, или содержательно – субъектно, организационно).
Но объяснить это раньше, чем мы о базовых понятиях договоримся, я не в состоянии.
Еще, забегая вперед, скажу. В некотором смысле (для выделенного далее частного "статического" случая) для удовлетворения принципа соответствия не нужны никакие уровни-метауровни и др. прикладные штуки.
Если имеется система множеств и их отношений (как система аксиом), то непротиворечиво производными могут являться как все элементы множеств и отношений, так и все вложенные полифакторструктуры на полагаемой системе. Дело в том, что любое множество включает по умолчанию все свои элементы, все свои подмножества, каждое из которых включает все свои подмножества и т.д. И любой формальный вывод «внутри» будет корректным. Это – достаточное формальное условие, допускающее использование слова «все». Это не единственный вариант, а самый простой.
Предварительное ограничение на будущее. Самовыводящийся формализм, который мы хотим определить (если у оппонентов нервов хватит), может выводить «расширение», изменение себя, «приписывание» (или, наоборот урезание) к себе «старому». То есть свойство самовыводимости мы выводить не будем (так как оно в аксиоматику предполагается быть положенным), а совсем другие свойства.
-
09.12.2005, 10:50 #37
- Регистрация
- 24.11.2005
- Сообщений
- 188
Сообщение от Ysto
Сообщение от Ysto
Что касается противоречий, циклов и т.п., то из современных прикладников - последователей Гегеля, никто не отрицает эти сущности. Более того, искусственно их создают в прикладных системах, используя их в качестве катализатора изменений формальных систем.
Простите, что пишу коротко. Не хочу отнимать время у читателей и дисковое пространство у администратора
-
09.12.2005, 11:47 #38
- Регистрация
- 24.11.2005
- Сообщений
- 188
И еще...
Ценность возможных теорий построения формальных систем все-таки следует, на мой взгляд, соизмерять с т.з. всевышнего. Нейро-кибернетика (исследования мехнизмов работы человеческого мозга) дают некоторые ответы на вопрос, как правильно следует строить формальные системы с учетом ограничений носителя этих систем. Имею в виду архитектуру мозга...
-
09.12.2005, 20:22 #39
- Регистрация
- 02.12.2005
- Сообщений
- 10
Евгению.
Спасибо за ссылку на формальную арифметику
Сообщение от Евгений
Согласен с Вами, понять сразу не просто, претензии принимаю. (Погорячился -- неприятно, когда мимоходом и необоснованно (особенно те, кто не выработал собственного мнения) тебя “тыкают носом” в пресловутую геделеву теорему.)
Попробую разъяснить (если интересно).
Есть положение (правило следования “ЕСЛИ – ТО”), по умолчанию (эмпирически) считающееся истинным. Но его нельзя ни доказать ни опровергнуть (потому что в обоих случаях доказываем через то, что требуется доказать – это, как известно, порицается). При этом, что интересно, – какую бы более общую (объемлющую) формальную систему мы не взяли, это правило следования (для проведения рассуждения) с необходимостью там уже имеется. Т.е. оно является как бы “абсолютным метаправилом” существующим априорно, и “зайти за него” нельзя (кстати, за этим стоит поразительный факт, характеризующий нашу действительность). Иными словами, мы будем выстраивать дурную бесконечность, не приближаясь к цели.
Поэтому я высказал (пока в соответствии с недопустимостью логических кругов) сомнение о достоверности и справедливости этой связки, так как невозможна формальная система, где её можно доказать (а справедлива она лишь “эмпирически”, т.е. что пока не подводила).
Объясните мне, пожалуйста, вот что:
Если утверждается, что существуют высказывания в формальной арифметике, которые нельзя ни опровергнуть, ни доказать в заданной системе аксиом, то это не значит, что нет доказуемых в этой системе аксиом высказываний. Поэтому Геделем, на самом деле, было сделано высказывание в виде теоремы, которое оказалось доказуемым.
Чтобы и остальным было ясно о чем речь, привожу отрывок из одного содержательного исследования:
“…Первый этап доказательства Геделя состоит в эффективном кодировании числами всех условий, входящих в определение формальной арифметики. Построение "парадоксального" условия приведет в конце концов к знаменитой второй теореме Геделя: "Система формальной арифметики содержит некоторое выражение е*, такое, то ни е*, ни не-е* не являются доказуемыми в формальной арифметике"
3.5.3. Структура доказательства теоремы Геделя о неполноте арифметики.
Идея доказательства заключается в том, чтобы построить такое выражение, которое свидетельствовало бы о своей собственной недоказуемости. Такое построение может быть выполнено в три этапа:
- первый этап – установление соответствия между формальной арифметикой и множеством целых чисел (геделизации);
- второй этап – построение некоторого специального свойства, А(х), о котором неизвестно, является ли оно теоремой формальной арифметики или нет;
- третий этап – подстановка в А(х) вместо х определенного целого числа, связанного с самим А(х), т.е. замещение этими числами всех х в А(х).
Формальная арифметика может быть арифметизирована (т.е. геделизирована) следующим образом: каждой ее теореме ставится в соответствие некоторое число. Однако так как всякое число также является теоремой, то всякая теорема может рассматриваться, с одной стороны, в качестве теоремы формальной арифметики, а с другой — как теорема над множеством теорем формальной арифметики, т.е. в качестве метатеоремы, соответствующей доказательству некой теоремы.
Таким образом, можно сделать вывод, что система формальной арифметики содержит также и свою собственную метасистему".
(Ж.-Л. Лорьер. Системы искусственного интеллекта. -- М.: МИР, 1991)Из содержания отрывка становится ясно, что Гедель "замутил" довольно основательно (гораздо круче чем в парадоксе "лжеца" или "брадобрея"). И в такой "мутной воде" он пытается определиться.В связи с тем, чтО в доказательстве предпринял Гедель, возникает некая аналогия. Манипуляции числами и как теоремами и как метатеоремами формальной арифметики напоминает манипуляции хитрого раджи из м/ф. "Золотая антилопа". Ссыпав монеты антилопы в свой сундук, раджа говорит, что они не отличаются от обычных в сундуке, а когда слуга, нашедший монеты антилопы, просит их ему вернуть, он заявляет, что их вернуть не сможет, поскольку не может свои монеты отличить от чужих (а свои он не отдает).
Раджа, таким образом, манипулирует представлением об одинаковости и различии монет – если это жадный раджа, он присваивает их себе. А не лукавый раджа мог бы их отдать – если, как он говорит, все монеты не отличаются друг от друга.
Каким способом мог бы Гедель отличить "теоремы" (числа) формальной арифметики от "метатеорем" (тоже числа)? И уследит ли он или кто другой тот момент, когда эти числа с разным смыслом могут перепутаться?! Так что в таком доказательстве неопределенности и неоднозначности может быть во много раз больше, чем в тех же элементарных парадоксах типа "парадокса брадобрея".
Поэтому Гедель и вывел, условно говоря (в контексте истории с сундуком раджи), что "монеты невозможно как вернуть, так и невозможно оставить".
Вы же опровергнуть его, как я понял, не можете, а раз так, то и ставить под сомнение его нельзя.
Наверное, логика дальнейшего доказательства теоремы построена Геделем таким образом, что опровергнуть впрямую ее нельзя (он ведь был не дурак и позаботился о безупречности доказательства).
Я думаю так. Может оказаться, что в процессе доказательства замена "теоремы" формальной арифметики на "метатеорему" вызовет некий эффект, который при возврате их на "исходные места" не исчезнет и проявится непредсказуемыми образом.
Например, когда вы ходите с развязанными шнурками, то шнурки с одной ноги болтаются сами по себе и как бы не связаны с другим ботинком. Когда же вы падаете, (эффект "наступания" ботинка на шнурок), то зажатый было шнурок после падения освобождается (опять ботинок и шнурок независимы), т.е. ситуация восстанавливается, и причина ("зажатие" шнурка) "растворяется". Но эффект тем не менее проявился (потеря равновесия)! А раз причины "нет", то падение, хотя имеет место, -- "недоказуемо".
-
10.12.2005, 01:00 #40
- Регистрация
- 03.12.2005
- Сообщений
- 177
Константин
Я кстати, как и Рубцов, не против аксиом, при выводе которых используются другие аксиомы, которые также как и первые включают базовые логические «операции». И считаю, что это формальности (непротиворечивости) никак не вредит.
Обращаю внимание, что хотелось бы отделить сами «операции» (импликации, конъюнкции, дизъюнкции, отрицания) от «комплексных» логических аксиом как «высказываний об объектах». (Есть вероятность, что в этом Ваше с ним взаимное недопонимание кроется)
То есть я согласна с Вами, что логические операции являются одновременно метаоперациями. Они – всегда полагаются и никогда не выводятся, можно так еще сказать. То есть они просто переносятся с уровень на уровень, объекты, к которым они прилагаются, только заменяются (по правилам уже для них определенным), и получаются разные классы допустимых силлогизмов (типа от общего к частному), и теоремы. Вывод теорем в этом смысле – это замена объектов высказывания, а не ее логики (которая просто «подставляется», «переносится»)+аксиоматика самих объектов добавляется.
Но объекты также могут быть образованы при помощи логических аксиом, а, кроме того, «нелогические» структуры на объектах тоже могут иметь собственную аксиоматику. К примеру, отношение множества и его собственных объектов является взаимооднозначным. Это правило тоже может переноситься по (мета) уровням.
И противоречивость кроется в преобразовании «объектов» по (мета) уровням, а не в первичной логике как таковой. Она какая есть, такая и должна оставаться (ложь на входе, байда на выходе, истина-истина).
Если очень хочется объединить в одно «самостоятельные» логические операции на объектах и внутриобъектные логические операции, то можно на «первичном графе» (минимальной формальной системы, которую я предлагала ввести) определить сразу два вида операций: направленные и ненаправленные.
Можно изначально положить эти два вида «связи» (о понятиях мы так и не договорились) – типа «стрелочки» и «палочки», а можно условно считать "ненаправленной" двунаправленную (граф направленный для логики тогда положить, от "точку старта мира" все раскручивать и непротиворечивость вычислять), но их тогда каждый раз отделять придется операцией классификации (разбиения).
Мы (в КАиП) пошли по третьему пути. Множества полагаем отдельно (то есть «прошиваем» аксиоматику множества заведомо), базовые ненаправленные операции полагаем отдельно (то есть «прошиваем» аксиоматику операций декартова произведения и булеана, они являются прямым следствием аксиоматики «множества»), логические выражения (направленные, или «причинно-следственные») отдельно. И всем этим хозяйством скопом по разным (мета) уровням и оперируем.
Заранее извиняюсь, если что-то непонятно, объясню.
-
11.12.2005, 15:32 #41
- Регистрация
- 02.12.2005
- Сообщений
- 10
Признаюсь, моя невыдержанность к собеседникам, замечания и претензии ко мне заставили задуматься.
Евгений
1. В программировании рекурсивное обращение ни к процедурам, ни к функциям, ни к используемым в программе переменным, ни даже к подключаемым модулям (Unut-ам) не допустимо. Компилятор тут же выдает ошибку.
2. Обратная всязь в технических системах (часто говорят "отрицательная" обратная связь, - в этом есть определенный смысл, когда речь идет об устойчивости систем) относится к теории автоматического регулирования, - причем здесь "циклические конструкции"? Здесь нет никаких циклов.
3. Использование в алгоритмах так называемых вложенных циклов неминуемо приводит к проблемме N-полноты (т.е. к ситуации, когда такой алгоритм не может быть реализован на вычислительных машинах за разумное время).
О чем Вы толкуете, уважаемый Ysto?
Ваша уверенность обрушила мою.
Сергей Рубцов.
Все-таки нужно учитывать фактор обыденного сознания большинства. Теории нужно соизмерять с возможностями этого большинства воспринимать суррогатные продукты этой теории. Поэтому, как солипсист, считаю, что чем проще, чем линейнее, тем лучше... Например, домохозяйки очень хорошо воспринимают нечеткую логику
Простите, что пишу коротко. Не хочу отнимать время у читателей и дисковое пространство у администратора
«Солипсист?» Значит -- я "недействителен" для С.Рубцова. (Понятно, я «в игноре»…)
И еще...
Ценность возможных теорий построения формальных систем все-таки следует, на мой взгляд, соизмерять с т.з. всевышнего.
Адепт_КАиП
Могу только извиниться в ответ. Какая уж есть "манера", потихоньку привыкните. Тут все - не подарки.
Дмитрий Рябых (Администратор)
Сообщение от Ysto
Очень жаль, такая постановка вопроса не может устроить -- читать явно безграмотные и безобразно составленные предложения противно (или может быть это есть элемент презрения?).
Ну и на десерт Вам, чтобы не зазнавались - "путанность" Вы, видимо, образовали от "путаны", что вносит некоторую путаность в Ваши ясные мысли.
Нагрубил и зазнался… Дурные наклонности, вобщем.
Намек на счет блокирования понял. Упрощаю вам задачу.
Я чувствую, что "не пришелся ко двору", поэтому покидаю данную ветку.
(Теперь свободен :-)&uarr$
(решение является примером формализма неконцептуального. :-)
-
11.12.2005, 16:24 #42
- Регистрация
- 03.12.2005
- Сообщений
- 177
Зря Вы так, никто ничего личного не имел ввиду.
Сообщение от Ysto
Сообщение от Ysto
Сообщение от Ysto
Сообщение от Ysto
Возвращайтесь, пожалуйста.
-
11.12.2005, 19:12 #43
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Ysto
Легко сдаетесь, коллега.
-
11.12.2005, 19:21 #44
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Ysto
-
11.12.2005, 20:44 #45
- Регистрация
- 03.12.2005
- Сообщений
- 177
Сообщение от Евгений
-
11.12.2005, 20:54 #46
- Регистрация
- 24.11.2005
- Сообщений
- 188
Сообщение от Ysto
Сообщение от Ysto
Сообщение от Ysto
Даже, если предположить, что кто-то опровергнет Геделя, то он это сделает по Геделю
-
11.12.2005, 21:27 #47
- Регистрация
- 03.12.2005
- Сообщений
- 177
Сообщение от Сергей_Рубцов
Так зачем игнорировать одно или другое – для первого непротиворечивость, для второго неполнота (развитие, самоприменимость и т.д. слова).
Гедель, имхо, был прав, что говорил только о неполноте (конкретных систем). Это не правы те, кто противопоставлял неполноту и противоречивость. (не) Полнота – это свойство самих множеств (меняются они, заразы), а противоречивость – и множеств и их логической связи. Противоречивость всегда можно устранить в каждом конкретном случае. А расширить можно в любом случае, поэтому неполнота неустранима.
-
12.12.2005, 00:06 #48
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Адепт_КАиП
-
12.12.2005, 00:26 #49
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Адепт_КАиП
"... Геделевский аргумент можно сформулировать как утверждение об алгоритмической невычислимости функции сознания. Невозможно написать программу для машины Тьюринга или любой другой универсальной вычислительной машины, которая была бы способна имитировать работу человеческого мозга и, таким образом, имитировать в любых ситуациях поведение человека. Этот аргумент можно сформулировать и несколько иначе, в виде утверждения, что человек обладает способностью решать алгоритмически неразрешимые проблемы. Эти формулировки, однако, не являются эквивалентными. В самом деле, любая подлинно случайная последовательность является "невычислимой" в том смысле, что никакой алгоритм не позволит нам гарантированно предсказать каждый следующий элемент в этой последовательности. Но отсюда, однако, не следует, что генератор случайных чисел может оказать нам какое-то содействие в решении каких-либо конкретных алгоритмически неразрешимых проблем."
Вопрос о сходимости произвольного итерационного алгоритма открыт, ибо неизвестно завершится ли соответствующий вычислительный процесс машины Тьюринга за конечное время. Это все он, - этот Гедель, со своей теоремой...
-
12.12.2005, 02:00 #50
- Регистрация
- 03.12.2005
- Сообщений
- 177
Сообщение от Евгений
Противоречие у множеств как раз такой локальной полнотой и снимается.
Сообщение от Евгений
Я об этом, по крайней мере, без иллюзий. А неформальное построение, конечно, тоже допускается, только потом на разрешимость все равно проверять :-(
То есть, если алгоритм сходим, то какой он (условия), только об этом речь.
-
12.12.2005, 02:30 #51
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Адепт_КАиП
-
12.12.2005, 20:20 #52
- Регистрация
- 03.12.2005
- Сообщений
- 177
Сообщение от Евгений
Было бы интересно узнать мнение Тимковского В.Г. об этом, он же вроде такими вопросами занимается.
Евгений Борисович, не могли бы Вы ему при случае переслать вопрос "при каких условиях Машина Тьюринга обязательно разрешима и какие основные условия сходимости (или как доказывают сходимость) итерационных алгоритмов".
Думаю, что это имеет отношение к обсуждаемому вопросу.
-
13.12.2005, 12:26 #53
- Регистрация
- 25.11.2005
- Сообщений
- 690
Гери, Джонсон.
Пусть R и R'— два произвольных словарных отношения над
алфавитом 2. Определим полиномиальную сводимость R к R'
в смысле Тьюринга как ОМТ-программу М с входным алфави-
алфавитом 2, такую, что для любой функции g: 2*-»-2*, реализующей
отношение R', релятивизированная программа Mg будет поли-
полиномиальной ОМТ-программой, а функция f^, вычисленная про-
программой Mg, будет реализовывать отношение R. Если # таким
образом сводится к R', то это обозначается следующим образом:
R <xTR' (читается "R сводится к R' по Тьюрингу"). Заметим, что
осг, подобно ос, транзитивно.
Теперь можно определить понятие "NP-трудной" задачи.
Словарное отношение R назовем NP-трудным, если существует
NP-полный язык L (в свою очередь представленный как сло-
словарное отношение описанным выше способом), такой, что
L ос TR. Переборная задача П (при схеме кодирования е) на-
называется NP-трудной, если словарное отношение R [П, е] яв-
является NP-трудным. Неформально можно сказать, что пере-
переборная задача П является NP-трудной, если существует неко-
некоторая ЛФ-полная задача ГГ, которая сводится по Тьюрингу к
задаче П. Нетрудно видеть, что если словарное отношение R
(или переборная задача П) является NP-трудной, то задача П
не может быть решена за полиномиальное время, если Р ф NP.
Заметим, что если R — произвольное NP-трудное словарное
отношение и при этом R сводится по Тьюрингу к словарному
отношению R', то, в силу транзитивности отношения осГ) словар-
словарное отношение R' также должно быть NP-трудным. Более того,
используя соответствие между языками и словарными отноше-
отношениями, а также соответствие между задачами распознавания и
переборными задачами, немедленно получаем, что все NP-пол-
NP-полные языки и все NP-полные задачи являются NP-трудными.
-
13.12.2005, 12:50 #54
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Адепт_КАиП
-
13.12.2005, 12:52 #55
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Сахават
-
13.12.2005, 13:59 #56
- Регистрация
- 25.11.2005
- Сообщений
- 690
Сообщение от Евгений
-
13.12.2005, 15:20 #57
- Регистрация
- 03.12.2005
- Сообщений
- 177
Сообщение от Сахават
А в формальных языках не хватает аксиом, чтобы они были транслируемы. Определение формальности надо менять.
А Вы мне тавтологичные определения предъявляете со сволом "все" :-). Не о том. И вообще неполиномиальность не имеет напрямую к этому отношения.
Просто в "np-трудность", как я поняла, засовывают "все", что не укладывается, поэтому я и считаю его матерным словом :-). Но это еще не значит, что обязательно неразрешимо.
Вы же решаете Np-трудные задачи, и на невычислимость не жалуетесь, пока размерность маленькая.
-
13.12.2005, 16:55 #58
- Регистрация
- 25.11.2005
- Сообщений
- 425
Сообщение от Адепт_КАиП
-
13.12.2005, 17:33 #59
- Регистрация
- 25.11.2005
- Сообщений
- 690
Не в размере дело. Надо очень хитро свести одну задачу в другую так, что результаты не сильно отличались. После решения сведенной задач можно итеративно решить и первичную задачу использую найденные точки опоры, а можно и так оставить, если дельтой можно пренебоечь.
-
13.12.2005, 20:52 #60
- Регистрация
- 03.12.2005
- Сообщений
- 177
Тьфу, вот ей-богу, кто про что, а оптимизаторы про свои эвристики. Говорю же, не о том речь!
"Та самая NP-трудная задача" не не решается, а Вы ее не решаете (из-за экономии времени расчетов) - это совсем другое. Вы не из-за неразрешимости ее не решаете. Не надо путать все в одну кучу, мы здесь не об эвристиках говорим.