Мне нужно доказать, что язык машин Тьюринга, который останавливается на каждом входе, не распознается. Я уже видел несколько решений этой проблемы, но профессор хочет, чтобы мы делали это, используя тот факт, что полуразрешимый язык является диапазоном некоторой частично вычислимой функции, а затем использовал диагонализацию, чтобы получить противоречие. Я не уверен, как начать думать над доказательством, используя эти "подсказки".
Спасибо!
Gil