Столкнулся с необходимостью написания генерации тестов для покрытия кода (язык программирования — некоторое подмножестве Java: есть доступ только к БД, никакого другого ввода-вывода (включая доступ к таймеру и Random); приложение строго однопоточное).

Решено покрывать пути выполнения. Но в той же Википедии написано, что проблема полного покрытия кода аналогична проблеме остановки. Но посмотрите на проблему остановки, как там сформулировано доказательство -- ведь это весьма сложная программа, получается.

Создается впечатление, что проблема надумана. Ну да, для 0.00...001% программ, встречающихся на практике, нельзя будет определить, останавливаются ли они (и покрыть их на 100% тестами). Но для остальных 99.9999...9% явно это можно сделать.

Так вот вопрос: встречались ли вам программы, у которых нельзя было бы покрыть все трассы выполнения? Можете ли привести пример таких программ?