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

Свойство

{{Рамка}}

{{Акмар}}

неразрешимо.

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

 

 

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

а затем, в случае, если результат равен 1, запускает зацикливающуюся машину.

Таким образом, <math>\mathfrak{B}</math> определена на <math>\cdots</math>BBB<i>M</i>EEE<math>\cdots</math>

то есть когда машина <math>\mathfrak{M}</math> некорректно работает на собственной программе.

 

Что же получается, если применить <math>\mathfrak{B}</math> к \textsf{<math>\cdots</math>BBB<math>B</math>EEE<math>\cdots</math>}?

Если результат определён, то, по построению, машина <math>\mathfrak{A}</math> на

<math>\mathfrak{B}</math> на \textsf{<math>\cdots</math>BBB<math>B</math>EEE<math>\cdots</math>} не определена. Если же результат не определён,

 

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

 

==Практическая разрешимость==