Проблема остановки: различия между версиями
| [отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
м r2.7.1) (робот добавил: vi:Bài toán dừng |
|||
Строка 9:
== Набросок доказательства ==
Рассмотрим множество <math>S</math> алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество <math>S</math> лексикографически (в словарном порядке), при этом каждый алгоритм получит свой порядковый номер. Назовем
* останавливается и возвращает 1, если алгоритм с номером <math>N</math> не останавливается, получив на вход <math>X</math>
* не останавливается в противном случае (если алгоритм с номером <math>N</math> останавливается, получив на вход <math>X</math>).
| |||