Что означает "состояние" для машины Тьюринга?

[AlexeyM]

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

[Xaositect]

AlexeyM в сообщении #756267 писал(а):

Это цифра, буква, слово или что это?

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

[nikvic]

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

[AlexeyM]

Xaositect

Терминологию я немного знаю, мне бы понять, что эта терминология означает :) Если природа элементов множества неясна, как же с ним работают? Конечных множеств ведь много. Вы не могли бы указать, какова суть элементов этого множества?

И такой еще вопрос, связанный с непосредственным примером (может, так смогу разобраться):

Пусть МТ имеет алфавит $A=\left \{ 1,\lambda \right \}$, где лямбда означает пустой символ. Набор состояний управляющего устройства выражен множеством $\left \{ q_{1},\ q_{z} \right \}$. Допустим, система команд такова: $q_{1}1\rightarrow q_{1}1R; q_{1}\lambda \rightarrow q_{1}1R$.

Верно ли я понимаю, если мой "перевод" этой системы команд звучит так:
1. Если в начальном состоянии (в первой обозреваемой головкой ячейке) содержится единица, то использовать команду $q_{1}1\rightarrow q_{1}1R$. Т.е., записать в обозреваемую ячейку символ "1" и сдвинуть головку вправо. Вернуться к исходному состоянию и снова просмотреть обе команды.

2. Если в начальном состоянии (в первой обозреваемой головкой ячейке) содержится пустой символ, то использовать команду $ q_{1}\lambda \rightarrow q_{1}1R$. Т.е., записать в обозреваемую ячейку символ "1" и сдвинуть головку вправо. Вернуться к исходному состоянию и снова просмотреть обе команды.

Верный ли такой "перевод"?

-- Вт авг 20, 2013 23:31:02 --

nikvic в сообщении #756270 писал(а):

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

Да, кажется, ошибся с заголовком. Меня интересует именно термин "состояние" в применимости к управляющему устройству.

[Deffe]

AlexeyM
Не понятно, где вы взяли эти команды. В МТ нет "если ..., то...". Команда - то тройка $(\alpha, q , S)$, где $\alpha$ - символ, который будет напечатан на ленте, $q$ - состояние, в которое перейдет машина, $S$ - сдвиг вправо/влево/на месте. И для каждой пары (символ, состояние) есть определенная команда.

Цитата:

Вернуться к исходному состоянию

никто никуда не возвращается машина переходит в указанное состояние.
UPD: Я понял ваш способ записи, но обязательно определять правила для всех состояний. И все-таки проще понять запись в форме таблицы.

[Xaositect]

AlexeyM в сообщении #756275 писал(а):

Терминологию я немного знаю, мне бы понять, что эта терминология означает :) Если природа элементов множества неясна, как же с ним работают? Конечных множеств ведь много. Вы не могли бы указать, какова суть элементов этого множества?

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

AlexeyM в сообщении #756275 писал(а):

Верный ли такой "перевод"?

Да, все так. Но лучше "переведите" что-нибудь менее тривиальное. Например, $A = \{1, \lambda\}$ ($\lambda$ - пустой), $Q = \{q_1,q_2,q_z\}$ ($q_1$ - начальное, $q_z$ - терминальное), $\Pi = q_11\to q_21R, q_1\lambda\to q_z1S, q_21\to q_1\lambda R, q_2\lambda\to q_z\lambda S$.

-- Вт авг 20, 2013 23:40:01 --

Deffe в сообщении #756276 писал(а):

Не понятно, где вы взяли эти команды. В МТ нет "если ..., то...". Команда - то тройка $(\alpha, q , S)$, где $\alpha$ - символ, который будет напечатан на ленте, $q$ - состояние, в которое перейдет машина, $S$ - сдвиг вправо/влево/на месте. И для каждой пары (символ, состояние) есть определенная команда.

У AlexeyM, как я понял, словесное описание. Вроде бы там все нормально.

[AlexeyM]

Xaositect в сообщении #756277 писал(а):

Но лучше "переведите" что-нибудь менее тривиальное. Например, $A = \{1, \lambda\}$ ($\lambda$ - пустой), $Q = \{q_1,q_2,q_z\}$ ($q_1$ - начальное, $q_z$ - терминальное), $\Pi = q_11\to q_21R, q_1\lambda\to q_z1S, q_21\to q_1\lambda R, q_2\lambda\to q_z\lambda S$.

Попробую :) Насколько я понимаю, начальная конфигурация не определена, поэтому результат работы этой МТ будет зависеть от того, что написано на ленте изначально.

1. Управляющее устройство в состоянии $q_{1}$ и головка обозревает $\lambda$. В обозреваемую ячейку будет записана "1" и МТ остановится.

2. Управляющее устройство находится в состоянии $q_{1}$ и головка обозревает "1". В обозреваемую ячейку $k_{1}$ будет записан символ "1" и головка будет сдвинута вправо (упр. устройство перейдёт в состояние $q_{2}$). Если в следующей ячейке $k_{2}$ будет записан пустой символ $\lambda$, то МТ остановит работу, записав $\lambda$ в ячейку $k_{2}$. Если же в ячейке $k_{2}$ будет символ "1", то его заменят на $\lambda$, управляющее устройство сдвинет головку вправо и перейдет в состояние $q_{1}$. Ну, а дальше, в зависимости от того, что написано в ячейке $k_{3}$, МТ перейдет либо к пункту 1, либо к пункту 2.

Вроде так или не совсем так?

-- Ср авг 21, 2013 01:02:14 --

Deffe в сообщении #756276 писал(а):

Я понял ваш способ записи, но обязательно определять правила для всех состояний. И все-таки проще понять запись в форме таблицы.

Да, я сейчас как раз пытаюсь разобрать табличную запись :) Просто мне для начала хочется понять основы команд МТ, а для этого приходится задействовать такой словесный "перевод для начинающих".

[Xaositect]

AlexeyM в сообщении #756290 писал(а):

Вроде так или не совсем так?

Вроде бы и так, но мне кажется немного корявым, потому что Вы из четырех возможных ситуаций ($q_11, q_1\lambda, q_21,q_2\lambda$) три упихиваете в последний пункт.