2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Что означает "состояние" для машины Тьюринга?
Сообщение20.08.2013, 21:59 


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

 Профиль  
                  
 
 Re: Что означает "состояние" для машины Тьюринга?
Сообщение20.08.2013, 22:05 
Заслуженный участник
Аватара пользователя


06/10/08
6422
AlexeyM в сообщении #756267 писал(а):
Это цифра, буква, слово или что это?
Неважно. Это элементы некоторого конечного множества. Обычно в качестве состояний используется буква $q$ с разными индексами.
Иногда множество состояний называют алфавитом состояний, а его элементы, соответственно, символами состояния.

 Профиль  
                  
 
 Re: Что означает "состояние" для машины Тьюринга?
Сообщение20.08.2013, 22:11 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Что означает "состояние" для машины Тьюринга?
Сообщение20.08.2013, 22:30 


19/04/11
69
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 писал(а):
... и состояние машины, т.н. полное, включает как внутреннее состояние, так и слово на ленте с указанием ячейки под головкой.


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

 Профиль  
                  
 
 Re: Что означает "состояние" для машины Тьюринга?
Сообщение20.08.2013, 22:36 


03/03/13
46
AlexeyM
Не понятно, где вы взяли эти команды. В МТ нет "если ..., то...". Команда - то тройка $(\alpha, q , S)$, где $\alpha$ - символ, который будет напечатан на ленте, $q$ - состояние, в которое перейдет машина, $S$ - сдвиг вправо/влево/на месте. И для каждой пары (символ, состояние) есть определенная команда.
Цитата:
Вернуться к исходному состоянию
никто никуда не возвращается машина переходит в указанное состояние.
UPD: Я понял ваш способ записи, но обязательно определять правила для всех состояний. И все-таки проще понять запись в форме таблицы.

 Профиль  
                  
 
 Re: Что означает "состояние" для машины Тьюринга?
Сообщение20.08.2013, 22:39 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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, как я понял, словесное описание. Вроде бы там все нормально.

 Профиль  
                  
 
 Re: Что означает "состояние" для машины Тьюринга?
Сообщение20.08.2013, 23:56 


19/04/11
69
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 писал(а):
Я понял ваш способ записи, но обязательно определять правила для всех состояний. И все-таки проще понять запись в форме таблицы.


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

 Профиль  
                  
 
 Re: Что означает "состояние" для машины Тьюринга?
Сообщение22.08.2013, 19:56 
Заслуженный участник
Аватара пользователя


06/10/08
6422
AlexeyM в сообщении #756290 писал(а):
Вроде так или не совсем так?
Вроде бы и так, но мне кажется немного корявым, потому что Вы из четырех возможных ситуаций ($q_11, q_1\lambda, q_21,q_2\lambda$) три упихиваете в последний пункт.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group