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

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

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

Может.

011 -> 1001 -> 10110

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

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

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

ссылка

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

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

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

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

(15 Апр 13:40) falcao

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

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

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

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

(15 Апр 18:04) falcao

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

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

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

(16 Апр 1:19) falcao

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

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

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

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

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

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

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

отмечен:

×732
×12
×10
×10
×5

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

показан
106 раз

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

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

по почте:

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

по RSS:

Ответы

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

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