Всюдуопределенность частично-рекурсивных функций.

[max(Im)]

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

Таким образом, надо свести такую проблему останова к первой. То есть по заданной машине Тьюринга $T$ построить частичнорекурсивную функцию (то есть вычислимую), что $T$ останавливается на всех входах тогда и только тогда когда построенная функция всюду определена.

Как определить функцию? это как-то должно быть просто...

[whitefox]

По правилам форума давать готовые ответы нельзя.
Вы должны привести свою попытку решения.
Тогда Вам укажут ошибки.

max(Im) в сообщении #528565 писал(а):

Как определить функцию? это как-то должно быть просто...

Это действительно просто. Почитайте, например, Роджерса либо Мальцева.

max(Im) в сообщении #528565 писал(а):

Таким образом, надо свести такую проблему останова к первой.

Насколько я понял, Вам нужно показать, что если существует машина Тьюринга решающая проблему общерекурсивности для любой частично рекурсивной функции, то существует и машина Тьюринга решающая проблему остановки.

max(Im) в сообщении #528565 писал(а):

То есть по заданной машине Тьюринга $T$ построить частичнорекурсивную функцию (то есть вычислимую), что $T$ останавливается на всех входах тогда и только тогда когда построенная функция всюду определена.

А это уже совершено другая проблема, и к вашей он имеет лишь косвенное отношение.