| RUS ENG |
| Полная версия |
|
|
|
| СЕМИНАРЫ |
|
Межкафедральный семинар МФТИ по дискретной математике
|
|||
|
|
|||
|
Проблема остановки для большинства входов и колмогоровская сложность А. Х. Шень |
|||
|
Аннотация: Проблема остановки (остановится ли данная программа или нет) неразрешима — но, может быть, она разрешима в «большинстве случаев» или «почти всегда»? Этот вопрос можно уточнять по-разному, и ответы тоже будет разные (но в основном отрицательные). Мы обсудим варианты постановки и доказательства, использующие колмогоровскую сложность. |
|||