Машина Тьюринга для сравнения бинарных

Question

Я пытаюсь написать, используя симуляцию Тьюринга, так в виде:
0 1 * r 0 0 0 * r 0 0 # * * 3 0 x * r 0 0 y * r 0

... программа, которая принимает два двоичных значения, разделенных символом ">", например 1010>111, который остановит-да, если слева> вправо, и остановит-нет слева> справа.

Я хотел бы сравнить решения, если вам интересно, оставьте свое решение.

Answer 1

Некоторый псевдокод для подхода, который я мог бы использовать:

1. Уберите все начальные нули из LHS и RHS, заменив их некоторым символом - (не пустым, но не 0, 1 или>).

2. Проверьте, чтобы количество оставшихся цифр в LHS и RHS было одинаковым. Если нет, мы можем сразу сказать, является ли LHS > RHS или нет, основываясь на относительной длине. Сделайте это, подпрыгивая вперед и назад и меняя 0, 1 на 0', 1' до тех пор, пока вы не выбежите на одну сторону, не отметив ту, которая вам нужна.

3. Если мы все еще проверяем, процесс теперь прост: сравните первую цифру LHS и RHS; если LHS(1) > RHS(1), то LHS > RHS; если LHS (1)

Шаг #1 - это O(n) во входной длине, поскольку мы можем сделать это за один проход слева направо. Затем мы можем вернуться к началу ленты.

Шаг № 2 - это O(n^2), поскольку ТМ в основном выполняет n шагов, n - 1 шаг, ..., 2 шага = n(n+1)/2 - 1 шаг в общей сложности для подсчета LHS и RHS,

Шаг № 3 - это O(n^2), поскольку ТМ в основном выполняет n/2 шага n/2 раза, всего в общей сложности около n^2/4 шагов.

Таким образом, временная сложность равна O(n^2), пространственная сложность равна O(n) (мы используем вход как чистую память).