ВАШЕ СВИДЕТЕЛЬСТВО
О ПУБЛИКАЦИИ В СМИ И РЕЦЕНЗИЯ
бесплатно за 1 минуту
Добавить материал
×
Медианары для учителей с выдачей свидетельства
Количество Ваших материалов: 0.
Авторское
свидетельство о публикации в СМИ
добавьте 1 материал
Свидетельство
о создании электронного портфолио
добавьте 5 материала
Секретный
подарок
добавьте 10 материалов
Грамота за
информатизацию образования
добавьте 12 материалов
Рецензия
на любой материал бесплатно
добавьте 15 материалов
Видеоуроки
по быстрому созданию эффектных презентаций
добавьте 17 материалов
Ахмед Изнауров свидетельство о публикации рецензия
‘видетельство о публикации скачивание доступно только автору
Свидетельство Скачивание доступно только автору
теорема о графике вычислимой функции

теорема о графике вычислимой функции

  • Научно-исследовательская работа
  • Научные работы
  • Образовательные программы
  • Повышение квалификации
  • Подготовка к тестированию
  • Информатика
  • Высшее образование

Всякий алгоритм однозначно сопоставляет допустимым начальным данным результат. Это означает, что с каждым алгоритмом однозначно связана функция, которую он вычисляет. В предыдущем параграфе были рассмотрены примеры функций, которые вычисляются с помощью алгоритма, названного машиной Тьюринга. Возникает естественный вопрос, для всякой ли функции существует вычисляющий ее алгоритм. Учитывая сформулированный ранее тезис Тьюринга, утверждающий, что функция вычислима с помощью какого-нибудь алгоритма тогда и только тогда, когда она вычислима с помощью машины Тьюринга, данный вопрос трансформируется в следующий. Для всякой ли функции можно указать вычисляющую ее машину Тьюринга? Если нет, то для каких функций существует вычисляющий их алгоритм (машина Тьюринга), как описать такие, как говорят, алгоритмически или эффективно вычислимые функции? Исследование этих вопросов привело к созданию в 1930-х гг. теории рекурсивных функций. При этом класс вычислимых функций (названных здесь рекурсивными) получил такое описание, которое весьма напомнило процесс построения аксиоматической теории на базе некоторой системы аксиом. Сначала были выбраны простейшие функции, эффективная вычисляемость которых была очевидна (своего рода "аксиомы"). Затем сформулированы некоторые правила (названные операторами), на основе которых можно строить новые функции из уже имеющихся (своего рода "правила вывода"). Тогда требуемым классом функций будет совокупность всех функций, получающихся из простейших с помощью выбранных операторов. Наша цель будет состоять в том, чтобы доказать, что этот класс функций совпадет с классом функций, вычислимых с помощью машин Тьюринга. Идея доказательства этого утверждения в одну сторону проста: сначала доказать вычислимость по Тьюрингу простейших функций, а затем вычислимость по Тьюрингу функций, получающихся из вычислимых по Тьюрингу функций с помощью выбранных операторов.