24 декабря Архивач восстановлен после серьёзной аварии. К сожалению, значительная часть сохранённых изображений и видео была потеряна. Подробности случившегося. Мы призываем всех неравнодушных помочь нам с восстановлением утраченного контента!
Сразу скажу, я не математик. Но хотелось бы обсудить теорему Геделя о неполноте.
Начал читать книгу "Эдер, Гедель, Бах" и попытался решить приведенную там головоломку. Пересказываю кратко: Дана последовательность символов MI. Нужно превратить последовательность в MU, следуя 4м правилам: 1) Если последняя буква последовательности I - можно добавить одну U в конец (MII -> MIIU, например) 2) Mx -> Mxx. То есть, имея MU можно сделать MUU, MIU -> MIUIU и тд. 3) Последовательность III может быть заменена U. MIIII -> MIU или MUI. 4) Любое кол-во U подряд может быть сокращено до одной U. MUUU -> MU.
Если кто-то будет решать, то не читайте спойлер.
Сначала я таки засел с листиком, стал прикидывать варианты. Но спустя время интуиция стала подсказывать, что задача не имеет решения. Еще спустя время я нашел вполне простое доказательство, что задача не разрешима и охуел от мощи абстракций
Уже зная, что теорема геделя упоминается как теорема о неразрешимости, я понял, что речь в книге пойдет о неразрешимых системах и возможности это доказать
Дропнул я читать на этом месте и задумался, есть ли способ доказать, имеет ли решение какая-либо данная задача. Ведь это же охуенно. Это ведь открытие уровня Крика (ДНК) или даже еще более крутое. Раз есть способ доказать, что задача неразрешима, то можно быстро узнать, решаема ли задача. Уже можно вывести "философские" выводы о бесконечности прогресса. И, мне кажется, с развитием выч. мощностей и уровня "комп. знаний", следствия этой теоремы станут еще более важными
С другой стороны, имхо, эта задача с трудом решается (или вообще не решается) компуктером и относительно легко человеком. Вот интересно, почему так. Когда комп начнет решать такие задачи, можно говорить о ИИ, а пока весь этот МАШИН ЛЕРНИНГ - примитив, ничего общего с интеллектом не имеющий.
>>146042240 (OP) Спойлер не читал. Хуй знает, мне кажется задача не разрешима. С помочью второго правила из первоначальной последовательности можно получить только последовательность с количеством I степени двойки (2, 4 и т.д.) в то время как U можно сделать только из трех I, то есть всегда будет оставаться либо 1 либо 2 буквы I, добавление U в конец ничего не даст, а чередование U и I не имеет смысла. Как это через теорему Геделя обосновать не ебу вообще. Самый годный тред за последнее время. Бамп.
>>146042240 (OP) > Дропнул я читать на этом месте и задумался, есть ли способ доказать, имеет ли решение какая-либо данная задача. Если ты говоришь о полиномиальном алгоритме резрешимости конкретной задачи, то такого нет и почти точно не будет. Т.к. из этого алгоритма очевидным образом следует равенство классов P=NP. Их равенство разрушит наш современный мир.
>>146048284 >P=NP. Их равенство разрушит наш современный мир. что ты такое говоришь, анон? Поподробнее это говно можешь нарезать? Я быдлан, но тянусь к свету.
>>146042240 (OP) ты же понимаешь разницу между отсутствием последовательности преобразований переводящих одну строку в другую и невозможности доказательства ее существования?
>>146048387 Загугли, это открытая проблема. Кратко говоря, вопрос состоит в том, является ли любая не полиномиальная задача (например разложение достаточно большого числа на простые множители или хотя бы доказательство простоты) выполнимой за полиномиальное время (то есть сложность реализуемого алгоритма не превосходит полинома от размера входных данных). Из равенства следует разрешимость любой задачи за "быстрое" время, следовательно вся криптография мира пойдет по пизде, если свести задачу о факторизации числа к полиномиальной.
Начал читать книгу "Эдер, Гедель, Бах" и попытался решить приведенную там головоломку.
Пересказываю кратко:
Дана последовательность символов MI. Нужно превратить последовательность в MU, следуя 4м правилам:
1) Если последняя буква последовательности I - можно добавить одну U в конец (MII -> MIIU, например)
2) Mx -> Mxx. То есть, имея MU можно сделать MUU, MIU -> MIUIU и тд.
3) Последовательность III может быть заменена U. MIIII -> MIU или MUI.
4) Любое кол-во U подряд может быть сокращено до одной U. MUUU -> MU.
Если кто-то будет решать, то не читайте спойлер.
Сначала я таки засел с листиком, стал прикидывать варианты. Но спустя время интуиция стала подсказывать, что задача не имеет решения. Еще спустя время я нашел вполне простое доказательство, что задача не разрешима и охуел от мощи абстракций
Уже зная, что теорема геделя упоминается как теорема о неразрешимости, я понял, что речь в книге пойдет о неразрешимых системах и возможности это доказать
Дропнул я читать на этом месте и задумался, есть ли способ доказать, имеет ли решение какая-либо данная задача. Ведь это же охуенно. Это ведь открытие уровня Крика (ДНК) или даже еще более крутое. Раз есть способ доказать, что задача неразрешима, то можно быстро узнать, решаема ли задача. Уже можно вывести "философские" выводы о бесконечности прогресса. И, мне кажется, с развитием выч. мощностей и уровня "комп. знаний", следствия этой теоремы станут еще более важными
Меня в какие-то дебри понесло?
Что сами думаете, аноны?