Случайные последовательности

[sun-stream.livejournal.com]

В детстве читала в энциклопедии (скорее всего, в книге "Я познаю мир: математика"), что человек не может придумать полностью случайную последовательность из нулей и единиц. Понятно, что такая последовательность может быть только псевдослучайной, но вопрос заключается в другом. В книге было сказано также, что если человек будет достаточно долго называть играющей с ним программе первое число, которое взбредёт в голову - нуль или единицу - то рано или поздно программа распознает закономерности, которым подчиняется полученная последовательность, и будет со стопроцентной вероятностью угадывать, какую цифру игрок назовет следующей. Действительно ли это так? Реализован ли уже подобный алгоритм?

Comments

[von-stuck.livejournal.com]

Мне кажется, вопрос скорее из области философии и религии, нежели математики. Если вы верите в свободу воли, значит не верите в такую машину. Если же вы детерминист - значит, ваши действия это просто сложная программа, где невозможны случайности, и умная вычислительная машина может "просчитать" вас.

[cass1an.livejournal.com]

Речь вовсе не о случайностях. В "человеческой" последовательностях случайных чисел, например, обычно реже встречаются и короче последовательности из одинаковых цифр подряд. Человек воспринимает в этом какой-то порядок и не считает случайностью.

[sun-stream.livejournal.com]

Вы опередили меня. Именно об этом и хотела написать. Да, так и есть.

[dendrr.livejournal.com]

Можно обобщить - в "человеческой" последовательности не будет циклов, как "0000" и "1111", так и "101010", "011011011" и т.п. Чисто психологически человек будет стараться эти циклы разбивать. То есть когда циклы начинают "проступать", то следующий элемент становится проще угадывать: после "0110110", вероятнее всего, последует не "единица", а "ноль". (Истинно случайный алгоритм же должен давать равновероятно обе цифры.) Полностью же, конечно, предугадать не выйдет.

[cass1an.livejournal.com]

Почему не будет? Длинных не будет совсем, а короткие-то вполне возможно. Другое дело, что вероятность их появления не будет соответствовать случайному процессу.

[bioplant.livejournal.com]

Однако так как все машины в конечном итоге придуманы людьми, генерируемые ими случайные последовательности ТАКЖЕ нельзя считать истинно случайными.

[cass1an.livejournal.com]

Вовсе необязательно. Эта машина может брать какие-то случайные процессы в природе(которые не созданы людьми) и пользоваться их данными.

[bronevichek.livejournal.com]

Аппаратный ГСЧ (http://ru.wikipedia.org/wiki/%D0%90%D0%BF%D0%BF%D0%B0%D1%80%D0%B0%D1%82%D0%BD%D1%8B%D0%B9_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB)

[spoonisoutthere.livejournal.com]

человек не может придумать полностью случайную последовательность из нулей и единиц

а если будет монетку кидать?

[cass1an.livejournal.com]

Если придуманную монетку, то все то же самое. Если реальную монетку - это уже не придуманная последовательность, а с использованием генератора.

[il-gattopardo.livejournal.com]

если монетку кидать - то это уже не подпадает под "придумать"

[deadkittten.livejournal.com]

> Реализован ли уже подобный алгоритм?
В том же детстве (около 90 года) мы его в школе реализовывали -- вполне хорошо угадывал...

[ohshitnotuagain.livejournal.com]

Теоретически - да.
Практически - не хватит вычислительной мощности алгоритм формализовать.
Кроме того, он у человека может "гуляющий", со случайными флуктуациями.
Т.е. 99% чисел угадываются, а вот изредка нет-нет, да и вставит что-то неожиданное
Но когда это произойдёт предсказать невозможно.
Так же невозможно будет и сказать, "угадала" ли машина "алгоритм", ведь опыт можно продолжать N итераций, а ошибка произойдёт на N+1-ой.

[sun-stream.livejournal.com]

Да, нужно ввести определение, что будет подразумеваться под "угадыванием". Опыт-то изначально не будет строиться на бесконечной последовательности.
Наличие флуктуаций сомнению не подвергается, но, возможно, их "случайность" также поддается прогнозированию. В том и вопрос.

[natomist.livejournal.com]

Он вьіше человек на школьном суперкомпьютере такую программу реализовьівал

[cass1an.livejournal.com]

Разница в вычислительной мощности между "хорошо угадывать" и "100% угадывать" - колоссальная.

[natomist.livejournal.com]

Жаль, я надеялся, что ему кто-то позадает грамотно сформулированньіе вопросьі...

[existas.livejournal.com]

Да они походу и искусственный интеллект написали в третьем классе на БК0010.

[il-gattopardo.livejournal.com]

если верить Нилу Стивенсону в "Криптономиконе" (а не верить ему нет оснований), то псевдослучайные комбинации расшифровывались уже вычислительными мощностями, существовавшими во время Второй Мировой
а теперь и подавно получилось бы

[sun-stream.livejournal.com]

Интересен конкретный пример алгоритма, на любом языке.

[igor-eta.livejournal.com]

Если понимать теорию вероятностей, а не заниматься профанацией то нет

[cass1an.livejournal.com]

Со стопроцентной- вряд ли. Речь ведь о распознавании алгоритма. Вовсе не факт, что алгоритм полностью детерминированный. Возможно, на него влияют мутации и смерть нейронов, вызванные космическими частицами(что вроде как считается вполне случайным процессом) или еще чем-нибудь подобным. Не говоря уже о том, что бесконечный ряд получить можно только гипотетически(т.е. распознает она "поздно", а не "рано") и машине вероятно придется иметь полную карту нейронов(память ведь тоже влияет как-то).

Реализованы подобные программы для статистических оценок подделки бухотчетности. Ни о какой стопроцентности речь не идет, точной цифры, правда, не знаю.

[sun-stream.livejournal.com]

Интересно: я с коллегами сходную тему обсуждала, и в ходе обсуждения было высказано утверждение, что и влияние космических частиц не может быть полностью случайным. Что, правда, не означает возможности просчитать его с применением алгоритмов обозримой сложности.
Полную карту нейронов можно получить, но только в определенный момент времени, да. Насчет динамической - ой, не знаю.
Спасибо за ответ, вы подали мне немало свежих идей.

[cass1an.livejournal.com]

"что и влияние космических частиц не может быть полностью случайным."
Т.е. у вас и квантовая карта Вселенной под рукой? Опасный вы человек...=)

По сравнению с монеткой - вполне может. Но и механическую систему не всегда можно точно посчитать, в т.ч. бильярд Синая можно вполне использовать при определенных условиях, а речь идет о сложноизмеримых квантовых(что уже как-то с детерминированностью не дружит) системах космических масштабов во всех смыслах.

[sun-stream.livejournal.com]

Я абсолютно безопасный профан, не переживайте :) но термины "квантовая система" и "космический масштаб" мне кажутся не совсем сочетаемыми. Разве огромные размеры системы не переводят ее в разряд тех, что поддаются моделированию? Заранее прошу прощения, если вопрос глуп.

[cass1an.livejournal.com]

"Разве огромные размеры системы не переводят ее в разряд тех, что поддаются моделированию?"
А с чего бы? В космосе условия гораздо экстремальней и случаются гораздо более сложные вещи, чем на Земле(тот же звездный распад все пытаются повторить и не могут, не получается термояд). И летит это все распавшееся несколько световых лет или тысяч\миллионов лет. Оттого, что летит в миллион раз больше всего, чем в ускорителе, расчитать судьбу каждого конкретного объекта ничем не проще. Другое дело, что в таких масштабах обычно обходятся "большими мазками", миллион тонн туда, миллион тонн сюда - при массе Бетельгейзе не большая величина.

[sun-stream.livejournal.com]

Принимается.
Что подразумевается под "повторить звездный распад"? Построить математическую модель или воспроизвести в меньшем масштабе? Я припоминаю, что в курс астрономии входило изучение жизненного цикла звезды, причем сопровождалось это конкретными уравнениями, а не ограничивалось вербальным описанием процессов.

[cass1an.livejournal.com]

"воспроизвести в меньшем масштабе?"
Воспроизвести. Условия не позволяют(при солнечной массе-то оно стабильно горит под гравитационным давлением, а так отказывается).

Одно дело рассчитать цикл всей звезды(опять же, с точностью до тысячелетий) и другое - хотя бы полностью один протуберанец.

[igor-eta.livejournal.com]

То, что нельзя доказать просто.


Количество алгоритмов счетно, количество последовательной несчетно.


Увы и ах. Вас обманули

[sun-stream.livejournal.com]

Не плачьте. Я это переживу.

[tarnyagin.livejournal.com]

Вас обманули, это не так.

[karachee.livejournal.com]

Вряд ли такое возможно. Чисто математически если рассматривать сферического человека в вакууме, у которого вот такой мозг, который работает вот как-то так - да, компьютер обсчитает все последовательности. Но человек реальный, он связан с миром органами чувств, в нем постоянное происходят процессы мышления, восприятия, ощущения и пр. Т.е. в него постоянно входит какой-то неалгоритмизирумый поток данных, который хотя бы иногда будет влиять на выдаваемую человеком последовательность. Поэтому стопроцентная угадываемость недостижима, даже если человек сам будет пытаться придерживаться какой-то схемы, он наверняка собьется и что-то спутает.

[grey-horse.livejournal.com]

На похожую тему: http://plakhov.livejournal.com/173717.html

[zellily.livejournal.com]

Хм... Насчёт стопроцентной вероятности сомнительно.

[22he-travnya.livejournal.com]

Ваш вопрос не такой уж и юзлес - по этому принципу найдено одно из многочисленных доказательств фальсификации выборов ГД_2011 в пользу ЕдРа
http://corbulon.livejournal.com/97153.html

[sun-stream.livejournal.com]

Пост немного о другом. Различна природа происхождения последовательностей. Меня интересовали, во-первых, бинарные последовательности, созданные конкретным человеком, а во-вторых, существование алгоритмов, способных эти последовательности воспроизводить независимо от первоисточника. Природа же псевдослучайности - вопрос, бесспорно, интересный, но не в данный момент :)

[angerona.livejournal.com]

нет, не действительно, и никто не знает, действительно ли оно так когда-то будет. Это зависит от того, является ли мозг машиной тюринга (скорее всего, нет, хотя может оказаться, что и да).

Ну и в любом случае человек может брать информацию для этой цепочки извне, так что разве что у машины есть абсолютно вся та же информация, что и у человека (включая память и прошлом и т.д.), то ничего не выйдет.

[sanitareugen.livejournal.com]

Стопроцентного угадывания не будет хотя бы потому, что, заметив, что его цифры угадываются постоянно, человек попытается изменить способ получения следующей. И даже если он не осведомлен об угадываниях его цифр машиной, его выбор будет зависеть от меняющихся внешних факторов.
Написанная мной лет 35 тому назад такая программа выигрывала у человека со счётом примерно 60:40, несмотря на крайнюю простоту. Думаю, что выше 80:20 не подымется даже очень хитроумная программа.

[karachee.livejournal.com]

Думаю такую программу написать не так и сложно. Программе достаточно анализировать микродвижения мышц человека, тембр его голоса и пр. чтобы вычислять какая цифра будет названа им через 1-2 секунды. А если ещё позволить ей обеспечивать человека некоторыми внешними факторами, звуками, картинками, то она скоро сможет даже заставить его выдать нужную последовательность )))

[sanitareugen.livejournal.com]

Попробуйте. Я покамест не представляю, как. Просто угадывающую - делал. Но не "100%-ную".

[munchhausen2.livejournal.com]

абсолютно случайных последовательностей при генерации человеческим мозгом не возникнет, но угадать последловательность возможно лишь с определенной вероятностью (меньшей единицы), причем вероятность будет нелинейной функцией от количества последовательностей и их длины. Мощность ВМ и алгоритм (если он конечно составлен правильно) будут влиять лишь на скорость вычисления.

[krazzzer.livejournal.com]

Это вопрос про программерство или про свободу воли?

[Панда Бу (from livejournal.com)]

меня заинтересовал предпоследний пост.. натолкнул на мысль.. машина предугадывает следующий ход человека.. но ставим так.. предположим я - человек не ограничен во времени.. тоесть машина зависит от моего решения в некотором роде... ммм... круться где то рядом мысль)).. 0 и 1 это же по сути "да и нет".. "есть - нет", решение машина уже приняла согласно моим предидущим решениям.. следовательно я имею большую свободу.. так как могу анализировать все происходящее ранее.. и вынести какое то решение.. и тоже предугадать?... ааааааа!!!!..

в любом случае вопрос крутиться где то рядом с интуицией.. и если даже кидать монетку, она зависит от нас.. от силы наших пальцев и подсознательных факторов.. если эту монетку гипотетически перевести на внешний... не зависящий от нас механизм(в широком смысле).. тогда может и да.. но опять же у него тоже можно вычислить со временем закономерность.. если сменять внешние механизмы "монеток", сейчас один, затем другой... другими словами собрать друзей и давать случайным образом каждом единожды бросить эту монетку.. а потом искать других людей..

возможно стоит ограничить колличество цифр в последовательности.. конечное колличество...

запутался немного)) интуиция очень проситься сюда влезть))