Аннотация:
Проблема остановки (остановится ли данная программа или нет) неразрешима — но, может быть, она разрешима в «большинстве случаев» или «почти всегда»? Этот вопрос можно уточнять по-разному, и ответы тоже будет разные (но в основном отрицательные). Мы обсудим варианты постановки и доказательства, использующие колмогоровскую сложность.
Обратная связь: