2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

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

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Случайность в арифметике
Сообщение21.04.2015, 14:33 
Аватара пользователя


04/06/14
623
http://ega-math.narod.ru/Nquant/Random.htm
Помогите пожалуйста разобраться в статье, по самой сущности статьи фактически ничего не понятно, ибо знаний в области теории алгоритмов не имею.
Может ли кто-нибудь "вкратце" объяснить, о какой такой случайности идёт речь?

 Профиль  
                  
 
 Re: Случайность в арифметике
Сообщение21.04.2015, 16:07 
Заслуженный участник


04/05/09
4582
Вкратце: берём некоторую Машину Тьюринга (МТ), и проверяем на каких входных данных она закончит вычисление за конечное время.
Допустим это:
0100100...
011000011001010...
101100001100101...
00100001111010011101...
110110000101001000100...
и так далее.
Входные данные, которые следуют далее за указанными, не важны, т.к. МТ их не прочитает.

Теперь можно посчитать вероятность того, что эта МТ остановится на равномерно случайных входных данных:
$\Omega = \sum\limits_{p\ halts}2^{-|p|}$
где $p$ - определяющий префикс входных данных, и $|p|$ - его длина.

Эта вероятность - конкретное число между 0 и 1, трансцендентное, и невычислимое, т.к. проблема останова (halting problem) МТ неразрешима.
Такое число называется константой Хайтина (Chaitin's Constant). Таких констант целый класс, т.к. число зависит от конкретного варианта МТ.
Для некоторых вариантов МТ вычислены начальные биты этой константы. Полностью же такую константу вычислить невозможно, хотя она и вполне определена.

 Профиль  
                  
 
 Re: Случайность в арифметике
Сообщение20.02.2018, 14:31 
Аватара пользователя


04/06/14
623
venco, спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group