Почему пустой символ не считается частью входного алфавита машины Тьюринга?

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

Интересно , что идет не так , когда вы бы сделать его частью входного алфавита, потому что фактически пустой символ , уже , кажется, часть входных данных.

Чтобы объяснить, что «кажется» в последнем предложении, рассмотрим следующее.

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

Теперь предположим, что вычисление будет впоследствии записывать символы из входного алфавита справа от этого первого пустого символа, затем возвращаться в крайнее левое положение, а также возвращаться в начальное состояние. Затем он «начнется заново» с другой ленты. По сути, теперь он начинается с другого ввода, где справа от пробела находятся символы ввода, которых раньше не было. Ввод, кажется, эффективно включает в себя пустой символ. Дальнейшее поведение машины теперь также может быть другим: после повторного столкновения с пробелом теперь будут встречаться другие символы справа.

Предположим, что этот сценарий действительно возможен, почему бы вам не рассмотреть пустую символьную часть входного алфавита и почему бы вам не разрешить включать его как часть «начального» ввода?

Возможно, это просто способ определить входные данные так, чтобы они не всегда были бесконечными?

turing-machines неразбериха
источник

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

Джошуа

Ответы:

Основная причина в том, что он позволяет машине определять конец ввода: это (символ перед) первый пробел. Если вы допустили пропуски на входе, аппарат никогда не узнает, сможет ли он найти больше входных данных, сканируя дальше вправо. Конечно, вы могли бы решить эту проблему с помощью специального символа «конец ввода», но затем вы должны настаивать на том, чтобы этого не было на входе, поэтому вы просто переместили проблему на один уровень глубже.

Это также значительно упрощает определение начальных условий: вход является непустой частью начальной ленты, которая должна быть конечной и непрерывной. И если вы хотите, чтобы пустой символ был частью входного алфавита, вы всегда можете добавить дополнительный символ (назовите его «пробел» или что-то в этом роде) и заставить машину вести себя так, как вы хотите, когда она ее видит.

Дэвид Ричерби
источник

Ах, конечно, без возможности определить конец начального ввода, некоторые вычисления были бы невозможны. Но в остальном в этом символе нет ничего особенного. И я полагаю, что терминологическая экономия заключается в использовании пустого символа, так как он нужен в любом случае в вашем алфавите. Я думаю, что это было бы более очевидно для меня, когда изначально определялось с явным символом конца ввода и примечанием, которое не было строго необходимым и часто пропускалось.

Беспорядок

Есть простые входные кодировки, которые не требуют дополнительного символа. Например, можно смоделировать четырехсимвольный алфавит, рассматривая пары символов 00, 01, 10 и 11, а затем (например) назначить декодирование . Но это значительно упрощает задачу, позволяя использовать третьего персонажа, и это не приводит к реальным недостаткам.

{00} \to 0, {11} \to 1, {10, 01} \to b

$\{00\} \rightarrow 0, \{11\} \rightarrow 1, \{10, 01\} \rightarrow b$

Йонатан N

Видя, что машине Тьюринга нужны правила, управляющие тем, что она делает, если она читает пробел, и у нее может быть правило, которое говорит ей писать пробел, не означает ли это, что пробел действительно является частью его алфавита? Я не понимаю, почему на входе не может быть пробелов. Как насчет кодирования элементов ввода с использованием непустых символов и одного пробела в качестве разделителя? Затем несколько последовательных пробелов указывают на конец ввода.

Рози Ф

@YonatanN Конечно. Это "просто", но с пустым символом проще.

Дэвид Ричерби

@RosieF Пробел является частью алфавита ленты; входной алфавит является подмножеством этого. И, конечно же, вы можете установить соглашения о том, как входные данные могут содержать пробелы при определенных обстоятельствах (как вы это сделали), но это только делает определения более сложными. Более сложные определения означают, что труднее доказать что-то о машинах Тьюринга. А поскольку машины Тьюринга действительно используются только для проверки (если вы хотите спроектировать настоящий компьютер, это не будет ТМ), это не хороший компромисс.

Дэвид Ричерби

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

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

Питер Шор
источник

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

Это различие важно, как говорили другие, чтобы машина могла определить, где заканчивается ее ввод. Это та же самая причина, по которой вы не можете (с пользой) поместить нулевой символ в середину строки в C: нулевой символ зарезервирован для обозначения «последнего ненулевого символа перед концом данных, поэтому когда вы видите это, все готово ». Если вам нужно ожидать ноль символов в середине строки, писать strlenстановится намного сложнее.

Draconis
источник