Основы математической логики и теории алгоритмов
Подождите немного. Документ загружается.
определенная функция f(x) = μy (s(x) < x) частично рекурсивна.
Класс РФ совпадает с классом ОРФ.
Класс ОРФ строго содержит класс ПРФ. В качестве примеров
общерекурсивных, но не примитивно рекурсивных функций можно взять так
называемые быстрорастущие функции, т.е. такие общерекурсивные функции f(x),
что для каждой ПРФ g(х) существует число а с условием g(х) < f(x) при x
а.
Вместо оператора R можно использовать арифметические операции, тогда
Предложение 1 Любая ЧРФ она может быть получена из простейших ПРФ
и функций + и
с помощью конечного числа применений операторов S, М.
Из определения ПРФ и ЧРФ следует, что любая ЧРФ является вычислимой,
обратное носит имя Черча: любая вычислимая частичная функция частично
рекурсивна.
Теорема об эквивалентности данных моделей алгоритмов Класс частично
рекурсивных функций совпадает с классом функций, вычислимых по Тьюрингу.
3.3.4. Рекурсивно перечислимые отношения
Отношение P
k
N
называется рекурсивным (РО), если рекурсивна
характеристическая функция
P
. Отношение P
k
N
называется рекурсивно
перечислимым (РПО), если существует такое рекурсивное отношение Q
1
k
N
, что
}),,...,(|),...,{(),,...,(
111
NyнекоторогодляQyxxxxyxxyQP
kkk
т.е. РП-мость
отношения означает, что оно является проекцией РО по некоторой координате.
Тогда проекция по нескольким координатам тоже РПО.
Предложение 1. Если Q
mk
N
-РО,
1m
, то отношение
),...,,,...,(...
111 mkm
yyxxQyy
- РПО.
Предложение 2. Р,Q
k
N
, R
l
N
-РО, тогда отношения
QP
,
QP
,
P
,
QP
,
RP
- рекурсивны.
Теорема Поста. Отношение P
k
N
- рекурсивно
P,
P
- РПО.
Доказательство.
Пусть P – рекурсивно, тогда
),,...,)((
1
yxxNPyP
k
, тогда
по Пр.2.
NP
- РО, и P,
P
- РПО.
Пусть P,
P
- РПО. Т.е.
),(
0
yxyQP
и
),(
1
yxyQP
, где Q
1,
Q
0
РО. Рассмотрим ЧРФ
)1()(
10
QQ
yxf
- она всюду определена, т.е.
71
рекурсивна. Тогда
1))(,(,0
1))(,(,1
)(
1
0
xfx
xfx
x
Q
Q
P
, тогда P- рекурсивное отношение.
3.4. Неразрешимость исчисления предикатов. Теорема Геделя о
неполноте. Разрешимые и неразрешимые теории.
Далее докажем неразрешимость ИП арифметической сигнатуры
},0,,,{
)2()0()2()2()1(
0
S
Исчисление I называется разрешимым, если существует алгоритм, позволяющий
по любому выражению Ф
I
узнать, доказуемо ли Ф или нет; в противном случае это
неразрешимое исчисление.
Определение. Пусть W(A) – множество слов алфавита А. Геделевской
нумерацией множества W(A) называется такая разнозначная функция
NAWg )(:
, что
существует алгоритм G, вычисляющий по слову w
)(AW
его номер g(w) и
существует алгоритм
G
, выписывающий по числу
Nn
слово w, если n=g(w), и
выдающий число 0, если
))((\ AWgNn
.
Тогда в силу тезиса Черча вопрос о разрешимости исчисления, имеющего
геделевскую нумерацию для каждого выражения исчисления, сводится к вопросу о
рекурсивности множества геделевских номеров всех теорем исчисления.
Поэтому каждой формуле
0
ИП
поставим геделевский номер
, по которому
можно эффективно распознавать структуру самой формулы.
Определение. Пусть
)(
0
T
и
)(
0
F
- множество термов и формул
0
.
Определим индукцией по числу шагов построения термов и формул геделевскую
нумерацию
NFT )()(:
00
по следующим правилам:
0)
)1,0()0( c
1)
),1()( ncv
n
, где v
n
- n- я переменная из множества V.
2)
))(,2())(( tcts
, где
)(
0
Tt
3)
)))(),((,3()(
2121
ttcctt
,
)(,
021
Ttt
4)
)))(),((,4()(
2121
ttcctt
5)
)))(),((,5()(
2121
ttcctt
6)
)))(),((,6()(
2121
ttcctt
7)
)))(),((,7()(
cc
,
)(,
0
F
8)
)))(),((,8()(
cc
9)
)))(),((,9()(
cc
10)
))(,10()(
c
72
11)
)))(,(,11()(
nccv
n
12)
)))(,(,12()(
nccv
n
из ПР-ности c,l,r вытекает
Предложение 1.
1) Множество геделевских номеров термов
0
)}(|)({
0
0
Ttt
T
- ПР-но.
2) Множество геделевских номеров формул
0
)}(|)({
0
0
F
F
- ПР-но
3) Множество геделевских номеров аксиом
0
)}(|)({
0
Aaa
i
A
14,...,1i
- ПР-но
Для аксиом приведем пример примитивно-рекурсивного описания характеристической
функции для множества A
1
- геделевских номеров аксиомы
)(
:
случаепротивномв
nrrrrnrlnrrlnlnесли
n
F
А
,0
))))(((())((,9)))(((,9)(,1)(,1
)(
0
1
Для 3-х правил вывода ИП также справедлива ПР-ность.
Пусть Sb(m,n,k) – функция, устанавливающая по геделевскому номеру m терма q и
геделевскому номеру k терма t геделевский номер результата подстановки
n
v
t
q)(
, а по
геделевскому номеру m формулы
, геделевскому номеру k терма t геделевский
номер результата подстановки
n
v
t
)(
. Sb(m,n,k) – ПРФ.
Теорема 1. Множество геделевских номеров доказуемых формул
0
ИП
, т.е. теорем,
рекурсивно перечислимо.
Следствие. Если X- множество формул
0
, у которого множество
)(Х
- рекурсивно
перечислимо, то множество {
||),( X
}
Определение. Множество Г предложений сигнатуры Σ, замкнутое относительно
выводимости (т.е. содержащее все предложения, выводимые из Г в ИΠ
Σ
), называется
элементарной теорией или просто теорией сигнатуры Σ
Определение. Теорией 1-го порядка (или элементарной теорией или просто
теорией) в
0
ИП
называется любое дедуктивно замкнутое множество замкнутых
формул
0
(т.е.
TAAT |
).
Замкнутой формулой Σ или предложением называется формула Σ, не имеющая
свободных переменных.
Mножество формул Σ T называется дедуктивно замкнутым, если для любой
формулы
из
TT
|
.
73
Множество замкнутых формул, которые выводимы в ИП из аксиом, называется
формальной аксиоматической теорией (дедуктивной теорией)
Представим аксиомы
0
, порождающие элементарную теорию арифметики:
1)
)()()( yxySxS
2)
)0)(( xS
3)
)))(()0(( ySxyx
4)
)0()0( xxxx
5)
))()(())()(( yxSyxSyxSySx
6)
)00()00( xx
7)
xyxySx )(
8)
)))()((
)()()(())())()((()(
xyyx
zxzyyxyxxyyxxx
9)
)( yzxzyx
Множество этих аксиом обозначим через
0
A
10)
)()))(()(()0( yyxSxx
- аксиома математической
индукции.
10 аксиом составляют систему аксиом арифметики Пеано (обозначим P)
Определение. Функция
NNf
k
:
назовем представимой в
0
A
, если для некоторой
формулы
),,...,(
1
yxx
k
0
и любых чисел
Nmnn
k
,,...,
1
выполняются следующие
условия:
если
mnnf
k
),...,(
1
, то
),,...,(|
1
0 mnn
k
A
если
mnnf
k
),...,(
1
, то
),,...,(|
1
0 mnn
k
A
при этом формула
называется представляющей для функции f.
Обозначим
0
константу 0, через
1
n
терм
)(
n
S
,
Nn
.
Теорема 2. (о представимости) Любая рекурсивная функция представима в
0
A
.
Теорема 3. Если X – непротиворечивое множество формул
0
, содержащее
множество
0
A
, то множество
)(
X
T
нерекурсивно, где
}||{
XT
X
.
Доказательство. Рассмотрим термы
n
и ПРФ Nm(n), определяемую схемой:
Nm(0)=c(0,1), Nm(n+1)=c(2,Nm(n)), и задающую геделевские номера термов
n
:
Nm(n)=
n
. Обозначим через Sb
0
(x,y)=Sb(x,0,Nm(y))( ПРФ), где для любой формулы
сигнатуры
0
и любого
Nn
справедливо
))(()),((
0
0
v
n
nSb
. Предположим
)(
X
T
- рекурсивно, т.е.
)(
X
T
- рекурсивная функция. Рассмотрим формулу
),,( zyx
, не
74
содержащую переменную v
0
и представляющую рекурсивную функцию
)),((
0)(
yxSb
X
T
. Положим
0
,,
,,
))),,(((
100
nzyx
zyx
vv
. Если
1)),((
000)(
nnSb
X
T
, то
)(),,((
1
00
Xnn
T
и следовательно
),,(|
1
00
nn
X
. Однако в силу
представимости в
0
A
функции
)),((
0)(
yxSb
X
T
справедливо
),,(|
10
00
nn
A
, а
значит
Xnn
T ),,(
1
00
т.к.
XA
0
. Т.о.
),,(|
1
00
nn
X
. Получили противоречие,
т.к. Х – непротиворечиво по условии.
Пусть
0)),((
000)(
nnSb
X
T
, тогда
Xnn
T ),,(
1
00
; но в силу представимости в
0
A
функции
)),((
0)(
yxSb
X
T
формулой
),,( zyx
,
),,(|
10
00
nn
A
(т.к.
1)),((
000)(
nnSb
X
T
) и
Xnn
T ),,(
1
00
- противоречие. Т.о.
)(
X
T
-нерекурсивно.
Определение. Непротиворечивая теория Т
0
называется разрешимой, если
множество геделевских номеров предложений из Т рекурсивно.
Следствие 1. (о неразрешимости теории элементарной арифметики) Для
любого X – непротиворечивого множества формул
0
, содержащего множество
0
A
, теория Т
Х
, порожденная множеством Х, неразрешима.
Т.е. не существует универсального алгоритма решения всех математических
задач.
Следствие 2. (теорема Геделя о неполноте теории арифметики Пеано) Пусть
X – непротиворечивое множество формул
0
, содержащее множество
0
A
, и
)(Х
-
рекурсивно перечислимое отношение. Тогда теория Т
Х
, порожденная множеством Х,
неполна.
Доказательство. Предположим Т
Х
–
полно. Т.к.
)(Х
- РПО, то по Следствию
Теоремы 1
)(
X
T
-РПО. Но в силу полноты теории Т
Х,
РП множество
)(
X
T
,
поскольку оно состоит из всех натуральных чисел, не являющихся геделевскими
номерами предложений
0
, а также из геделевских номеров, предложений
, для
которых
X
T
, тогда по теореме Поста
)(
X
T
-рекурсивно. Противоречие с
теоремой 3.
Следствие 3. (теорема Черча о неразрешимости
0
ИП
) Множество
геделевских номеров теорем исчисления
0
ИП
нерекурсивно.
Доказательство. Пусть
0
- конъюнкция формул из А
0
.Очевидно, для любой
формулы
сигнатуры
0
условие
|
0
A
равносильно тому, что
0
- теорема
75
0
ИП
. Предположим, что множество
}|)({
0
ИПтеоремаB
- рекурсивно. Тогда
рекурсивна функция
)(,))),(,9((
000
nгдеxnccf
B
. При этом f является
характеристической функцией для множества Х геделевских номеров формул,
выводимых из А
0
. Это невозможно, т.к. по теореме 3 множество Х нерекурсивно.
В силу теоремы Черча возникла задача нахождения разрешимых теорий. В
частности, разрешимыми являются следующие теории:
Th(<Q;< >),
Th(<R;+,<,0,1,
>),
Th(<Q;+,-,0>),
Th(<Z;+,-, 0>),
Th(<N;+,S,0>)
Th(<N;
,0>).
76