Существуют. Например, нельзя создать программу, которая для произвольной программы скажет зациклиться она или нет на входе из своего номера. Нельзя для определенного класса языков сказать будут ли две входных грамматики задавать один и тот же язык или нет. Если задать два разных набора последовательностей (система Поста) в некотором алфавите, то нельзя сказать можно ли будет в каждой из систем составить (конкатенацией) одинаковое слово. Таких проблем бесконечно много.
Существует и таких проблем несчетное множество.
Количество решаемых проблем бесконечно и счетно, а количество нерешаемых проблем бесконечно и несчетно.
На такие вопросы отвечают, например, в курсе теория вычислений.