* Алгоритмічно нерозв'язні задачі

Проблема розв’язності (зависання)

В теорії обчислювальності існує проблема зависання (обчислювальності): дано опис алгоритму та початкові вхідні дані, необхідно визначити, чи може алгоритм з цими вхідними даними завершитися коли-небудь. Альтернативою зупинки є ситуація, коли робота алгоритму не припиняється (він зависає). Машина Т‘юринга не може бути використана для вирішення проблеми зависання будь-якого алгоритму. Тому подібна задача відноситься до алгоритмічно нерозв‘язних задач