Чего не могут вычислительные машины: различия между версиями
Содержимое удалено Содержимое добавлено
Greck (обсуждение | вклад) |
Greck (обсуждение | вклад) |
||
Строка 288:
===Теорема 1===
Свойство
«''Машина Тьюринга'' <math>\mathfrak{M}</math> останавливается, будучи запущенной на данных <math>X</math>»▼
неразрешимо. ▼
▲''Машина Тьюринга'' <math>\mathfrak{M}</math> останавливается, будучи запущенной на данных <math>X</math>
▲неразрешимо.
Таким образом
В частности, не перечислимо множество машин, не заканчивающих работу при фиксированных исходных данных.
Строка 327 ⟶ 325 :
<b>Следствие 1:</b> Есть машина, непродолжимая до всюду определённой.
Таковой является, в частности, любая универсальная машина.
Строка 353 ⟶ 349 :
# Существование положительных натуральных чисел <math>x_i</math>, таких что <math>P(x_1,\dots,x_n)=0,</math> где <math>P</math> — многочлен с целыми коэффициентами (наличия корня у диафантового уравнения).
# Существование решения произвольной системы уравнений в словах.
# Равенство либо неравенство (<math>\neq</math>,
# Доказуемость логического утверждения с кванторами или же утверждения некоторой общепринятой формальной теории (арифметики, анализа и т. д.).
# Определение, переходит ли когда-нибудь данный двухголовочный автомат в состояние 0. (поскольку иначе можно было бы разрешить проблему остановки для машин Тьюринга).
Этот список можно продолжать очень долго. Есть и критерии, которые позволяют ответить на вопрос о неразрешимости сразу для некоторого класса свойств. Приведем самый известный и одновременно самый практически полезный из них.
<b>Определение 2:</b> Свойство <math>P</math> программ называется <b>функциональным</b>, если для любых двух программ <math>a</math>, <math>b</math>, вычисляющих одну и ту же функцию, <math>P(a) \iff P(b)</math>.▼
<b>Теорема 2</b> (Теорема Райса-Успенского): Есть лишь два разрешимых функциональных свойства программ: тождественно истинное и тождественно ложное.▼
▲Свойство <math>P</math> программ называется <b>функциональным</b>, если для любых двух программ
▲Есть лишь два разрешимых функциональных свойства программ: тождественно истинное и тождественно ложное.
Множество объектов называется <b>перечислимым</b>, если есть алгоритм,
Строка 390 ⟶ 380 :
вычисляющей ту же функцию, что и <math>a</math>, и ложно для любой
программы <math>b^\prime</math>, вычисляющей ту же функцию, что и <math>b</math>.
Рассмотрим теперь произвольную программу <
(машину, функцию, комбинатор: конкретное понятие алгоритма здесь
безразлично, слишком простое построение):
Она будет вычислять <math>b(x)</math>, если <math>f(0)</math> выдаст какое-то значение, и нигде не определённую функцию,▼
▲Она будет вычислять <
<b>Конец доказательства</b>
| |||