Home

Семинар 10 января 2000 года

Понедельник, 10 января, комната 203. Начало в 14:30.

Докладчик: Б. Ю. Конев.

"Подход Г.Чайтина к колмогоровской сложности"
Этот подход отличается тем, что, в частности, предлагается ограничиться только такими программами универсальной машины Тьюринга, для которых никакой префикс не является программой (self-delimiting programs). Это позволяет ввести вероятность остановки $ \Omega $ (halting probability). Будут рассмотрены свойства введенных понятий, а также следствия для алгоритмической теории информации.