Существует ли такая главная универсальная вычислимая функция Uˆ(p, x), в которой множество программ I, вычисляющих тождественную функцию f(x) = x, совпадает с множеством чётных чисел? Более точно множество I задаётся как I = {p | ∀x Uˆ(p, x) = x}.

задан 3 Окт '19 18:53

10|600 символов нужно символов осталось
0

Известно, что проблема распознавания всюду определённых функций по номерам программ неразрешима. Для каждой машины Тьюринга (без входа) можно написать программу, выдающую 1 в случае остановки этой машины на любом входе. Такая программа, номер которой мы умеем вычислять (так как универсальная функция главная), всюду определена в случае остановки машины за конечное время, и нигде не определена в противном случае.

Каждую программу, вычисляющую функцию y=f(x), можно преобразовать в такую, которая в случае окончания вычислений выдаёт в качестве значения x, а не y. Преобразованная программа, номер которой вычисляется эффективно, вычисляет тождественную функцию тогда и только тогда, когда исходная функция всюду определена. Следовательно, проблема распознавания тождественности функций неразрешима, и потому множество номеров таких функций неразрешимо, то есть не может совпадать с множеством чётных чисел.

ссылка

отвечен 3 Окт '19 19:57

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,787

задан
3 Окт '19 18:53

показан
209 раз

обновлен
3 Окт '19 19:57

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

по почте:

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

по RSS:

Ответы

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

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