Доказать, что всякая частично рекурсивная функция является вычислимой

задан 19 Июн '19 21:58

@Мария125Masha: чаще всего определение вычислимой функции в таком виде и даётся (тезис Чёрча). А какое было у Вас в курсе?

(19 Июн '19 22:22) falcao

Мы говорили, что арифметическая функция называется частично рекурсивной, если она имеет частично рекурсивное описание

(20 Июн '19 1:01) Мария125Masha

А тезис Чёрча мы формулировали в другую сторону, т.е. всякая вычислимая функция является частично рекурсивной

(20 Июн '19 1:04) Мария125Masha

@Мария125Masha: что такое частично рекурсивная функция, это понятно. Вопрос был в том, как у вас определялась вычислимость.

(20 Июн '19 2:13) falcao

Ааа, извините, невнимательно прочитала сообщение. Мы сначала вводили определение, а затем признак. Арифметическая функция наз-ся вычислимой, если существует алгоритм её вычисляющий. Арифметическая функция f (n-местная) является вычислимой <=> когда для любого кортежа Х длины n выполняются два условия: 1)если функция f определена на кортеже Х, то алгоритм, вычисляющий функцию f применим к Х и результат работы алгоритма, вычисляющего функцию f совпадает со значением функции f на этом кортеже; 2)если функция f не определена на кортеже Х,то алгоритм, вычисляющий функцию f не применим к Х

(20 Июн '19 3:27) Мария125Masha

@Мария125Masha: определение вычислимой функции в таком виде базируется на интуитивном понимании того, что такое "алгоритм". Одной из основных целей курса теории алгоритмов является разработка строгого понимания того, что мы понимаем под алгоритмом. И делается это на основе рекурсивных функций. Ясно, что всякая рекурсивная функция задаёт некоторый алгоритм её вычисления. В этом мы непосредственно убеждаемся для каждого из пунктов определения. Но это не доказательство (так как строгим понятием алгоритма мы в этот момент не располагаем), а всего лишь интуитивное обоснование тезиса Чёрча.

(20 Июн '19 8:01) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×194

задан
19 Июн '19 21:58

показан
283 раза

обновлен
20 Июн '19 8:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru