проблема останова

Остановится же. Исполнитель сдохнет рано или поздно.

Сенкью, кэп :)

Хотел здесь накатать более красочную иллюстрацию основанную на сюжете сношений романтических отношений тьюринга и молодого Арнольда

Ты понимаешь, что ты поехавший?

Можно исчо кароче: если б знал, соломку б подстелил. Действительно бред.

Пятница начинается в четверг?

просто у тебя слабое абстрактное мышление, всего-то.

И что не так с проблемой останова? Попахивает К.О.? Ну так и почти все остальные фундаментальные законы попахивают, и ничего

А я все ждал, появиться ли подобный коммент. Вероятность что не появиться я оценивал примерно как 1/10000. Не ошибся, значится.

Тогда нахрена наши налоги расходуются на эти нано? Нет других ртов, которые нуждаются в хлебе?

Из простых закономерностей составляют сложные. Сложные настолько, что маловероятно что кто-нибудь бы импирическим путём бы их вывел. И эти самое сложные закономерности уже применяют в народном хозяйстве.

Почему бы эти сложные закономерности не составлять непосредственно из перлов капитана? Разница есть?

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

Ты опять все перепутал. Должно быть:

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

Пятница начинается в четверг?

У него каждый день пятница.

Я ничего не перепутал.

Я ничего не перепутал.

Перепутал, перепутал.

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

А как Вы считаете (ну, или как считается в теории вероятностей), если мы, например играем в русскую рулетку, существует ли вероятность, что револьвер никогда не выстрелит? Как, вообще, официально считается?

«Ты опять выходишь на связь, ...?»

Долгое время не мог врубиться в витиеватую формулировку сабжа.

Ничего в ней витиеватого нет, просто кое-кто сказочный <неприличное_слово_из_3_букв>.

Остановиться ли наш перебор когда либо, если мы не знаем существует ли красный шарик?

А сам то как думаешь?

Ничего он не перепутал. Последовательность шариков — это последовательность всех шариков, которые перебираются алгоритмом в процессе поиска красного.

Вся суть проблемы останова капитанская, да: вычисления и алгоритмы не превышают по способностям тупой механический перебор, то есть не могут магическим образом определить, есть ли таки там красный шарик или нет, не увидев его. Это имеет важное значение, если перебираемых шариков именно что бесконечное количество. Нечто похожее есть в определении аксиомы выбора.

Это косяк.

Почему бы эти сложные закономерности не составлять непосредственно из перлов капитана?

Так это и есть перл капитана, только записанный и доказанный формально в терминах машины Тьюринга. И, в общем то, никакой магии.

А как Вы считаете (ну, или как считается в теории вероятностей), если мы, например играем в русскую рулетку, существует ли вероятность, что револьвер никогда не выстрелит? Как, вообще, официально считается?

Это в чистом виде схема Бернулли, где за успех (сомнительный такой успех, конечно) принимаем выстрел. Соответственно, все свойства смотрите для схемы Бернулли. Вероятность того, что выстрела не будет, — бесконечно малая величина. Для статистически значимого числа попыток можете смело считать, что эта вероятность 0.

Меня как раз бесит то, что люди выдающие за феерические открытия очевидные вещи, удостаиваются посмертной славы и мат благ и почестей при жизни, а потом, чтобы скрыть этот гребаный стыд, это капитанство облачают в витиеватые «ритуальные одежды», чтоб домохозяйки не поняли.

Ну я так и думал, собственно. Спасибо.

никогда не выстрелит

блин, ты это никогда уточняй. А вообще вспоминай университетский курс. Вероятность того что револьвер с барабаном на 6 патронов и одном заряженном не выстрелит - 5/6. Вероятность того что револьвер не выстрелит к n-ному разу - (5/6)^n; Если твое никогда - бесконечное число выстрелов, то lim(5/6)^n при n->Inf. Предел этот равен нулю. Но револьвер быстрее развалится, чем бесконечность к нам придет, ты же понимаешь.

Предел этот равен нулю

Наверное, будет точнее - стремится к нулю?

Да зачем нам бесконечность? На практике берём некое сильно маленькое значение вероятности, сравни падению метеорита на голову, скажем, 1e-8. И получаем всего 102 попытки.

Стремится последовательность, предел равен.

что люди выдающие за феерические открытия очевидные вещи

А Тьюринг таки бегал без штанов по городу и орал «эврика, эврика»? Или ходил на все конференции в округе и заявлял что нашел решение всех проблем человечества?

И получаем всего 102 попытки.

ну таки вопрос был «существует ли вероятность, что револьвер никогда не выстрелит». Именно никогда - нет, но вообще, либо эмир, или ишак, или я за это время сдохнут

Глупо было бы. Так бы он точно не добился ничего кроме места в желтом доме. Нужно скорчить наукообразную мину, и поиграть в скромность. Ну, в его случае, понадобилось еще скопипи-ть чужие идеи, но это в общем случае даже не обязательно.

Ну, в его случае, понадобилось еще скопипи-ть чужие идеи, но это в общем случае даже не обязательно.

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

Рискну предположить, что не существует четкой, конкретной границы, где последовательность «переходит в предел»?

Я про его машину. man Пост.

Рискну предположить, что не существует четкой, конкретной границы, где последовательность «переходит в предел»?

Предел — это характеристика последовательности. О каком переходе речь?

где последовательность «переходит в предел»

Кто куда переходит? Это разные вещи вообще

Я в этом не силен, просто семантически это звучит как оксюморон. Предел - это конец (например веревки). Конец не может быть последовательностью. Математики просто жонглируют словами, чтобы оправдать несостоятельность своего подхода. Это мое ИМХО. Это похоже на парадокс Аххилеса и черепахи.

Я в этом не силен

Математики просто жонглируют словами, чтобы оправдать несостоятельность своего подхода.

Охлол. Есть ещё на Руси «нечиталноосуждаю». Ты просто не осилил, смирись.

Я в этом не силен
Математики просто жонглируют словами, чтобы оправдать несостоятельность своего подхода

Пастернака не читал, но осуждаешь?

Ну ладно, признаю. Но возможно, имею здравый смысл. Кака понять выражение больше, чем бесконечность?

Кака понять выражение больше, чем бесконечность?

Ссылку на то, где ты это откопал.

проблема останова (комментарий)

Пардон, там наверное имеется в виду, как раз, переход в бесконечность.

Там нет ничего про «больше, чем бесконечность». Вероятно, Вам следует открыть учебник матана для первого курса и почитать о сходимости.

Так его и не за машину почестей удостоили, а за теорию вычислений, а МТ лишь ее инструмент и он там не один.

Но сам переход ведь не дискретен? Мы не можем его определить? Что значит предел тогда, если к нему невозможно подойти?

Четыре ошибки на коммент. Чувак, ты либо пиши грамотнее, либо тролль тоньше.

Да, я уже понял. Но матан читать не буду. Мне тьюринга хватило. Лучше своими мозгами отсеивать грязь, чем через 30 лет обнаружить что ты по шею в грязи.

Что значит предел тогда, если к нему невозможно подойти?

Возможно. Причём, для сходящегося ряда можно подойти сколь угодно близко. Есть ещё частичные пределы, да :)

Ну, о чем я и говорю! Это просто ловкость рук. Ни один математик не в праве утверждать, что вероятность равна нулю, если очевидно, что к этой вероятности невозможно подойти так, что «мы действительно знаем, когда мы будем стоять непосредственно на нулевой отметке». Вы правы были в своем первом ответе. Эта вероятность бесконечно будет приближаться к нулю, но этого никогда не произойдет. Я и без математиков это понимаю.