170
правок
Изменения
Нет описания правки
{{Теорема
|statement=
Не существует алгоритма, определяющего по формуле [[ Исчисление предикатов | исчисления предикатов первого порядка]], является ли она [[Исчисление предикатов#valid | общезначимой]].
|proof=
Обозначим язык всех общезначимых формул <tex>L = \{w | w</tex> {{---}} общезначимая формула исчисления предикатов первого порядка<tex>\}</tex>. Покажем, что [[Разрешимые (рекурсивные) языки#uni | универсальный язык]] <tex>U</tex> [[m-сводимость | m-сводится]] к <tex>L</tex>. Для этого нужно построить вычислимую функцию <tex>f</tex>, которая принимает на вход пару из [[ Машина Тьюринга | машины Тьюринга ]] <tex>M = \langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex> и слова <tex>w</tex> и возвращает некоторую формулу исчисления предикатов, причём:
== Ссылки ==
* [http://logic.pdmi.ras.ru/~dmitrits/csclub/likbez4.pdfПрезентация по данной проблеме]* [http://en.wikipedia.org/wiki/Entscheidungsproblem Wikipedia {{---}} Entscheidungsproblem]* [http://en.wikipedia.org/wiki/First-order_logic Wikipedia {{---}} First-order logic]
