Чем отличается частная проблема от общей? В общей даны списки образующих и соотношений. Разве это не то же самое, что зафиксировать полугруппу? Утверждается, что вторая проблема неразрешима (обсуждалось тут ранее), но первая может быть разрешима.

Или тут имеется в виду, что может существовать программа, в код которой внесены образующие и соотношения (в этом заключается "частность"?), на вход которой подаются 2 слова, и которая может решить, равны ли они. Но не существует программы, которая на вход принимала бы образующие и соотношения и два слова и говорила бы, равны ли слова.

alt text

задан 16 Окт 6:35

10|600 символов нужно символов осталось
1

@logic: тут всё довольно просто. Общая задача -- это когда мы решаем проблему равенства слов для всех полугрупп сразу. То есть на вход подаётся список соотношений, и два слова. И надо распознать, следует ли равенство двух этих слов из данных соотношений. Частная задача возникает для каждой отдельной полугруппы, заданной соотношениями. Она может быть просто устроена, и для неё вполне может существовать разрешающий алгоритм. Там на вход подаются два слова, и надо решить, равны ли они в конкретной полугруппе.

Теоретически могло оказаться, что общая проблема неразрешима, но любая частная разрешается при помощи какого-то алгоритма, приспособленного к данной конкретной полугруппе. То есть алгоритмы могут усложняться в зависимости от сложности устройства полугруппы, но частный алгоритм, решающий проблему слов, всегда имеется. А единого для всех полугрупповых исчислений нет.

Правда, результат о неразрешимости получается в более сильной форме: строится конкретная полугруппа, про которую известно, что для неё проблема равенства слов неразрешима. Тогда общая проблема неразрешима тем более.

Однако для других задач это может быть и не так. Возьмём знаменитую X Проблему Гильберта, которую решил Матиясевич. Общего алгоритма, который говорил бы нам, имеет ли решение поданное на вход диофантово уравнение, не имеется. Однако каждое частное уравнение либо имеет решение, либо нет. Поэтому для частного случая есть программа, которая говорит "да", и есть программа, которая говорит "нет". Хотя мы не знаем, какая из двух права, но одна точно даёт верный ответ на вопрос о данном конкретном уравнении.

ссылка

отвечен 16 Окт 7:05

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×915

задан
16 Окт 6:35

показан
41 раз

обновлен
16 Окт 7:05

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru