Чего не могут вычислительные машины: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 290:
Свойство
{{Рамка}}
{{Акмар}}
неразрешимо.
Строка 298:
В частности, не перечислимо множество машин, не заканчивающих работу при фиксированных исходных данных.
''Доказательство''
Предположим противное, что данное свойство разрешимо. Тогда имеется машина <math>\mathfrak{A}</math>, которая
Строка 312:
а затем, в случае, если результат равен 1, запускает зацикливающуюся машину.
Таким образом, <math>\mathfrak{B}</math> определена на <math>\cdots</math>BBB<i>M</i>EEE<math>\cdots</math>
тогда и только тогда, когда <math>\mathfrak{M}</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>} не определена. Если же результат не определён,
то <math>\mathfrak{A}</math> даёт
Итак, сделанное нами предположение о существовании машины, распознающей применимость, опровергнуто.
''Конец доказательства''
==Практическая разрешимость==
|