2014 dxdy logo

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

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




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

 
 
 
 Re: Случайность в арифметике
Сообщение21.04.2015, 16:07 
Вкратце: берём некоторую Машину Тьюринга (МТ), и проверяем на каких входных данных она закончит вычисление за конечное время.
Допустим это:
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 
Аватара пользователя
venco, спасибо.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group