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

 

===Теорема 1===

Таким образом, если нетривиальное функциональное свойство программ перечислимо, то его дополнение не перечислимо.

В частности, не перечислимо множество машин, не заканчивающих работу при фиксированных исходных данных.

 

'''Доказательство'''

Предположим противное, что данное свойство разрешимо. Тогда имеется машина <math>\mathfrak{A}</math>, которая

всегда останавливается и даёт на ленте <math>\cdots</math>BBB<i>M</i>A<i>X</i>EEE<math>\cdots</math>

 

Итак, сделанное нами предположение о существовании машины, распознающей применимость, опровергнуто.

 

Таковой является, в частности, любая универсальная машина.

 

машины, и практически лишь из него.

 

С ними необходимо бороться (как и с бесами в душе), но победить их до конца невозможно (как и Дьявола).

 

Этот список можно продолжать очень долго. Есть и критерии, которые позволяют ответить на вопрос о неразрешимости сразу для некоторого класса свойств. Приведем самый известный и одновременно самый практически полезный из них.

 

 

 

который ничего не получает на вход, а последовательно выводит на выход объекты из этого

множества, то есть для любого объекта этого множества наступит

момент, когда алгоритм его выведет.

 

 

 

Пусть <math>P</math>&mdash; функциональное разрешимое свойство, не являющееся

тривиальным. Тогда есть такие программы <math>a</math> и <math>b</math>, что <math>P(a)</math>

истинно, а <math>P(b)</math> ложно. Поскольку <math>P</math> всюду определено, оно

либо истинно, либо ложно на программе для нигде не определённой

(второй случай рассматривается абсолютно симметрично).

<math>P(a^\prime)</math> истинно также для любой программы <math>a^\prime</math>,

вычисляющей ту же функцию, что и <math>a</math>, и ложно для любой

программы <math>b^\prime</math>, вычисляющей ту же функцию, что и <math>b</math>.

(машину, функцию, комбинатор: конкретное понятие алгоритма здесь

безразлично, слишком простое построение):

 

 

==Метод Британского музея==