Показывает ли мое решение, что язык не вычислим, если применить теорему Райса?
Если p машина Тьюринга, то L(p) = {x | р (х) = да}.
Let A = {p | p is a Turing machine and L(p) is a finite set}.
Является ли вычислимым? Обосновать ответ.
Поэтому я пытаюсь выяснить, как решить этот вопрос, и вот ответ, который я придумал:
(i) Итак, мы знаем, что A - нетривиальная задача, поскольку некоторые машины Тьюринга L (p) являются конечным состоянием, а некоторые машины Тьюринга, где L (p) не является конечным состоянием.
(ii) Соблюдает эквивалентность, когда даны любые 2 эквивалентные машины Тьюринга p и q.
p ε A ⇒ p is a turing machine and L(p) is a finite set
⇒ q is a turing machine and L(q) is a finite set
⇒ q ε A
Следовательно, применяя теорему Райса, мы можем видеть, что A невычислимо.