Проблема остановки для большинства входов и колмогоровская сложность

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