Cтраница 4
Итак, ( Ех) ( у) ( Ег) Т3 ( а, а, х, у, г) имеет проблему разрешимости наивысшеч степени неразрешимости среди проблем разрешимости для предикатов формы ( Ех) ( у) ( Ег) R ( а, х, у, г) с рекурсивным, R, и к его проблеме разрешимости взаимно однозначно сводима проблема разрешимости для любого предиката, имеющего эту форму. [46]
Итак, ( Ех) ( у) ( Ег) Т3 ( а, а, х, у, г) имеет проблему разрешимости наивысшеч степени неразрешимости среди проблем разрешимости для предикатов формы ( Ех) ( у) ( Ег) R ( а, х, у, г) с рекурсивным, R, и к его проблеме разрешимости взаимно однозначно сводима проблема разрешимости для любого предиката, имеющего эту форму. [47]
Итак, ( Ех) ( у) ( Ег) Т3 ( а, а, х, у, г) имеет проблему разрешимости наивысшеч степени неразрешимости среди проблем разрешимости для предикатов формы ( Ех) ( у) ( Ег) R ( а, х, у, г) с рекурсивным, R, и к его проблеме разрешимости взаимно однозначно сводима проблема разрешимости для любого предиката, имеющего эту форму. [48]
Таким образом, доказав, что не существует алгоритма для решения вопроса об остановке машины, Тьюринг показал ( также как и Черч, который использовал свой собственный и весьма отличающийся подход), что не может быть и общего алгоритма для решения математических задач. Проблема разрешимости Гильберта не имеет решения. [49]
Изучение диаграмм Венна подсказало автору некоторые изменения решения проблемы разрешения для исчисления одноместных предикатов. Венн не занимался проблемами разрешимости и разрешения. Но для того, чтобы обосновать его метод преобразования информации ( в которую могут входить и частные предложения), нами решается проблема разрешения для формул исчисления одноместных предикатов с помощью только диаграмм Венна. Из ее решения получается общее правило, позволяющее обозревать логические следствия данных посылок. [50]