Сразу скажу, я не математик. Но хотелось бы обсудить теорему Геделя о неполноте.Начал читать книгу "Эдер, Гедель, Бах" и попытался решить приведенную там головоломку.Пересказываю кратко:Дана последовательность символов 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)а как тебе теорема Гудстейна?
>>146043293Только услышал, интересноИ чому я раньше математикой не увлекался особо.
Какая-то бесполезная хуйня
>>146045339Ясно.
>>146042240 (OP)Ну и нахуя ты сюда это притащил, я слишком тупой для этого дерьма.
>>146042240 (OP)Спойлер не читал. Хуй знает, мне кажется задача не разрешима. С помочью второго правила из первоначальной последовательности можно получить только последовательность с количеством I степени двойки (2, 4 и т.д.) в то время как U можно сделать только из трех I, то есть всегда будет оставаться либо 1 либо 2 буквы I, добавление U в конец ничего не даст, а чередование U и I не имеет смысла. Как это через теорему Геделя обосновать не ебу вообще. Самый годный тред за последнее время. Бамп.
Бамп
>>146046128Браво, все так.
Тоже бпобампаю.
>>146042240 (OP)Сначала показалось, что решить нельзя, но потом вот это очень сильно смутило.>MIU или MUIНужно уточнить правила перестановки.
>>146042240 (OP)3/4 философии Гегеля состоит из бессмыслицы, а оставшаяся треть - из продажных идей. Вот тебе и теорема.
>>146047579>третьМожет четверть?
>>146047579а про бабеля что скажешь?
>>146047736Да.>>146047749Что фамилия хуевая.
>>146047579Пруфы
>>146047579Твой пост состоит из бессмыслицы. Ха!
>>146042240 (OP)> Дропнул я читать на этом месте и задумался, есть ли способ доказать, имеет ли решение какая-либо данная задача.Если ты говоришь о полиномиальном алгоритме резрешимости конкретной задачи, то такого нет и почти точно не будет. Т.к. из этого алгоритма очевидным образом следует равенство классов P=NP. Их равенство разрушит наш современный мир.
>>146048284>P=NP. Их равенство разрушит наш современный мир.что ты такое говоришь, анон? Поподробнее это говно можешь нарезать? Я быдлан, но тянусь к свету.
>>146042240 (OP)ты же понимаешь разницу между отсутствием последовательности преобразований переводящих одну строку в другую и невозможности доказательства ее существования?
>>146048284Это не радует, конечно.
>>146048387Загугли, это открытая проблема. Кратко говоря, вопрос состоит в том, является ли любая не полиномиальная задача (например разложение достаточно большого числа на простые множители или хотя бы доказательство простоты) выполнимой за полиномиальное время (то есть сложность реализуемого алгоритма не превосходит полинома от размера входных данных). Из равенства следует разрешимость любой задачи за "быстрое" время, следовательно вся криптография мира пойдет по пизде, если свести задачу о факторизации числа к полиномиальной.
>>146048836prime in p уже 15 лет как.
>>146048387http://www.scottaaronson.com/papers/pnp.pdf
>>146048836Этим можно вайпать /b/.
>>146048967Не знал, спасибо. Почему то казалось что тесты на простоту все еще не полиномиальны.
>>146049451факторизация нет, а простота - тот же aks, может с тех пор еще что-то придумали, честно говоря не следил.
>>146042240 (OP)Спасибо, братан！Уже договорился со знакомым о патенте, завтра будем оформлять.
>>146049715На что потент то?
>>146049715Ты импотент что ли?
Bump
