|
|
Межкафедральный семинар МФТИ по дискретной математике
14 октября 2015 г., г. Долгопрудный, МФТИ, Корпус Прикладной Математики, 115
|
 |
|
 |
|
|
|
Проблема остановки для большинства входов и колмогоровская сложность
А. Х. Шень |
|
Аннотация:
Проблема остановки (остановится ли данная программа или нет) неразрешима — но, может быть, она разрешима в «большинстве случаев» или «почти всегда»? Этот вопрос можно уточнять по-разному, и ответы тоже будет разные (но в основном отрицательные). Мы обсудим варианты постановки и доказательства, использующие колмогоровскую сложность.
|
|
Обратная связь: