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