Существует ли ТМ для всех счетных языков?

Question

Я знаю, что если для языка существует машина Тьюринга, этот язык рекурсивно перечислим, и поэтому для него существует процедура перечисления. Однако, если язык исчисляется, означает ли это, что для него должен быть ТМ?

Спасибо!

Answer 1

Множество Σ* является счетным множеством, поэтому все его подмножества счетны. В частности, это означает, что каждый бесконечный язык исчисляется, хотя не все бесконечные языки рекурсивно перечислимы. Следовательно, существует бесконечно много бесконечных языков, для которых не существует ТМ.

Надеюсь это поможет!