задачи бывают алгоритмически не разрешимыми, как например задача остановки
все остальные обычно(!) сравнивают по времени решения на рандомизированноймашине Тьюринга
задача остановки - это задача по коду программы предсказания на одной машине тьюринга, остановится ли другая машина тьюринга, когда этот код будет выполнять