-1

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

задан 27 Фев '18 0:20

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

Если бы такая функция существовала, мы умели бы по номеру программы распознавать, задаёт ли она тождественную функцию. Но тогда мы умели бы решать проблему остановки. В самом деле, по заданной машине Тьюринга M мы можем написать такую программу, которая получает на вход число x, запускает эту машину, и в случае её остановки выдаёт значение x. Тогда факт остановки машины равносилен тому, что данная программа вычисляет тождественную функцию. Номер программы p=p(M) вычисляется явно, так как нумерация главная.

ссылка

отвечен 27 Фев '18 0:51

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

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

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

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

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

отмечен:

×589
×534
×25

задан
27 Фев '18 0:20

показан
470 раз

обновлен
27 Фев '18 0:51

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

по почте:

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

по RSS:

Ответы

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

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