Чего не могут вычислительные машины: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 325:
'''Конец доказательства'''
<b>Следствие 1</b>
Есть машина, непродолжимая до всюду определённой.
Таковой является, в частности, любая универсальная машина.
Заметим, что существование неразрешимых проблем и непополнимых частичных функций не
зависит от частностей теории алгоритмов. Оно следует из фундаментальнейшего факта наличия универсальной
машины, и практически лишь из него.
Отсюда следует важнейший практический вывод: понятие ошибки в программе не устранимо даже <b>в принципе</b>.
С ними необходимо бороться (как и с бесами в душе), но победить их до конца невозможно (как и Дьявола).
Теперь приведём список известных классических неразрешимых проблем, который может служить ориентиром при рассмотрении
других проблем (в частности, если задачу удается алгоритмическим преобразованием свести к неразрешимой,
то она тоже неразрешима).
# Равенство функций, вычисляемых двумя программами.
# Равенство нулю результата данной программы для определённых входных данных (наборе входных данных).
# Пустота (соответственно, и непустота) разрешимого множества,
представленного программой, которая для каждого элемента может
определить, принадлежит он этому множеству или нет.
# Определение количества шагов, которое сделает программа до завершения.
# Определение количества памяти, которое может понадобиться программе с динамическим выделением
памяти.
# Определение, зависит или не зависит в программе значение одной переменной от значения другой.
# Определение, пройдёт ли когда-нибудь программа по данной ветви.
# Определение, являются ли два функциональных выражения частными случаями одного и того же.
# Существование положительных натуральных чисел <math>x_i</math>, таких что <math>P(x_1,\dots,x_n)=0,</math>
где <math>P</math> — многочлен с целыми коэффициентами (наличия корня у диафантового уравнения).
# Существование решения произвольной системы уравнений в словах.
# Равенство либо неравенство (<math>\neq</math>, <math><</math>, <math>></math>) двух действительных чисел.
# Доказуемость логического утверждения с кванторами или же утверждения некоторой общепринятой формальной
теории (арифметики, анализа и т. д.).
# Определение, переходит ли когда-нибудь данный двухголовочный автомат в состояние 0. (поскольку иначе можно
было бы разрешить проблему остановки для машин Тьюринга).
==Практическая разрешимость==
|