Для неразрешимого языка нет машины Тьюринга, которая принимает язык и принимает решение для каждой входной строки w (хотя TM может принять решение для некоторой входной строки). Решение проблемы P называется «неразрешимым», если язык L всех экземпляров yes для P не разрешим. Неразрешимые языки не являются рекурсивными языками, но иногда они могут быть рекурсивно перечислимыми языками.