Массовая проблема считается
алгоритмически неразрешимой, если не существует решающего её алгоритма, который позволял бы находить решение для каждой из единичных
проблем, которые составляют массовую проблему.
Алгоритмически неразрешимые проблемы, указанные Чёрчем и Тьюрингом, слишком сложны.
В работе "В.А.Успенский. Апология математики" приведен простой пример такой проблемы.
Рассмотрим следующую игру. Игровыми принадлежностями будут служить модифицированные костяшки домино. Каждая костяшка доминоразделена пополам чертой. В каждой половине записывается цепочка из букв x и z.
Примеры цепочек.
Возможный вид пластинок (рисунок взять из книжки В.А.Успенский. Апология математики).
Обозначим изображенные костяшки буквами A, B, C, D.
Костяшки складываем друг с другом длинными сторона. При скаладывваении мы получаем некоторое слово, состоящее из букв костяшек.
Каждую костяшку разрешается воспроизводить в неограниченном количестве и создавать сочетания из повторяющихся пластинок, такие, например, как AACA. В этом примере верхней строчкой будет xxxzx, а нижней – zxzxzzzx.
Игра состоит в следующем. Объявляется некоторый конкретный набор пластинок. Далее предлагается, воспроизводя каждую из пластинок набора в необходимом количестве, приложить пластинки друг к другу так, чтобы верхняя и нижняя строчки совпали друг с другом.
Если объявленный набор состоит из одной костяшки A, то решение невозможно, так как нижняя длина всегда окажется длинне верхней. Также решения не существует для двух костяшек A и D. Но если объявить набор из четырёх пластинок A, B, C и D, то решение существует: DBCDA, – верхняя и нижняя строка одинаковы: zzzxxzzzzx.
Итак, набор объявлен.
Но, прежде чем пытаться найти такое расположение пластинок, при котором верхняя и нижняя строки окажутся одинаковыми, желательно узнать, возможно ли такое расположение в принципе. Ведь если оно невозможно, то бесперспективно его искать.
Оказывается, что не существует эффективного способа узнать - существует ли решение. Не существует такого алгоритма (он не просто неизвестен – его нет), который позволял бы для любого объявленного набора пластинок узнать, имеется ли решение. Узнать, к какой из двух категорий относится каждый отдельно взятый набор пластинок – к той, для которой решения имеются, или же к той, для которой решений нет, – это сугубо творческая задача, своя для каждого набора, а общий метод нахождения ответа для всех таких задач отсутствует.
В.А.Успенский. Апология математики.
Алгоритмически неразрешимые проблемы, указанные Чёрчем и Тьюрингом, слишком сложны.
В работе "В.А.Успенский. Апология математики" приведен простой пример такой проблемы.
Рассмотрим следующую игру. Игровыми принадлежностями будут служить модифицированные костяшки домино. Каждая костяшка доминоразделена пополам чертой. В каждой половине записывается цепочка из букв x и z.
Примеры цепочек.
- Цепочка длины ноль.
- Цепочки длины один: x, z.
- Цепочки длины два: xx, xz, zx, zz.
- Цепочки длины три: xxx, xxz, xzx, xzz, zxx, zxz, zzx, zzz.
- Цепочка произвольной длины.
Возможный вид пластинок (рисунок взять из книжки В.А.Успенский. Апология математики).
Обозначим изображенные костяшки буквами A, B, C, D.
Костяшки складываем друг с другом длинными сторона. При скаладывваении мы получаем некоторое слово, состоящее из букв костяшек.
Каждую костяшку разрешается воспроизводить в неограниченном количестве и создавать сочетания из повторяющихся пластинок, такие, например, как AACA. В этом примере верхней строчкой будет xxxzx, а нижней – zxzxzzzx.
Игра состоит в следующем. Объявляется некоторый конкретный набор пластинок. Далее предлагается, воспроизводя каждую из пластинок набора в необходимом количестве, приложить пластинки друг к другу так, чтобы верхняя и нижняя строчки совпали друг с другом.
Если объявленный набор состоит из одной костяшки A, то решение невозможно, так как нижняя длина всегда окажется длинне верхней. Также решения не существует для двух костяшек A и D. Но если объявить набор из четырёх пластинок A, B, C и D, то решение существует: DBCDA, – верхняя и нижняя строка одинаковы: zzzxxzzzzx.
Итак, набор объявлен.
Но, прежде чем пытаться найти такое расположение пластинок, при котором верхняя и нижняя строки окажутся одинаковыми, желательно узнать, возможно ли такое расположение в принципе. Ведь если оно невозможно, то бесперспективно его искать.
Оказывается, что не существует эффективного способа узнать - существует ли решение. Не существует такого алгоритма (он не просто неизвестен – его нет), который позволял бы для любого объявленного набора пластинок узнать, имеется ли решение. Узнать, к какой из двух категорий относится каждый отдельно взятый набор пластинок – к той, для которой решения имеются, или же к той, для которой решений нет, – это сугубо творческая задача, своя для каждого набора, а общий метод нахождения ответа для всех таких задач отсутствует.
В.А.Успенский. Апология математики.
Комментариев нет:
Отправить комментарий