существует ли алгоритм, который выписывает все алгоритмы, которые не останавливаются?
- такой вопрос я встретил в книжке Китаев, Шень, Вялый "Классическите и квантовые вычисления", и что-то он меня ввел в раздумья.
Понятно, что все входные данные алгоритма можно зашить в самом алгоритме.
Понятно, что все алгоритмы можно некоторым образом занумеровать.
Казалось бы, этот алгоритм (назовем его алгоритм A) (если он существует) генерирует множество не останавливающихся алгоритмов; к нему можно получить дополнение (назовем его алгоритм B), и мы будем для каждого алгоритма знать останавливается он или нет, а как известно, такой алгоритмической процедуры не существует.
Но как алгоритмически посчитать дополнение к этому бесконечному множеству?
Если этот алгоритм A выписывает алгоритмы, которые не останавливаются, в некотором заранее известном порядке (например в котором мы занумеровали все алгоритмы), то посчитать такое дополнение не составит труда: после того, как этот алгоритм A выдал очередной номер МТ, которая не останавливается, алгоритм B выдает номера всех МТ, которые находятся между предпоследним и последним номерами, выданными алгоритмом A.
А как быть, если алгоритм A выписывает алгоритмы в некотором заранее НЕизвестном порядке?
В этом случае у меня не получается придумать алгоритм B.
Может ли такой алгоритм A существовать?
В принципе, вопрос задан без уточнения, какой из случаев имеет место быть
, по этому и во втором случае должно быть так же как и в первом, но как это доказать?
