O (n * log (n)) Машина Тьюринга с ровно 1 лентой для «равного числа a и b в данном слове»?

Question

Мне нужно собрать ТМ с ровно 1 лентой для языка L = {w |w - это слово с одинаковыми номерами a и b, например: abba, aababb}

ТМ должен иметь ТОЛЬКО 1 ленту и работать в O (n log (n)) время.Я понимаю, как сделать это в O (n ^ 2), но я понятия не имею, как сделать это n log (n).

Если у меня есть вход w = "аааа ....abbbbb .... bb "например, где w = a ^ n / 2 * b ^ n / 2 (что является наихудшим случаем), тогда я буду идти назад каждый раз (чтобы удалить каждый a для каждого b) и шагивзятый будет размером 1,2,3,4 ..... n.Сумма (от 1 до n) равна O (n ^ 2) ...

Помощь?есть идеи?

Answer 1

На высоком уровне решение, о котором я думаю, обрабатывает слово в порядке слева направо.Всегда существует префикс слова, которое было обработано, и суффикс слова, которое не было обработано.Если delta будет числом a с в префиксе минус число b с, лента будет выглядеть так в начале каждой итерации:

<big-endian abs(delta)><sign(delta)><suffix>
                                    ^
                                tape head

Чтобы обработать следующую букву(то есть первая буква в суффиксе), добавьте / вычтите одну из delta в зависимости от того, является ли буква a или b и является ли знак + или -, перемещая представлениеdelta один пробел направо в процессе.В конце проверьте, равен ли delta нулю.

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