Теория алгоритмов. Зюзысов В.М. - 42 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

При этом требуется: (i) чтобы значение функции g можно было вычислить с помощью
некоторого алгоритма, (ii) чтобы существовал алгоритм, позволяющий для каждого m
определить, является ли m значением функции g, и в случае, если является, то построить
тот объект x, для которого m = g(x). Значение функции g
для символа (
выражения, последовательности выражений)
называется гёделевым номером соответствующего
объекта.
Курт Гёдель
Существуют различные способы построения
гёделевых номеров для системы EA[17, с. 151–152].
Изложим кратко одну из возможных гёделевых
нумераций. Рассмотрим алфавит теории EA. Выберем 10
основных символов этого алфавита: 0, S, (, ), +, ×, ⊃, ¬, ∀ и
=. Другие логические связки можно выразить через ⊃, ¬ и
∀. Например, A∨B≡¬A⊃B, а ∃xA(x) ≡¬∀x¬A(x).
Таким образом, основной символ алфавита
получает в качестве гёделева номера число, не
превосходящее 10. Например, соответствие может быть
задано таблицей:
0
S
( ) +
× ⊃ ¬ ∀
=
1 2 3 4 5 6 7 8 9 10
Предметным переменным сопоставляются простые числа, большие 10 (скажем, x
получает номер 11, y – номер 13 и т. д.).
3
Формула получает номер по правилу, которое лучше всего пояснить на примере.
Рассмотрим формулу ∀x (x×S(0) = x), которая утверждает, что число не меняется при
умножении на 1. Эта формула содержит 12 символов, причем некоторые из них (скажем,
x) входят несколько раз. Возьмем первые 12 простых чисел, возведем каждое из них в
степень
, равную номеру соответствующего символа и перемножим полученные числа.
Найденное так число
2
9
×3
11
×5
3
×7
11
×11
6
×13
2
×17
3
×19
1
×23
4
×29
10
×31
11
×37
4
=
3512466963791134964962551783462053411408361516343794496506561501312862272000
и будет гёделевым номером этой формулы.
Последовательность формул (которая может составлять доказательство) F
1
, F
2
,…,
F
m
получает гёделевый номер
m
G
m
GG
p××× ...32
21
,
где p
m
есть m-е простое число, а G
1
, G
2
,… – гёделевы номера соответственно формул
F
1
, F
2
, … .
Таким образом каждой формуле или последовательности формул ставится в
соответствие единственное натуральное число. Не всякое натуральное является геделевым
номером, но всякий гёделевый номер однозначно определяет соответствующее
выражение. Это следует из теоремы о единственности разложения на простые множители:
для целого числа, большего 1, существует единственный (с точностью до порядка) способ
записать его
в виде произведения степеней простых чисел.
3
Если мы расширяем язык, добавляя счетное число новых функциональных символов, то нумерацию
символов алфавита меняем следующим образом: предметным переменным сопоставляются простые числа,
большие 10 и имеющие вид 3n+1, а новым функторам сопоставляются простые числа, большие 10 и
имеющие вид 3n+2.

Страницы