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