Ребра л-мерного гиперкуба

Существует много других аспектов этих головоломок. Например, Л. Дики с математического факультета Универ-

ситета Ватерлоо в Онтарио напомнил мне, что решение головоломки «Китайские кольца» эквивалентно также «прохождению» по ребрам л-мерного гиперкуба.

Выше мы установили, что задачу о башне с и дисками можно решить за 2я — 1 шага, если пользоваться при этом тремя стержнями. Интересно заметить, что число шагов значительно уменьшается при использовании большего числа стержней — оно равно 2л — 1 для п + 1 стержней. А какая картина наблюдается в интервале от 3 до п + 1 стержней? По какому закону меняется минимальное число шагов для решения в зависимости от числа используемых стержней? Было бы интересно заняться этим вопросом в одной из последующих статей. В то время как я пишу эти строки, энтузиасты размышляют над задачей с четырьмя стержнями, а также над головоломкой, которую Мартин Гарднер называет «дьявольской версией башни» (или японской головоломкой).

ТРИ головоломки о бобре-работяге, о писанные в августовском номере журнала, были решены М. Мэйни из г. Палатин (шт. Иллинойс). Его бобр- работяга с двумя состояниями показан ниже. Начиная с чистой ленты, он записывает 4 единицы, а затем останавливается.

Решение Мэйни лучше описать на словах. Машина Тьюринга, стирающая единственную единицу, записанную на чистой ленте, пользуется двумя единицами в качестве маркеров. На каждой стадии она проходит ленту от одной единицы к другой и проверяет ячейки, находящиеся непосредственно за ними. Если там находится единица, которую требуется стереть, то машина стирает все 3 единицы и останавливается. Если единицы там нет, машина передвигает маркер на одну ячейку дальше и возвращается к другому маркеру.

 

0 Коментариев

Вы можете быть первым =)

Оставить коментарий