Теорема Райса

Теорема Райса утверждает, что любое нетривиальное семантическое свойство языка, которое распознается машиной Тьюринга, неразрешимо. Свойство P — это язык всех машин Тьюринга, которые удовлетворяют этому свойству.

Формальное определение

Если P является нетривиальным свойством, а язык, содержащий свойство L _p , распознается машиной Тьюринга M, то L _p = {<M> | L (M) ∈ P} неразрешима.

Описание и свойства

• Свойство языков P — это просто набор языков. Если какой-либо язык принадлежит P (L ∈ P), говорят, что L удовлетворяет свойству P.

• Свойство называется тривиальным, если оно не удовлетворяется какими-либо рекурсивно перечислимыми языками или если оно удовлетворяется всеми рекурсивно перечислимыми языками.

• Нетривиальное свойство удовлетворяется некоторыми рекурсивно перечислимыми языками и не удовлетворяется другими. Формально говоря, в нетривиальном свойстве, где L ∈ P, выполняются оба следующих свойства:

  • Свойство 1. Существуют машины Тьюринга, M1 и M2, которые распознают один и тот же язык, т. Е. Либо (<M1>, <M2> ∈ L), либо (<M1>, <M2> ∉ L)

  • Свойство 2 — Существуют машины Тьюринга M1 и M2, где M1 распознает язык, а M2 — нет, то есть <M1> ∈ L и <M2> ∉ L

Свойство языков P — это просто набор языков. Если какой-либо язык принадлежит P (L ∈ P), говорят, что L удовлетворяет свойству P.

Свойство называется тривиальным, если оно не удовлетворяется какими-либо рекурсивно перечислимыми языками или если оно удовлетворяется всеми рекурсивно перечислимыми языками.

Нетривиальное свойство удовлетворяется некоторыми рекурсивно перечислимыми языками и не удовлетворяется другими. Формально говоря, в нетривиальном свойстве, где L ∈ P, выполняются оба следующих свойства:

Свойство 1. Существуют машины Тьюринга, M1 и M2, которые распознают один и тот же язык, т. Е. Либо (<M1>, <M2> ∈ L), либо (<M1>, <M2> ∉ L)

Свойство 2 — Существуют машины Тьюринга M1 и M2, где M1 распознает язык, а M2 — нет, то есть <M1> ∈ L и <M2> ∉ L

доказательство

Предположим, что свойство P нетривиально и φ ∈ P.

Поскольку P нетривиален, по крайней мере один язык удовлетворяет P, т. Е. L (M ₀ ) ∈ P, Machine машина Тьюринга M ₀ .

Пусть, w будет входом в конкретный момент, а N является машиной Тьюринга, которая следует

На входе х

• Беги М на ж
• Если M не принимает (или не останавливает), то не принимает x (или не останавливает)
• Если M принимает w, тогда запустите M ₀ на x. Если M ₀ принимает x, то принимает x.

Функция, которая отображает экземпляр ATM = {<M, w> | M принимает ввод w} к N так, что

• Если M принимает w и N принимает тот же язык, что и M ₀ , то L (M) = L (M ₀ ) ∈ p
• Если M не принимает w и N принимает φ, то L (N) = φ ∉ p

Поскольку _ТМ неразрешима и может быть уменьшена до Lp, Lp также неразрешима.