Ладно уж, сказал A - говорю B. Правильный вариант складывания вероятностей: P(A | B) = P(A) + P(B) - P(AB), нужно не забыть отнять вероятность того, что A и B пересекаются. В моём примере это только строка "aa". Если подставить всё в формулу, то получим P = 0,5 + 0,5 - 0,25 = 0,75, то есть правильный ответ. Вот вам основы за первый курс
Вообще говоря, для того, чтобы вероятности складывать, события должны быть независимы, а свойство независимости у нас не соблюдено. Рассмотрим простой пример. Пусть в алфавите 2 буквы - "a" и "b". Мы ищем включение слова "a" в последовательностях из 2-х букв, для простоты. Я довожу пример до абсолютного минимума, чтобы не было никаких вопросов (надеюсь). Итак, слово "a" встречается в начале у двух слов - "aa" и "ab", т.е. с веорятностью 0,5. Слово "a" встречается в конце у двух слов - "aa" и "ba", т.е. с вероятностью 0,5. Казалось бы, если поступить как Вы и сложить ответы, то должно получиться 2*0,5 = 1, что было бы весьма абсурдным заявлением. Перечислив все слова явно, мы получим "aa", "ab" и "ba", т.е. 0,75. 1 больше, чем 0,75. Как я и говорил в статье, эта вероятность является завышенной. Надеюсь теперь стало понятно.
Мне потребуется немного времени, чтобы дать вам развёрнутый ответ. Добавлю его в эту ветку комментариев. Пока лишь скажу - перед тем как обвинять кого-то в незнании основ, пожалуйста, убедитесь на 100%, что сами не ошиблись.
Остальное городить к тому, что вы ошиблись. Это сказано и в статье, и в комментариях. Данную ошибку уже совершили несколько людей. Ваш вариант считает некоторые слова по несколько раз, в частности слова, которые содержат fuck 2 и более раз. Так что могу лишь попросить быть внимательнее
Как раз таки нет, Rsa97 не прав. В приблизительном решении слово "fuckfuckfuckfuckfuck" (5 раз, ровно 20 букв) будет учтено 5 раз вместо одного, именно по этой причине приведённая оценка завышена. Дальнейшие рассуждения исключают подсчёт одних и тех же строк несколько раз.
В статье найдена вероятность того, что fuck встретится хотя-бы один раз. На самом деле мне казалось, что и описание, и содержание явно об этом говорят, может быть мне стоило более аккуратно выбирать формулировки. Касательно Вашего предыдущего вопроса про код - на привычной мне Java это было бы str.contains("fuck").
На шаге 2 получена приблизительная формула, и я даже вкратце объяснил почему. Точное значение отличается от приблизительного, пусть и не очень сильно. Пожалуйста, прочитайте немного дальше прежде чем судить, спасибо!
ребята, занимаясь с конструктором, вынуждены искать не технические решения возникшей проблемы, которые как раз и развивают их инженерную мысль, а нужные детальки
Погодите, так разве не ограниченный набор деталей заставляет быть более креативным в инженерных решениях? Я в детстве с одним жалким "ЛИГО" чего только не собирал. Набор деталей в Education серии намеренно делают очень гибким, чтобы что угодно можно быть сделать. А опыт получается из сборок по инструкции, чтобы потом работать уже без неё.
(фу блин, не в той ветке ответил)
Тут нигде нет вложенных доказательств от противного. Есть две посылки в одном доказательстве.
Окей, в доказательстве, которое я привёл, посылка одна.
В рамках исходной посылки, канторовое число сформулировано в форме брадобрея. Его не может существовать не из-за исходной посылки, а из-за формулировки. Поэтому оно ничего не доказывает.
Нет, там приводится вещественное число, удовлетворяющее всем аксиомам вещественных чисел, конструктивно и неоспоримо. Оно существует по построению =) Противоречие возникает не с существованием данного числа, а с существованием соответствующего отображения из R в N.
Метод состоит в оценке вероятности того, что случайный объект из заданного класса удовлетворяет нужному условию. Если доказано, что эта вероятность положительна, то объект с нужными свойствами существует. Хотя доказательство использует вероятности, окончательный вывод делается определённо, без какой-либо неоднозначности.
Говорю же, неуместно.
Существование такого перебора, собственно, и доказывает счётность числа элементов. Существование хоть чего-то несчётного доказать не получится без привлечения абсурдных определений.
Т.е. согласно вашим рассуждениям, вы априори считаете, что все бесконечные множества (которые содержат счётное подмножество) счётны сами по себе. А доказательство несчётности множества вещественных чисел считаете абсурдом, при этом не указав, что именно там абсурдно. Точнее так — вы указали на часть, кажущуюся вам абсурдной, я привёл контраргумент, уточняющий доказательство Кантора, в который вы, кажется, не захотели вдумываться.
Ничего не мешает. Только доказательство Тьюринга разваливается.
Намекаете на специальные завершающие состояния? Их наличие или отсутствие не влияет на исследуемые свойства.
Произвольный объём памяти. Выделенное — это квантор всеобщности, ключевая часть доказательства по индукции.
Стараюсь понять, что вы имеете ввиду. Бесконечная лента и лента заданного неограниченно большого размера — совершенно разные вещи, если вы об этом. Второе — не интересно в рамках проблемы останова.
Докажите.
Из доказательства той же проблемы останова следует, что задача эквивалентности программ тоже неразрешима. Невозможно по программе понять, использует ли она какую-то конкретную "подпрограмму" или нет.
Понятие остановимости не применимо к некорректным программам.
Что такое некорректная программа? Любой набор команд для машины Тьюринга является корректной программой, каким бы бессмысленным он ни был. Машина STOP, кажется вы её так назвали, корректна по построению, если предполагать, что машина HALT существует, что являлось базой доказательства от противного.
Попробую разобраться. Я честно вдумываюсь в то, что вы пишете, поверьте. Итак, Если HALTS существует, то есть противоречие. Значит утверждение "HALTS существует" либо ложно, либо абсурдно, либо неоднозначно.
Полагаю, вы сравниваете такую машину с бородобреем, но немного теряется суть. Существование бородобрея приводит к его несуществованию. Существование же машины HALTS приводит к логическому противоречию, не утверждающему невозможность существования HALTS. И, в отличие от бородобрея, утверждение о несуществовании HALTS к противоречию не приводит, по крайней мере математика таких противоречий до сих пор не знает.
Далее, "абсурдность" и "неоднозначность". Неоднозначности быть не может, так как ложность исключена. Наверное поэтому вы её не упомянули. Остаётся исключить абсурдность.
Итак, есть утверждение: "существует объект, удовлетворяющий данному формальному свойству", которое не может быть истинным. Является ли оно абсурдным? На мой взгляд только в том случае, если его ложность приводит к противоречию. Это самый скользкий момент в ваших рассуждениях, на самом деле, ведь не до конца понятно, что значит "абсурдно" с формальной точки зрения.
Т.е., подводя итог, если исходить из предположения, что непротиворечивость теории алгоритмов в объединении с принятым утверждением о проблеме останова не доказана формально, то выходит, что истинность проблемы останова пока принимать рано, верно? То же касается любых теорем существования. Это определённо любопытный взгляд на математику. Думаю, вам просто сразу следовало сказать, что вы из тех, кто принципиально отрицает доказательства от противного, стало бы проще. В рамках данных убеждений ваш вывод уже имеет больше смысла, но, к сожалению, такая математика оказывается гораздо скучнее, ведь многие теоремы становятся недоказуемыми, или как минимум не имеют известных конструктивных доказательств. Кажется я наконец вас понял.
Тем не менее, то, что вы пишете про счётность множества вещественных чисел, даже при этих допущениях абсолютно неадекватно. При переборе надо доказывать не только то, что перебрали бесконечное множество элементов, а то, что перебрали все элементы. А этого вы не показали.
P.S. Про теорию вероятностей. Думаю вы имеете представление о том, что она строится на теории мер и что значением вероятности являются вещественные числа от 0 до 1. И то, что для непрерывных распределений требуется интегрирование и т.д. Это я к чему? Применять аппарат теории вероятностей к тому, на чём эта теория строится, немного рекурсивно, не находите?
У меня так много вопросов… я опущу обсуждение большей части видео и сосредоточусь на мощности множества вещественных чисел и проблеме останова.
"Опровержение" доказательства Кантора — бред. Доказывать от противного, используя внутри доказательство от противного — абсолютная норма. Почитайте доказательство теоремы Менгера, например, там гораздо менее абстрактно. Плюс у Кантора не доказывается, что есть вещественное число, которое не вещественное. Краткий пересказ настоящего доказательства:
предполагаем, что есть отображение C: R -> N, определённое на всех вещественных чисел и такое, что для разных аргументов результатом будут разные натуральные числа;
строим конкретное вещественное число, основываясь на этом отображении;
доказываем, что отображение C не определено на нём, что приводит к противоречию со свойствами C.
Что вас тут не устроило?
Ваше доказательство того, что вещественных чисел вполне может быть счётное количество — тоже бред. Притягивание за уши теории вероятностей и понятий вроде "мат ожидание" неуместно. На чём строится ваше доказательство в итоге? Перескажу, как я понял: выбирая бесконечное количество раз случайные вещественные числа, мы с вероятностью 1 в итоге выберем каждое из них. Кажется вы это утверждали. НО, осуществлять перебор, например используя мат индукцию, можно только для счётного количества элементов. Откуда тогда взялось число 1, если мера любого счётного подмножества равна 0? Вам формализма в рассуждениях не хватает. Это и доказательством то не назовёшь. Выглядит как "если предположить, что множество счётно, то оно счётно". Окей.
Теперь по поводу Тьюринга. Первое — что мешает выразить троичные ответы через двоичный код и рассматривать именно такой подкласс алгоритмов? Причём тут вообще классическая логика, не понимаю.
Теперь, "существовать он вполне может" — это как? Что значит "бросить ошибку"? Завершение с ошибкой — нормальное свойство машин Тьюринга, если в текущем состоянии не найдена команда, соответствующая символу на ленте. Они только так и завершаются, добавление специального состояния принципиально ничего не поменяет.
Анализатор, проверяющий выход "за границы памяти" — ровно то, что вы описали. Диапазон памяти конечен, алфавит конечен, размер программы конечен. Так что запускаем и ждём либо повторения конфигурации, либо выхода за границы. Один из этих вариантов обязательно случится за конечное время.
Другое дело, что такой анализатор ничем не поможет ввиду неограниченности ленты, о чём вы тоже сказали. Зачем тогда была вся заключительная часть?
"Алгоритм некорректен, так как его поведение зависит от результата работы анализатора" — такое свойство банально невычислимо. Вы тоже стараетесь придумать какой-то хак, ведь вам наверное просто не нравится то, что проблема останова неразрешима.
Да и вообще, завершение с ошибкой == остановка, разве нет. Скажите, какой третий вариант можно добавить к паре "остановится / не остановится"? Число шагов либо конечно, либо бесконечно, третьего быть не может, даже если добавить абсурдные и невозможные утверждения.
Скажите, вы обсуждаемые доказательства из науч-поп источников узнавали или действительно знакомы с их математическими формулировками и формальными доказательствами? Ставлю на то, что вы не сможете мне рассказать, что такое машина Тьюринга.
Извиняюсь за такой большой комментарий, меня просто задевает подобная безграмотность.
Кажется, значение результата сильно преувеличивают. Плюс автор оригинальной статьи явно лукавит — то ему не нужна оригинальная матрица, чтобы найти собственные вектора (это в общем случае являлось бы явной ложью), то уже вдруг матрица должна быть эрмитовой и нужно знать собственные числа минорных матриц, а это значения, явно зависящие от самой матрицы, не только от её собственных чисел.
Как уже было сказано в предыдущих комментариях, многое в статье вводит в заблуждение. Грустно, при большей внимательности к математическим деталям могла бы получиться действительно интересная статья, но вышла, увы, обычная жёлтая пресса.
В вашей версии игры, по какой-то причине, можно переписывать числа в конец даже тогда, когда ещё есть другие доступные ходы. Получается, что у вас другой набор правил, который я никогда не рассматривал. Так что да, при этом условии может существовать более короткое решение, верю.
Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.
Собственно, я так и поступал.
Это, пмсм, не самое верное решение. Так будет найден локальный минимум.
Знаю, именно поэтому после нахождения первого попавшегося решения я перебирал все более короткие ветки, чтобы узнать, не пропустил ли чего. В начале у меня приоритет в очереди был по другому признаку и первым было найдено решение в 86 цифр.
Наверное, нужно было отразить это в тексте, спасибо!
Так у меня и так перебор на очереди с приоритетами) Только не до конца уверен, что имеется ввиду под обрезкой ветвей. Это как если просто ограничить количество ходов?
А что нельзя то, интересная задача! Сходу как решать тоже не знаю, но на досуге подумаю, спасибо!
Ладно уж, сказал A - говорю B. Правильный вариант складывания вероятностей: P(A | B) = P(A) + P(B) - P(AB), нужно не забыть отнять вероятность того, что A и B пересекаются. В моём примере это только строка "aa". Если подставить всё в формулу, то получим P = 0,5 + 0,5 - 0,25 = 0,75, то есть правильный ответ. Вот вам основы за первый курс
Итак.
Вообще говоря, для того, чтобы вероятности складывать, события должны быть независимы, а свойство независимости у нас не соблюдено. Рассмотрим простой пример. Пусть в алфавите 2 буквы - "a" и "b". Мы ищем включение слова "a" в последовательностях из 2-х букв, для простоты. Я довожу пример до абсолютного минимума, чтобы не было никаких вопросов (надеюсь). Итак, слово "a" встречается в начале у двух слов - "aa" и "ab", т.е. с веорятностью 0,5. Слово "a" встречается в конце у двух слов - "aa" и "ba", т.е. с вероятностью 0,5.
Казалось бы, если поступить как Вы и сложить ответы, то должно получиться 2*0,5 = 1, что было бы весьма абсурдным заявлением. Перечислив все слова явно, мы получим "aa", "ab" и "ba", т.е. 0,75.
1 больше, чем 0,75. Как я и говорил в статье, эта вероятность является завышенной. Надеюсь теперь стало понятно.
Мне потребуется немного времени, чтобы дать вам развёрнутый ответ. Добавлю его в эту ветку комментариев.
Пока лишь скажу - перед тем как обвинять кого-то в незнании основ, пожалуйста, убедитесь на 100%, что сами не ошиблись.
Вы посчитали часть слов несколько раз, т.е. ваше вычисление - неточное
Остальное городить к тому, что вы ошиблись. Это сказано и в статье, и в комментариях. Данную ошибку уже совершили несколько людей. Ваш вариант считает некоторые слова по несколько раз, в частности слова, которые содержат fuck 2 и более раз. Так что могу лишь попросить быть внимательнее
Реальная вероятность дана в пункте 3.1, равна 0.00003720064..., вычислена по рекуррентной формуле. Дальше идёт общий случай
Как раз таки нет, Rsa97 не прав. В приблизительном решении слово
"fuckfuckfuckfuckfuck"(5 раз, ровно 20 букв) будет учтено 5 раз вместо одного, именно по этой причине приведённая оценка завышена. Дальнейшие рассуждения исключают подсчёт одних и тех же строк несколько раз.В статье найдена вероятность того, что fuck встретится хотя-бы один раз. На самом деле мне казалось, что и описание, и содержание явно об этом говорят, может быть мне стоило более аккуратно выбирать формулировки.
Касательно Вашего предыдущего вопроса про код - на привычной мне Java это было бы
str.contains("fuck").На шаге 2 получена приблизительная формула, и я даже вкратце объяснил почему. Точное значение отличается от приблизительного, пусть и не очень сильно. Пожалуйста, прочитайте немного дальше прежде чем судить, спасибо!
Погодите, так разве не ограниченный набор деталей заставляет быть более креативным в инженерных решениях? Я в детстве с одним жалким "ЛИГО" чего только не собирал. Набор деталей в Education серии намеренно делают очень гибким, чтобы что угодно можно быть сделать. А опыт получается из сборок по инструкции, чтобы потом работать уже без неё.
(фу блин, не в той ветке ответил)
Окей, в доказательстве, которое я привёл, посылка одна.
Нет, там приводится вещественное число, удовлетворяющее всем аксиомам вещественных чисел, конструктивно и неоспоримо. Оно существует по построению =) Противоречие возникает не с существованием данного числа, а с существованием соответствующего отображения из R в N.
Метод состоит в оценке вероятности того, что случайный объект из заданного класса удовлетворяет нужному условию. Если доказано, что эта вероятность положительна, то объект с нужными свойствами существует. Хотя доказательство использует вероятности, окончательный вывод делается определённо, без какой-либо неоднозначности.
Говорю же, неуместно.
Т.е. согласно вашим рассуждениям, вы априори считаете, что все бесконечные множества (которые содержат счётное подмножество) счётны сами по себе. А доказательство несчётности множества вещественных чисел считаете абсурдом, при этом не указав, что именно там абсурдно. Точнее так — вы указали на часть, кажущуюся вам абсурдной, я привёл контраргумент, уточняющий доказательство Кантора, в который вы, кажется, не захотели вдумываться.
Напомните, в каком месте оно разваливается?
Намекаете на специальные завершающие состояния? Их наличие или отсутствие не влияет на исследуемые свойства.
Стараюсь понять, что вы имеете ввиду. Бесконечная лента и лента заданного неограниченно большого размера — совершенно разные вещи, если вы об этом. Второе — не интересно в рамках проблемы останова.
Из доказательства той же проблемы останова следует, что задача эквивалентности программ тоже неразрешима. Невозможно по программе понять, использует ли она какую-то конкретную "подпрограмму" или нет.
Что такое некорректная программа? Любой набор команд для машины Тьюринга является корректной программой, каким бы бессмысленным он ни был. Машина STOP, кажется вы её так назвали, корректна по построению, если предполагать, что машина HALT существует, что являлось базой доказательства от противного.
Попробую разобраться. Я честно вдумываюсь в то, что вы пишете, поверьте. Итак, Если HALTS существует, то есть противоречие. Значит утверждение "HALTS существует" либо ложно, либо абсурдно, либо неоднозначно.
Полагаю, вы сравниваете такую машину с бородобреем, но немного теряется суть. Существование бородобрея приводит к его несуществованию. Существование же машины HALTS приводит к логическому противоречию, не утверждающему невозможность существования HALTS. И, в отличие от бородобрея, утверждение о несуществовании HALTS к противоречию не приводит, по крайней мере математика таких противоречий до сих пор не знает.
Далее, "абсурдность" и "неоднозначность". Неоднозначности быть не может, так как ложность исключена. Наверное поэтому вы её не упомянули. Остаётся исключить абсурдность.
Итак, есть утверждение: "существует объект, удовлетворяющий данному формальному свойству", которое не может быть истинным. Является ли оно абсурдным? На мой взгляд только в том случае, если его ложность приводит к противоречию. Это самый скользкий момент в ваших рассуждениях, на самом деле, ведь не до конца понятно, что значит "абсурдно" с формальной точки зрения.
Т.е., подводя итог, если исходить из предположения, что непротиворечивость теории алгоритмов в объединении с принятым утверждением о проблеме останова не доказана формально, то выходит, что истинность проблемы останова пока принимать рано, верно? То же касается любых теорем существования. Это определённо любопытный взгляд на математику. Думаю, вам просто сразу следовало сказать, что вы из тех, кто принципиально отрицает доказательства от противного, стало бы проще. В рамках данных убеждений ваш вывод уже имеет больше смысла, но, к сожалению, такая математика оказывается гораздо скучнее, ведь многие теоремы становятся недоказуемыми, или как минимум не имеют известных конструктивных доказательств. Кажется я наконец вас понял.
Тем не менее, то, что вы пишете про счётность множества вещественных чисел, даже при этих допущениях абсолютно неадекватно. При переборе надо доказывать не только то, что перебрали бесконечное множество элементов, а то, что перебрали все элементы. А этого вы не показали.
P.S. Про теорию вероятностей. Думаю вы имеете представление о том, что она строится на теории мер и что значением вероятности являются вещественные числа от 0 до 1. И то, что для непрерывных распределений требуется интегрирование и т.д. Это я к чему? Применять аппарат теории вероятностей к тому, на чём эта теория строится, немного рекурсивно, не находите?
У меня так много вопросов… я опущу обсуждение большей части видео и сосредоточусь на мощности множества вещественных чисел и проблеме останова.
"Опровержение" доказательства Кантора — бред. Доказывать от противного, используя внутри доказательство от противного — абсолютная норма. Почитайте доказательство теоремы Менгера, например, там гораздо менее абстрактно. Плюс у Кантора не доказывается, что есть вещественное число, которое не вещественное. Краткий пересказ настоящего доказательства:
Что вас тут не устроило?
Ваше доказательство того, что вещественных чисел вполне может быть счётное количество — тоже бред. Притягивание за уши теории вероятностей и понятий вроде "мат ожидание" неуместно. На чём строится ваше доказательство в итоге? Перескажу, как я понял: выбирая бесконечное количество раз случайные вещественные числа, мы с вероятностью 1 в итоге выберем каждое из них. Кажется вы это утверждали. НО, осуществлять перебор, например используя мат индукцию, можно только для счётного количества элементов. Откуда тогда взялось число 1, если мера любого счётного подмножества равна 0? Вам формализма в рассуждениях не хватает. Это и доказательством то не назовёшь. Выглядит как "если предположить, что множество счётно, то оно счётно". Окей.
Теперь по поводу Тьюринга. Первое — что мешает выразить троичные ответы через двоичный код и рассматривать именно такой подкласс алгоритмов? Причём тут вообще классическая логика, не понимаю.
Теперь, "существовать он вполне может" — это как? Что значит "бросить ошибку"? Завершение с ошибкой — нормальное свойство машин Тьюринга, если в текущем состоянии не найдена команда, соответствующая символу на ленте. Они только так и завершаются, добавление специального состояния принципиально ничего не поменяет.
Анализатор, проверяющий выход "за границы памяти" — ровно то, что вы описали. Диапазон памяти конечен, алфавит конечен, размер программы конечен. Так что запускаем и ждём либо повторения конфигурации, либо выхода за границы. Один из этих вариантов обязательно случится за конечное время.
Другое дело, что такой анализатор ничем не поможет ввиду неограниченности ленты, о чём вы тоже сказали. Зачем тогда была вся заключительная часть?
"Алгоритм некорректен, так как его поведение зависит от результата работы анализатора" — такое свойство банально невычислимо. Вы тоже стараетесь придумать какой-то хак, ведь вам наверное просто не нравится то, что проблема останова неразрешима.
Да и вообще, завершение с ошибкой == остановка, разве нет. Скажите, какой третий вариант можно добавить к паре "остановится / не остановится"? Число шагов либо конечно, либо бесконечно, третьего быть не может, даже если добавить абсурдные и невозможные утверждения.
Скажите, вы обсуждаемые доказательства из науч-поп источников узнавали или действительно знакомы с их математическими формулировками и формальными доказательствами? Ставлю на то, что вы не сможете мне рассказать, что такое машина Тьюринга.
Извиняюсь за такой большой комментарий, меня просто задевает подобная безграмотность.
Кажется, значение результата сильно преувеличивают. Плюс автор оригинальной статьи явно лукавит — то ему не нужна оригинальная матрица, чтобы найти собственные вектора (это в общем случае являлось бы явной ложью), то уже вдруг матрица должна быть эрмитовой и нужно знать собственные числа минорных матриц, а это значения, явно зависящие от самой матрицы, не только от её собственных чисел.
Как уже было сказано в предыдущих комментариях, многое в статье вводит в заблуждение. Грустно, при большей внимательности к математическим деталям могла бы получиться действительно интересная статья, но вышла, увы, обычная жёлтая пресса.
В вашей версии игры, по какой-то причине, можно переписывать числа в конец даже тогда, когда ещё есть другие доступные ходы. Получается, что у вас другой набор правил, который я никогда не рассматривал. Так что да, при этом условии может существовать более короткое решение, верю.
Собственно, я так и поступал.
Знаю, именно поэтому после нахождения первого попавшегося решения я перебирал все более короткие ветки, чтобы узнать, не пропустил ли чего. В начале у меня приоритет в очереди был по другому признаку и первым было найдено решение в 86 цифр.
Наверное, нужно было отразить это в тексте, спасибо!