Доброго времени суток.
К сожалению, пришлось оторваться от изучения этого вопроса на 2 недели. На данный момент возвращаюсь к нему. Не могли бы Вы сказать, насколько правильны мои рассуждения относительно алгоритма Тарского-Куратовского?
Итак, проблема тотальности заключается в том, чтобы по некоторому номеру
определить, существует ли момент времени
, что для любого набора
, функция
вычислится в этот момент. Или же, вычисляет ли программа с гёделевым номером
всюду определённую функцию
?
Получаем, что множество проблемы тотальности эквивалентно множеству индексов всюду определенных функций.
Таким образом, мы можем рассматривать
- всюду определена
или же
.
Применим алгоритм Тарского-Куратовского:
- всюду определена
.
Имеем предваренную форму с видом префикса
. Множество
входит в арифметическую иерархию,
.