Арифметические функции. (Лекция 10) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Арифметические функции. (Лекция 10), слайд №1

Арифметические функции. (Лекция 10), слайд №2

Арифметические функции. (Лекция 10), слайд №3

Арифметические функции. (Лекция 10), слайд №4

Арифметические функции. (Лекция 10), слайд №5

Арифметические функции. (Лекция 10), слайд №6

Арифметические функции. (Лекция 10), слайд №7

Арифметические функции. (Лекция 10), слайд №8

Арифметические функции. (Лекция 10), слайд №9

Арифметические функции. (Лекция 10), слайд №10

Арифметические функции. (Лекция 10), слайд №11

Арифметические функции. (Лекция 10), слайд №12

Арифметические функции. (Лекция 10), слайд №13

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Арифметические функции. (Лекция 10). Доклад-сообщение содержит 13 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Слайд 2

Описание слайда:

Теорема Множество арифметических функций n-переменных несчетно.

Слайд 3

Описание слайда:

Слайд 4

Описание слайда:

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Так как каждой вычислимой арифметической функции соответствует хотя бы одна машина Тьюринга, а машин Тьюринга א 0, то значит вычислимых арифметических функций никак не больше чем א 0. Получим: |ВАФ| ≤ א 0 . Так как каждой вычислимой арифметической функции соответствует хотя бы одна машина Тьюринга, а машин Тьюринга א 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 (0,0,0)=f0(0,0,0)+1 g (0,0,1)=0 g (0,1,0)=0 g (1,1,1)=f1(1,1,1)+1 g (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 вычислима. 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 переменных. Т.о. видно, что диагональная функция g(x1,…,xn) принадлежит множеству вычислимых арифметических функций n переменных. Раз построенная функция принадлежит к множеству вычислимых арифметических функций, то она должна быть среди ранее эффективно перечисленных функций, но по построению она не может быть среди них, так как от каждой функции она отличается хотя бы в одной точке. Получили противоречие, следовательно, исходное предположение неверно и вычислимые арифметические функции n переменных нельзя эффективно перечислить, Q.E.D.

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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