Проблема отличия элемента машины Тьюринга

Question

Таким образом, язык выглядит следующим образом:

E = {# x1 # x2 ... # xi, где алфавит равен {0,1} *, и ни одна строка не может быть дубликатом другой строки}

Я пытаюсь создать диаграмму состояний для этого, но даже до этого я придумал алгоритм для его решения, но проблема, с которой я сталкивался, заключается в том, что всякий раз, когда я сравниваю первые две строки, я должен отмечать каждуюсимвол с «х», так как мне восстановить первую строку?Как и вначале, я сравниваю x1 и x2, к тому времени, когда я закончу, в x2 и все символы в x1 будут отмечены знаком «x», поэтому, когда я перехожу к x3, x1 не с чем сравнивать.

Answer 1

Вместо того, чтобы отмечать рассматриваемые символы крестиком, пометьте их специальными символами, соответствующими обозначаемым символам. Таким образом, вместо записи x для 0 и x для 1, напишите a для 0 и b для 1. На самом деле, используйте символы c и d также для замены значений в «самой ранней вещи, которую мне нужно проверить», чтобы вы могли проверьте все пары. Общее описание машины Тьюринга, использующей эту стратегию, следующее:

1. начать чтение первого ввода, заменив 0 на c и 1 на d
2. перейдите ко второму входу, и если второй вход пока совпадает, напишите a для 0 и b для 1, затем продолжите. Если это не совпадение, мы знаем, что эти входные данные не совпадают, и мы можем начать сравнение других пар. Измените вход, который вы проверяете, только на a и b и сбросьте первый вход только на 0 и 1.
3. повторите этот процесс, пропустив все a и b уже там, чтобы проверить все пары, включающие первый член.
4. как только вы проверили все пары, включающие первый член, вычеркните его (возможно, с помощью x), а затем повторите весь процесс на оставшихся входных данных

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