Чего не могут вычислительные машины: различия между версиями
Содержимое удалено Содержимое добавлено
Greck (обсуждение | вклад) |
|||
Строка 399:
==Метод Британского музея==
Многие из перечисленных выше не разрешимых проблем являются <i>перечислимыми
Например, можно построить машину, которая будет перебирать всевозможные последовательности формул, и тогда она обязательно найдёт доказательство теоремы формальной теории, если только это доказательство существует. Этот исключительно неэффективный▼
▲которая будет перебирать всевозможные последовательности формул, и тогда она обязательно найдёт доказательство
алгоритм называется <b>методом Британского музея</b>.
Но не все неразрешимые проблемы перечислимы. Для установления неперечислимости есть один важный результат, который заодно демонстрирует исключительно неэффективный метод программирования разрешимых задач (такие методы порой полезны для установления принципиальной разрешимости задачи, после чего можно спокойно искать лучший).
==Метод Маркова==
| |||