С конечной последовательностью нулей и единиц разрешается производить следующие операции: заменять 01 на 100 или на 110. Может ли для некоторой начальной последовательности процесс замен продолжаться бесконечно?

задан 15 Апр '18 0:29

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

Может.

011 -> 1001 -> 10110

После двух преобразований внутри появилось то же самое слово, с которого всё начиналось. Поэтому дальше, применяя те же преобразования, будем получать по дополнительной 1 слева и 0 справа.

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

Задача тематически порадовала, потому что преобразованиями слов я сам немало занимался, и продолжаю это делать :)

ссылка

отвечен 15 Апр '18 2:26

@falcao, большое спасибо! Что понимать под преобразованиями слов? Это слишком общая тема. Если учесть, что все компьютерные программы в конечном итоге представляют из себя последовательность битов, то под преобразованиями слов можно понять всё, что угодно :)

(15 Апр '18 10:06) Казвертеночка
1

@Казвертеночка: при изучении алгебраических систем (групп, полугрупп) с комбинаторной точки зрения, возникает широкий класс задач, когда в словах разрешается заменять те или иные подслова по определённым правилам. То есть рассматриваются односторонние или двусторонние замены подслов вида u->v, как в условии задачи. В этой области есть масса интересных открытых проблем, которые зачастую очень просто формулируются.

(15 Апр '18 13:40) falcao

@falcao, Вы пишете: "В этой области есть масса интересных открытых проблем, которые зачастую очень просто формулируются." ........ Прошу прощение за занудство, но мне стало крайне любопытно!

(15 Апр '18 17:00) Казвертеночка
1

@Казвертеночка: например, есть такая проблема. Дано одно соотношение вида u=v (алфавит можно считать двухбуквенным). В любом слове можно менять любое вхождение подслова u на v, и наоборот. Ни одна из таких замен не обязательна, порядок замен произволен. Если от одного слова можно перейти к другому при помощи этих замен, то такие слова называются "равными" (относительно заданного фиксированного правила u=v). Всегда ли существует алгоритм распознавания "равенства"?

Известно, что если правил три (u1=v1, u2=v2, u3=v3), то не всегда (это один из ранних результатов Ю.В.Матиясевича).

(15 Апр '18 18:04) falcao

@falcao, жутко интересно! Спасибо, что просвещаете.

(16 Апр '18 0:50) Казвертеночка

@Казвертеночка: "раз уж пошла такая пьянка" (с), то вот ещё красивая проблема, которая стоит много лет. Пусть мы в каком-то слове встретили троекратный повтор произвольного слова X, то есть слово имело вид ...XXX... . Тогда разрешается из трёх секций оставить только две: ...XX... . Разрешается также совершать обратное преобразование, также с любым вхождением вида XX, заменяя его на XXX. Спрашивается, есть ли алгоритм, который по двум словам определяет, может ли одно быть получено из другого такого рода элементарными преобразованиями.

(16 Апр '18 1:19) falcao

Приведу заодно классический пример для случая, когда XX можно менять на X, и обратно (эта задача решена). КОЛОКОЛ ~ КОКОЛОКОЛ (удвоили первое КО) ~ КОКОЛ (убрали повтор слова ОКОЛ в конце) ~ КОЛ (убрали повтор КО).

В обоих задачах можно считать без ограничения общности, что сначала слово несколько раз удлиняли, а потом несколько раз укорачивали.

(16 Апр '18 1:22) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,009
×14
×13
×10
×6

задан
15 Апр '18 0:29

показан
179 раз

обновлен
16 Апр '18 1:22

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

по почте:

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

по RSS:

Ответы

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

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