TOPIC: Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
20 Март 2011 19:53 #151
Serge_P написал(а):
фиксированная последовательность неслучайна, если она обладает каким-нибудь свойством, которое для настоящей случайной последовательности (т.е., для того объекта, который определяется в современной теории вероятностей) выполняется с вероятностью 0.
Не врубился - какие свойства случайной последовательности могут выполнятся с вероятностью бОльше 0, а какие не?
А иначе почти все (с вероятностью 1) двоичные (бесконечные) последовательности нельзя определить/застукать ни словами, ни формулами, ни алгоритмами. Тем не менее и несмотря на их изобилие, НЕ можем указать на ни одну такую последовательность
, потому что не знаем какой чередой уходит в бесконечность. Если бы знали, последовательность была бы определимой (definable) словами или формулами или алгоритмами. Смотря на любой начальный отрезок, нельзя сказать будет ли ВСЯ последовательность определимой словами или формулами или алгоритмами, потому что любой конечный начальный участок уже (по определению) определим
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
20 Март 2011 20:46 #152
Serge_P написал(а):
говорит, что случайных последовательностей может и не быть
Сам автор оговаривается, что не специалист в матлогике (me - too
), хотя и ссылается на счётные модели теории множеств вслед за теоремой Лёвенгейма-Скулема. Может, если нет несчётных множеств, все последовательности оказываются определимыми (definable) словами или формулами или алгоритмами
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
20 Март 2011 22:54 #153
Хайдук написал(а):
Не врубился - какие свойства случайной последовательности могут выполнятся с вероятностью бОльше 0, а какие не?
Ну например, то, что пропорция единиц стремится к 1/2 - имеет вероятность 1, а то, что стремится еще куда-нибудь (иль вообще никуда не стремится) - вероятность 0 (имеется в виду, что 0 и 1 выпадают с вероятностью 1/2, и независимо).
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
23 Март 2011 01:24 #154
Serge_P написал(а):
пропорция единиц стремится к 1/2 - имеет вероятность 1, а то, что стремится еще куда-нибудь (иль вообще никуда не стремится) - вероятность 0 (имеется в виду, что 0 и 1 выпадают с вероятностью 1/2, и независимо).
Это да, но мне кажется, что под случайностью (бинарной) последовательности мерещится (ибо в конечном счёте строго застукать не удаётся) что-то другое. Последовательность 0101010101.... удовлетворяет пропорции 1/2, но назвать случайной не поворачивается язык
. Также многие из остальных, различных от 1/2 пропорций, вполне могли бы удовлетворять другим случайным вероятностным распределениям, отличным от 1/2. По-видимому, нельзя согласовать определение вероятности как меру статистики с интуитивной случайностью почти всех неалгоритмических (бесконечных) последовательностей, коих несчётно много. Это попросту разные концепции/представления
Таким образом вероятность набрести на случайную неалгоритмическую последовательность оказывается полной, 1, за вычетом лишь счётно-бесконечного числа конечных и бесконечных алгоритмических последовательностей, чья вероятность/мера равна 0 по причине их счётности, конечно. Ирония состоит в том, что - отныне и во веки веков - мы сможем узнать и записать только последовательности из ... второй группы вероятности 0
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
23 Март 2011 02:04 #155
Alexander написал(а):
что имеете ввиду под мера на множествах всяких статистических событий
Статистические события это те, что могут (или не) произойти со временем или встретиться (или не) вдоль пространства. Если частота их происхождения/встречания тяготеет к устойчивой (тем лучше, чем бОльше происхождений/встречаний), то таким событиям можно присобачить положительную числовую (между 0 и 1, включительно) меру/вероятность, совпадающую с частотой происхождений/встречаний. Равномерная мера/вероятность такая совпадает с мерой Лебега на единичном отрезке [0,1] прямой обычных действительных чисел. Таким образом оказываются осмысленными и мера/вероятности непрерывного континуума событий, скажем попаданий наугад карандашом в точки отрезка или плоскости.
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
23 Март 2011 13:06 #156
Хайдук написал(а):
Это да, но мне кажется, что под случайностью (бинарной) последовательности мерещится (ибо в конечном счёте строго застукать не удаётся) что-то другое. Последовательность 0101010101.... удовлетворяет пропорции 1/2, но назвать случайной не поворачивается язык
Немножко не так: там случайная последовательность должна обладать всеми свойствами (подразумевается, всеми, которые можно сформулировать), которые выполняются с вероятностью 1. Т.е., не только пропорция единиц должна стремится к 1/2, но и пропорция, скажем, 11 должна стремится к 1/4, и т.д. (это называется нормальность). Еще должен быть выполнен, к примеру, закон повторного логарифма, и т.п.
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
23 Март 2011 13:49 #157
Сколько известно таких формулируемых свойств, выполняющихся с вероятностью 1? Можно ли в принципе увеличить эффективно/алгоритмически их число до счётного? Множество анти-свойств этим свойствам будет довольствоваться мерой/вероятностью 0, конечно
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
23 Март 2011 15:17 #158
Хайдук написал(а):
Сколько известно таких формулируемых свойств, выполняющихся с вероятностью 1?
Множество таковых счетно. Не больше и не меньше.
Оно не более чем счетно, потому что букв и символов конечное число, и под сформулировать свойство подразумевается записать его в виде конечной последовательности букв и символов.
Оно не менее чем счетно, потому что достаточно рассмотреть свойства типа асимптотическая пропорция строк 111...111 (n раз) равна 1/2^n.
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
24 Март 2011 01:00 #160
Я вроде запутался и не уверен в чёткости башки
. Можно ли утверждать, что счётное множество формулируемых свойств покрывает ВСЕ конечные последовательности, которых тоже счётное (!) число? Как-бы выходит, что конечные последовательности делятся на 2 класса эквивалентности: настоящие случайные с мерой 1 и с проколами случайности меры 0
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
24 Март 2011 15:14 #161
Хайдук написал(а):
Я вроде запутался и не уверен в чёткости башки
Это нормальное состояние, когда пытаешься понять продвинутые книги/статьи по матлогике
Хайдук написал(а):
Можно ли утверждать, что счётное множество формулируемых свойств покрывает ВСЕ конечные последовательности, которых тоже счётное (!) число?
В принципе да, но непонятно, что значит множество формулируемых свойств покрывает ВСЕ конечные последовательности? Определение в статье - строго для бесконечных последовательностей. Если имеется в виду, что заданная конечная последовательность находится в начале бесконечной - то тогда вероятность этого строго между 0 и 1, и поэтому к случайности/неслучайности (в смысле этого определения) отношения вообще не имеет. Если имеется в виду, что заданная конечная последовательность просто где-нибудь в бесконечной содержится - то да, случайная последовательность должна таким свойством обладать.
Хайдук написал(а):
Как-бы выходит, что конечные последовательности делятся на 2 класса эквивалентности: настоящие случайные с мерой 1 и с проколами случайности меры 0
Этого не понял: про конечные последовательности в статье вообще речь не идет.
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
25 Март 2011 02:38 #162
Serge_P написал(а):
Это нормальное состояние, когда пытаешься понять продвинутые книги/статьи по матлогике
Полагаю, что я даже не достучался до матлогики в статье
Сколько таких последовательностей, кто обладают вероятностой мерой 0 ? В статье указано, что последовательности типа 00a00b00c00d00е неслучайны и их несчётно много (a, b, c, d, е кто такие?).
Что будет, если для бинарных последовательностей 0 и 1 не равновероятны?
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
26 Март 2011 02:56 #164
Serge_P написал(а):
Такие последовательности (00a00b00c00d00е...) неслучайны хотя бы потому, что доля единиц не больше 1/3
Как неслучайность таких последовательностей собачится с сингулярной мерой, скажем, 1/4 для единиц и 3/4 для нулей (в смысле, что доля нулей и единиц различна от 50:50)?
Какой дурак все-таки этот Gregory Chaitin
, насколько все сложнее и тоньше его алгоритмически невычислимых последовательностей. Даже многие вполне детерминированные неким алгоритмом последовательности типа е и
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
26 Март 2011 15:02 #166
Хайдук написал(а):
Как неслучайность таких последовательностей собачится с сингулярной мерой, скажем, 1/4 для единиц и 3/4 для нулей (в смысле, что доля нулей и единиц различна от 50:50)?
Ну, такая последовательность будет неслучайной по отношению к мере с любым p (= вероятность единицы). Хотя бы потому, что пропорция единиц должна стремится к p если считать, скажем, только то, что стоит на позициях 1,4,7,10,13,...
Хайдук написал(а):
Может в счётных моделях теории множеств теории вероятностей вообще ... не бывает вслед за везде равной нулю мерой
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
26 Март 2011 23:06 #167
Serge_P написал(а):
такая последовательность будет неслучайной по отношению к мере с любым p (= вероятность единицы). Хотя бы потому, что пропорция единиц должна стремится к p если считать, скажем, только то, что стоит на позициях 1,4,7,10,13,...
Мне мерещится, что долю 1-иц можно приурочить к какой угодно не бОльшей, чем 1/3 (для a00b00c00d00e... !), хотя все равно эти два 00 нуля вперемежку угробят малину случайности
. Должно быть просто вычислить какой должна быть обычная вероятность 1-иц лишь для позиций 1,4,7,10,13,..., дабы доля их для a00b00c00d00e... была любой не бОльшей 1/3. Интересно можно ли 2 дежурных нуля застукать статистическим экспериментом, подразумевая любую, не бОльшую 1/3 вероятность 1-иц?
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
26 Март 2011 23:28 #168
Хайдук написал(а):
Мне мерещится, что долю 1-иц можно приурочить к какой угодно не бОльшей, чем 1/3 (для a00b00c00d00e... !), хотя все равно эти два 00 нуля вперемежку угробят малину случайности
. Должно быть просто вычислить какой должна быть обычная вероятность 1-иц лишь для позиций 1,4,7,10,13,..., дабы доля их для a00b00c00d00e... была любой не бОльшей 1/3. Интересно можно ли 2 дежурных нуля застукать статистическим экспериментом, подразумевая любую, не бОльшую 1/3 вероятность 1-иц?
Ну ясно что последовательность a00b00c00d00e... не случайна, чего тут обсуждать.
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
27 Март 2011 00:29 #170
Хайдук написал(а):
А как можно это доказать/обнаружить для в меру длинной такой последовательности, не зная наперёд о чередовании двух нулей?
Ну а вот тут мы опять возвращаемся к
Serge_P написал(а):
Вообще, в отличие от вопроса насколько данная конечная последовательность похожа на случайную (который имеет огромное практическое значение и про который написаны толстые книги), аналогичный вопрос о бесконечной последовательности имеет, скорее, философский интерес (ну значит, ежели делать нечего, то можно и его обсудить
).
Определение из статьи имеет смысл только для бесконечных последовательностей, т.е., там предполагается, что вся последовательность (до бесконечности) уже задана, и мы уже все знаем наперед. Например, из их определения легко следует, что если взять случайную последовательность и приписать ей в начало миллион единиц, то эта последовательность будет продолжать быть случайной (хотя практически будет трудновато в это поверить).
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
27 Март 2011 01:27 #171
Serge_P написал(а):
Определение из статьи имеет смысл только для бесконечных последовательностей, т.е., там предполагается, что вся последовательность (до бесконечности) уже задана, и мы уже все знаем наперед.
Я, несомненно, сплошь и рядом путаю конечные последовательности с бесконечными
, но мне трудно представить как по-настоящему случайная бесконечная последовательность может быть задана наперёд, за исключением, может быть, хороших знакомых типа е и
, о которых, кстати, наперёд ... не знаем ничего и как раз потому такие последовательности могут обернуться случайными. Как-то напрашивается, что любой начальный участок должен удовлетворять всем признакам случайности по теории вероятностей
Serge_P написал(а):
из их определения легко следует, что если взять случайную последовательность и приписать ей в начало миллион единиц, то эта последовательность будет продолжать быть случайной
За счёт чего такое сойдёт, как увязать с вероятностной мерой?
А говорить о невычислимых последовательностях попросту ... нельзя, на то они и невычислимые/неопределимые словами или каким-либо образом
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
27 Март 2011 12:01 #172
Хайдук написал(а):
но мне трудно представить как по-настоящему случайная бесконечная последовательность может быть задана наперёд,
мне тоже трудно представить. Но вот как-то математики уже свыклись с мыслью, что бесконечная последовательность существует как единое целое.
Хайдук написал(а):
за исключением, может быть, хороших знакомых типа е и пи, о которых, кстати, наперёд ... не знаем ничего
Кое-что знаем: например, что цифирки не войдут в период
Хайдук написал(а):
и как раз потому такие последовательности могут обернуться случайными.
Это вряд-ли: они вычислимы. Если Вы играете с кем-то в угадай число, и Ваш соперник уже загадал 3, 1, 4, 1, 5, 9, 2, то, я думаю, следующее число будет угадано с вероятностью несколько большей, чем 1/10
Хайдук написал(а):
Как-то напрашивается, что любой начальный участок должен удовлетворять всем признакам случайности по теории вероятностей
Теория вероятностей признаками случайности вообще не занимается; это надо читать другие умные книги (например, [3] из статьи).
Хайдук написал(а):
Serge_P написал(а):
из их определения легко следует, что если взять случайную последовательность и приписать ей в начало миллион единиц, то эта последовательность будет продолжать быть случайной
За счёт чего такое сойдёт, как увязать с вероятностной мерой?
Grosso modo, потому что добавление любого конечного куска в начало не может порушить свойство, которое выполняется с вероятностью 0 или 1.
Хайдук написал(а):
А говорить о невычислимых последовательностях попросту ... нельзя,
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
27 Март 2011 16:59 #173
Serge_P написал(а):
как-то математики уже свыклись с мыслью, что бесконечная последовательность существует как единое целое... добавление любого конечного куска в начало не может порушить свойство, которое выполняется с вероятностью 0 или 1
Разумеется, должен был прикинуть
. Тут попросту экстраполируют меру с длинных последовательностей на подобные бесконечные, а последних любые конечные перегибы не колышут
Serge_P написал(а):
они вычислимы. Если Вы играете с кем-то в угадай число, и Ваш соперник уже загадал 3, 1, 4, 1, 5, 9, 2, то, я думаю, следующее число будет угадано с вероятностью несколько большей, чем 1/10
А что может помешать любой супер-пупер случайной последовательности в один прекрасный день оказаться вычислимой? Где гарантия тому, что конкретная серия из 1000 бросаний копеечки не окажется двоичным развитием некоего вычислимого иррационального числа вроде корня из 2? Кстати, оно почти так и есть - любая серия бросаний даёт нам приближение к беснесчётному числу действительных чисел на отрезке [0,1].
Тут напрашивается аналогия с динамическим хаосом. Отличить вычислимые от невычислимых последовательностей по рылу, так сказать, вроде никак нельзя, не говоря уж о ... неизмеримых (вероятностью) последовательностей, коих континнуум, нет?
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
28 Март 2011 03:01 #177
Serge_P написал(а):
множество вычислимых последовательностей счетно, а вероятность попасть в любое фиксированное счетное множество равна нулю.
Хитрый ответ
. По мне, вычислимость и вероятностная мера (вкупе со статистикой) довольно разные идеи и друг друга не очень колышут. Фактические статистические последовательности всегда конечные и значит вычислимые ... постфактум. Для существования осмысленной и полезной меры на статистических событиях совершенно безразлично вычислимы ли они в смысле однозначной физической детерминированности/причинности/эволюции или не (пример последнему служит квантовая механика, конечно).
К сожалению забыл как точно называют класс действительных чисел, которые НЕ вычислимы в смысле е и
, но тем не менее можно узнать сколь угодно цифр после запятой. Как раз таковым числом самовлюблённый Chaitin
состряпал свою Омегу, якобы выражающую вероятность остановки случайно выбранной компьютерной программы. Вдали от сомнительной осмысленности такой вероятности вообще, само число определяется монотонно возрастающим и ограниченным 1-цей рядом, чем обеспечивается его сходимость. Число невычислимо в том смысле, что - в отличие от известных аппроксимаций для е и
- не можем быть уверены насколько близко подошли к настоящему значению/пределу
. Можем лишь оценить отстояние до потолка 1, чем и фиксируем цифры после запятой. Ниже ли настоящее значение Омеги потолка и насколько сказать совершенно невозможно ввиду невычислимости этого настоящего значения. Благо все-таки можем вычислить некоторые нижние оценки.
