Чего не могут вычислительные машины: различия между версиями

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