Задача на машину Тьюринга

[passenger]

Уже который день бьюсь над следующей задачей:
Построить машину Тьюринга, которая останавливается тогда и только тогда, когда на ленте присутствует две последовательности из единиц одинаковой длины. Лента бесконечная. Входной алфавит: {0,1}. Дополнительные символы использовать запрещается.

Люди, помогите! Задача не поддаётся Или может быть она не имеет решения?..

[незваный гость]

Мне кажется (я давно забыл, что такое м.Т.), что в Вашей постановке задача неразрешима. Мое подозрение связано с тем, что негде хранить более чем конечную информацию. Это приводит к регулярным языкам. Можно рассмотреть ленту, первоначально заполненую … 8, 0, 6, 0, 4, 0, 2, 0, 1, 0, 3, 0, 5, 0, 7 … (0 — одинокий 0, 1,2,3,… — соответствующее число 1), маркер на нуле между 2 и 1. Тогда нам нужно хранить произвольно большую информацию до повторения.

Совершенно иная ситуация, если Вам надо проверить наличие повтора слева от (от начального положения) маркера. Тогда правую часть ленты можно использовать как память. В этом случае задача становится разрешимой.

[maxal]

Дык надо просто реализовать сортировку пузырьком:
т.е. располагать единичные слова в порядке $w_1, w_, \dots, w_n$ так, чтобы
$|w_1| < |w_2| < \dots < |w_n|$
причем между каждыми двумя соседними словами ровно 1 ноль.
С приходом каждого нового единичного слова w', оно "всплывает" в нужную позицию путем последовательного обмена:
$w_1 0 w_2 0 \dots 0 w_n 0 w'$
$w_1 0 w_2 0 \dots 0 w' 0 w_n$
$\dots$
$w_1 0 w_2 0 \dots 0 w_k 0 w' 0 w_{k+1} 0 \dots 0 w_n$
так что $|w_k| < |w'| < |w_{k+1}|.$
Операция обмена двух соседних единичных слов $1^x$ и $1^y$ в случае $x>y$ может быть реализована на машине Тьюринга, при этом так же можно проверять равенство длин и останавливаться, если $x=y$.

[незваный гость]

"""Меня терзают смутные сомнения.""" Предполагая, что подпрограмма перестановки сделана, где гарантия, что пузырек остановится? (Может быть, мой вопрос сводится к тому, как сделать маркер начала. А это, в свою очередь, к вопросу, как сделать 00.)

[maxal]

незваный гость писал(а):

:evil:
"""Меня терзают смутные сомнения.""" Предполагая, что подпрограмма перестановки сделана, где гарантия, что пузырек остановится? (Может быть, мой вопрос сводится к тому, как сделать маркер начала. А это, в свою очередь, к вопросу, как сделать 00.)

Сделать 00 не проблема. Сначала пишем прогу для случая, когда два 00 есть, а потом еще ее модификацию для случая, когда есть только один 0: у самого первого слова заменяем первую единицу на 0 (получая таким образом два нуля) и помним этот факт, когда дело доходит до сравнения/обмена первого слова со вторым по счету. Аналогичным образом можно получить два нуля для обозначения конца сортированного участка.

Бесконечная в два конца лента тоже проблем не доставляет, в этом случае ведем поиск новых слов по одной позиции вправо и влево: вправо пробегаем отсортированный участок (до двух нулей), и смотрим есть ли сразу за ним новое слово, если есть обрабатываем, если нет ставим 1; бежим влево до двух нулей и смотрим есть ли там новое слово, есть - обрабатываем, нет - ставим единичку; затем снова бежим вправо по отсортированному участку до двух нулей, затем ищем нашу единичку, стираем ее, смотрим есть ли слово в следующей позиции, если есть - обрабатываем, нет - ставим единичку в эту позицию; затем бежим вправо до 1 после отсортированного участка и сдвигаем ее правее, если слово не найдено и т.д.
С искусственным созданием двух нулей (при необходимости) ситуация та же, что в однонаправленной бесконечной лентой.

[незваный гость]

maxal писал(а):

Сначала пишем прогу для случая, когда два 00 есть, а потом еще ее модификацию для случая, когда есть только один 0: у самого первого слова заменяем первую единицу на 0 (получая таким образом два нуля) и помним этот факт, когда дело доходит до сравнения/обмена первого слова со вторым по счету.

Как прекрасен этот мир! и как изящен. Sapienti sat est. Остальное — излишние детали.

Спасибо!

[Сомик]

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

[незваный гость]

Сомик писал(а):

Просто мы поочереди стрираем по одной единицы из двух последовательностей когда одна из них кончается, проверяем есть ли что-нибудь во второй

Ленту изменять можно и нужно. Только на ленте (бесконечно) много последовательностей, а Ваш подход не позволяет запомнить, что было на ленте до начала сравнения.

[Сомик]

Забавно.
Если на ленте бесконечно много, тобишь счетное число последовательностей, то эта задачка уже не совсем на машины тюринга... ну в смысле там ведь всегда полагается, что в любой момент времени занято лишь конечное число ячеек.

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

Тобишь сводим задачу для последовательностей длины $n_1, \dots, n_k$ к последовательностям $n_1-1, \dots, n_k-1$ и т.д.

[maxal]

Сомик писал(а):

Забавно.
Если на ленте бесконечно много, тобишь счетное число последовательностей, то эта задачка уже не совсем на машины тюринга... ну в смысле там ведь всегда полагается, что в любой момент времени занято лишь конечное число ячеек.

Кто вам такое сказал?

[Someone]

maxal писал(а):

Сомик писал(а):

Забавно.
Если на ленте бесконечно много, тобишь счетное число последовательностей, то эта задачка уже не совсем на машины тюринга... ну в смысле там ведь всегда полагается, что в любой момент времени занято лишь конечное число ячеек.

Кто вам такое сказал?

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

Это не означает, что нельзя рассматривать бесконечные входные слова, но это несколько нестандартно.

[незваный гость]

Не совсем. В задаче указано, что она останавливается тогда, и только тогда, когда есть два одинаковых слова.

Кроме того, предположим, на ленте записано конечное, но неизвестное число единиц. Как алгорифм Сомика найдет конец (границы области)? Между 1цами могут быть произвольные пропуски.

[Someone]

незваный гость писал(а):

Кроме того, предположим, на ленте записано конечное, но неизвестное число единиц. Как алгорифм Сомика найдет конец (границы области)? Между 1цами могут быть произвольные пропуски.

Пусть автор уточнит, как представляются на ленте входные данные и что они собой представляют. Но лента с бесконечным количеством записей - это действительно что-то нестандартное.

[незваный гость]

Someone писал(а):

Но лента с бесконечным количеством записей - это действительно что-то нестандартное.

Почему же с бесконечным? С конечным. Но неизвестным. И без явного маркера конца данных.

Кроме того, в задаче явно оговорено требование: машина не всегда должна останавливаться. Поэтому неопределенность границы — не проблема.

[maxal]

Someone писал(а):

Но лента с бесконечным количеством записей - это действительно что-то нестандартное.

Пересмотрел в интернете несколько определений МТ - нигде не оговаривается, что входные данные являются конечной последовательностью.