Проблема остановки: различия между версиями
[отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
м откат правок 109.110.43.57 (обс) к версии MBHbot |
финитных -> конечных |
||
Строка 8:
== Набросок доказательства ==
Рассмотрим множество <math>S</math> алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество <math>S</math> (это возможно, поскольку оно является множеством
* останавливается и возвращает 1, если алгоритм с номером <math>N</math> не останавливается, получив на вход <math>X</math>
* не останавливается в противном случае (если алгоритм с номером <math>N</math> останавливается, получив на вход <math>X</math>).
|