Если p машина Тьюринга, то L (p) = {x |p (x) = yes}.
Let A = {p | p is a Turing machine and L(p) is a finite set}.
Является ли A вычислимой?Обоснуйте свой ответ.
Поэтому я пытаюсь выяснить, как решить этот вопрос, и вот ответ, который я придумал:
(i) Итак, мы знаем, что Aявляется нетривиальной задачей, поскольку некоторые машины Тьюринга L (p) являются конечным состоянием, а некоторые машины Тьюринга, где L (p) не является конечным состоянием
(ii) A уважает эквивалентность, когда даны любые 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 невычислимо.