состояние Машины Тьюринга

@Paola · Регистрация: 23.05.2013

Author24 — интернет-сервис помощи студентам

Помогите, пожалуйста/
1. Сначала мне казалось что это номер ячейки на ленте, но я встретила пример(на вики:<a href="http://upload.wikimedia.org/wikipedia/ru/5/57/Prot.gif">вот в этой табличке</a>), что читающая головка перемещается, но все рамках одного qi. Теперь не совсем понятно на что указывает состояние?
2. Кусок попавшегося примера:
q0*->q0*R
q0 1-> q0 1 R
q0 0 ->qm0 0 L
qm0 1 -> qm0 0, L
qm0 1 -> qm1 1, L
qm1 1 -> q m2 0, L
qm2 1 -> q m0 0, L

Правильно ли я понимаю его:
1. если при состоянии q0 в ячейке * записываем в нее * и передвигаем в право,
2. если 1 то записываем 1 и передвигаем в право, (если много 1 или * мы получается просто идем вправо пока не встретим 0?)
3. если 0, то записываем 0 и передвигаем влево и меняем состояние на qm0.
4. если в состоянии qm0 символ 1 то пишем 0 и идем влево....
и т.д.

Это верное понимание?

@Tuma · 16.05.2014, 19:12

Что это такое и где вы это взяли,если вы берете пример от куда-то, то лучше его скопировать,а не переписывать.А конкретно в примере из вики, "*" - это пусто,а не знак умножения.

Сообщение от Paola

2. Кусок попавшегося примера:
q0*->q0*R
q0 1-> q0 1 R
q0 0 ->qm0 0 L
qm0 1 -> qm0 0, L
qm0 1 -> qm1 1, L
qm1 1 -> q m2 0, L
qm2 1 -> q m0 0, L

И вообще-то,как только вы встретили в состояние 0 символ "*" или "х" мы двигаемся направо и при этом меняем состояние на 1.И в примере по-моему достаточно понятно написано.Сформулируйте ваш вопрос еще раз.

@Paola · 16.05.2014, 23:15 **[ТС]**

Только что заметила, что половину первого вопроса оставила у себя в голове.
По первому вопросу: мне не понятно, что вообще такое состояние? просмотрела несколько учебников и не могу найти ответ.

По второму мне в целом надо понять, правильно ли я трактую то, что происходит в тех строчках или нет(итоговый результат всего того не важен). Надо именно построчно, потому что я не могу понять либо это укладывается в рамки "если...то" либо мы выполняем каждую строчку: в q0 * переписали в ту же ячейку шагнули вправо, в след ячейке перезаписали 1, шагнули дальше, там 0 поменяли состояние на qm0... Я поняла))) Второй вариант верный, так?

Остался вопрос с состояниями...

@Tuma · 16.05.2014, 23:54

Ну состояние-это некоторая характеристика,которая будет означать конкретные действия в зависимости от него.
А команды понимаете верно,да.

@Paola 0 / 0 / 0 Регистрация: 23.05.2013 Сообщений: 11
		1
	состояние Машины Тьюринга 16.05.2014, 16:05. Показов 1224. Ответов 3 Метки нет (Все метки) Помогите, пожалуйста/ 1. Сначала мне казалось что это номер ячейки на ленте, но я встретила пример(на вики:<a href="http://upload.wikimedia.org/wikipedia/ru/5/57/Prot.gif">вот в этой табличке</a>), что читающая головка перемещается, но все рамках одного qi. Теперь не совсем понятно на что указывает состояние? 2. Кусок попавшегося примера: q0->q0R q0 1-> q0 1 R q0 0 ->qm0 0 L qm0 1 -> qm0 0, L qm0 1 -> qm1 1, L qm1 1 -> q m2 0, L qm2 1 -> q m0 0, L Правильно ли я понимаю его: 1. если при состоянии q0 в ячейке * записываем в нее * и передвигаем в право, 2. если 1 то записываем 1 и передвигаем в право, (если много 1 или * мы получается просто идем вправо пока не встретим 0?) 3. если 0, то записываем 0 и передвигаем влево и меняем состояние на qm0. 4. если в состоянии qm0 символ 1 то пишем 0 и идем влево.... и т.д. Это верное понимание? 0

@Tuma 62 / 43 / 20 Регистрация: 28.09.2013 Сообщений: 193
	16.05.2014, 19:12	2
	Что это такое и где вы это взяли,если вы берете пример от куда-то, то лучше его скопировать,а не переписывать.А конкретно в примере из вики, "" - это пусто,а не знак умножения. Сообщение от Paola* 2. Кусок попавшегося примера: q0->q0R q0 1-> q0 1 R q0 0 ->qm0 0 L qm0 1 -> qm0 0, L qm0 1 -> qm1 1, L qm1 1 -> q m2 0, L qm2 1 -> q m0 0, L И вообще-то,как только вы встретили в состояние 0 символ "*" или "х" мы двигаемся направо и при этом меняем состояние на 1.И в примере по-моему достаточно понятно написано.Сформулируйте ваш вопрос еще раз. 0

@Paola 0 / 0 / 0 Регистрация: 23.05.2013 Сообщений: 11
	16.05.2014, 23:15 [ТС]	3
	Только что заметила, что половину первого вопроса оставила у себя в голове. По первому вопросу: мне не понятно, что вообще такое состояние? просмотрела несколько учебников и не могу найти ответ. По второму мне в целом надо понять, правильно ли я трактую то, что происходит в тех строчках или нет(итоговый результат всего того не важен). Надо именно построчно, потому что я не могу понять либо это укладывается в рамки "если...то" либо мы выполняем каждую строчку: в q0 * переписали в ту же ячейку шагнули вправо, в след ячейке перезаписали 1, шагнули дальше, там 0 поменяли состояние на qm0... Я поняла))) Второй вариант верный, так? Остался вопрос с состояниями... 0

@Tuma 62 / 43 / 20 Регистрация: 28.09.2013 Сообщений: 193
	16.05.2014, 23:54	4
	Сообщение было отмечено Paola как решение Решение Ну состояние-это некоторая характеристика,которая будет означать конкретные действия в зависимости от него. А команды понимаете верно,да. 0

состояние Машины Тьюринга

Решение