Арифметические функции. (Лекция 10)

1. ЛЕКЦИЯ 10. Арифметические функции

2. Арифметические функции

Арифметическая
определенная на
натуральных чисел
из расширенного
чисел.
функция
–
функция,
расширенном множестве
и принимающая значения
множества натуральных
Расширенное множество натуральных чисел, помимо
обычного множества натуральных чисел, включает также
число ноль (это множество обозначается N*)
Теорема
Множество арифметических функций nпеременных несчетно.

3. Доказательство

Предположим противное.
Пусть
арифметических
функций
одной
переменной счетное множество, т.е. их можно
перечислить. Тогда их можно расположить в
виде бесконечной последовательности
f0(x), f1(x), f2(x), … , fn(x),…
Построим новую функцию g(x)=fx(x)+1.
Это так называемая диагональная функция,
например:
g(0)= f0(0)+1, g(1)= f1(1)+1, g(2)= f2(2)+1, …\
g(x) отлична от всех перечисленных функций,
т.к. от каждой из функций она отличается
хотя бы в одной точке.

4. Доказательство

Например, от функции f0(x) функция g(x)
отличается в точке х=0, от функции f1(x) функция
g(x) отличается в точке х=1 и т.д. Однако по
построению
g(x)
принадлежит
множеству
арифметических функций одной переменной,
значит должна быть в списке перечисления fi(x),
т.е. совпадать с одной из перечисленных функций.
Получили противоречие, следовательно, исходное
предположение неверно, и функций одной
переменной несчетное множество.
Поскольку множество арифметических функций
одной
переменной
является
подмножеством
множества
арифметических
функций
n
переменных, то значит множество арифметических
функций n переменных несчетно, Q.E.D.

5. Вычислимые арифметические функции

Арифметическая функция называется
вычислимой, если существует алгоритм для
ее вычисления в каждой точке.
Теорема
Множество вычислимых арифметических
функций счетно.

6. Доказательство

Так как каждой вычислимой арифметической
функции
соответствует хотя бы одна машина
Тьюринга, а машин Тьюринга
‫א‬0, то значит
вычислимых арифметических функций никак не
больше чем ‫א‬0. Получим: |ВАФ| ≤ ‫א‬0 .
С другой стороны, подмножеством множества
вычислимых арифметических функций являются,
например, функции вида f(x)=n, где n – натуральное
число. Поскольку натуральных
чисел
‫א‬0, то
вычислимых арифметических функций никак не
меньше чем ‫א‬0. Получим: |ВАФ|≥ ‫א‬0 .
Значит,
мощность
множества
вычислимых
арифметических функций равна ‫א‬0, а значит оно
счетно, Q.E.D.

7. Теорема Тьюринга

Множество вычислимых арифметических
функций n переменных не поддается
эффективному перечислению.
Доказательство:
Предположим противное. Пусть множество
вычислимых арифметических функций n
переменных эффективно перечислимо. Тогда
существует алгоритм, по которому его можно
перечислить. Применим этот алгоритм. Получим
последовательность:
f0(x1,…,xn), f1(x1,…,xn),…, fn(x1,…,xn),…

8. Доказательство

Построим диагональную функцию:
fx1(x1,…,xn)+1, при x1=…=xn
g(x1,…,xn)=
0, в противном случае
Пример (пусть n=3)
g
g
g
g
g
(0,0,0)=f0(0,0,0)+1
(0,0,1)=0
(0,1,0)=0
(1,1,1)=f1(1,1,1)+1
(1,1,2)=0
По построению видно, что функция g(x1,…,xn) –
арифметическая. Докажем, что, кроме этого, она является
вычислимой. Для этого должен существовать алгоритм её
вычисления. Укажем алгоритм вычисления g(x1,…,xn). Для
любых значений x1,…,xn мы можем сначала провести
операцию сравнения.

9. Доказательство

1) Если x1=…=xn, запускаем алгоритм перечисления
вычислимых арифметических функций fi(x1,…,xn).
Этот
алгоритм
существует
в
силу
нашего
предположения. Находим функцию с номером x1, т.е.
fx1(x1,…,xn). Далее применим к ней алгоритм
вычисления в точке (x1,…,x1), т.е. вычислим
fx1(x1,…,x1). Такой алгоритм существует в силу
вычислимости функций вида fi(x1,…,xn). Прибавление
к результату вычисления единички есть тривиальная
арифметическая операция, т.о. при одинаковых
значениях аргументов g(x1,…,xn) = fx1(x1,…,x1) +1
вычислима.
2) Если условие x1=…=xn не выполняется, т.е. не все
значения аргументов равны, то значение g(x1,…,xn)
приравнивается нулю, т.о. при различных значениях
аргументов g(x1,…,xn)=0 тоже вычислима.

10.

Т.о. видно, что диагональная функция g(x1,…,xn)
принадлежит множеству вычислимых арифметических
функций n переменных.
Раз построенная функция принадлежит к множеству
вычислимых арифметических функций, то она должна
быть
среди
ранее
эффективно
перечисленных
функций, но по построению она не может быть среди
них, так как от каждой функции она отличается хотя
бы в одной точке.
Получили противоречие, следовательно, исходное
предположение
неверно
и
вычислимые
арифметические функции n переменных нельзя
эффективно перечислить, Q.E.D.

11. Теорема

Множество невычислимых арифметических
функций несчетно.
Доказательство:
Ранее доказаны два утверждения:
АФ (арифметических функций) несчетное
множество.
ВАФ (вычислимых арифметических функций)
счетное множество.
Но при этом ВАФ есть подмножество АФ, а значит
дополнение ВАФ до АФ (т.е. множество
невычислимых функций) является несчетным.
Значит, множество невычислимых арифметических
функций несчетно, Q.E.D.

12. Теорема (без док-ва)

Множество арифметических функций,
описываемых конечным числом слов, счетно и
эффективно перечислимо.

13.

Среди функций, описываемых конечным числом слов,
содержатся ВСЕ вычислимые функции
(алгоритм их
вычисления и есть описание) и еще какие то иные, типа
приведенных выше примеров f1(x) и f2(x). Однако на примере
нумерации Гёделя, рассмотренной в ходе доказательства
теоремы
об
эффективной
перечислимости
алгоритмов
Маркова, множество функций, описываемых конечным числом
слов (понятий / терминов / идей и т.д.), тоже может быть
сопоставлено с рядом натуральных чисел, т.е. является счетным
и даже эффективно перечислимым множеством.
Исходя из вышесказанного, существует несчетное множество
арифметических функций, которые не могут быть даже
описаны конечным числом слов (разумеется, об их
вычислимости не может идти и речи). Примеры таких функций
нельзя привести по определению, в силу того что любой
завершенный по своему описанию пример является уже
законченным описанием функции, а значит сама функция
попадает в множество функций, описываемых конечным
числом слов.