2014 dxdy logo

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

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


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


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



Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней. На страницу 1, 2  След.
 
 Номенклатура машины Тьюринга
Сообщение03.05.2017, 00:03 
Аватара пользователя


05/11/11
91
Задача звучит так:

МТ с внешним алфавитом $\{0, 1\}$ и алфавитом внутренних состояний $\{p_1, p_2, \ldots, p_n\}$ определяется следующей функциональной таблицей:

Изображение

Определите, в какое слово перерабатывает МТ каждое из следующих слов (в начальный момент времени МТ находится в первом состоянии и обозревает крайнюю правую ячейку, в которой записан пустой символ 0, а в следующей слева ячейке уже записана 1).

а) 0111011101110
б) 0110111010
в) 01110110
г) 011011110

======

Видимо, у меня какое-то недопонимание с определением МТ (или у автора задания). Я понял так, что здесь лента полубесконечная, но простирается влево, $d_1$ означает переход влево, $d_{-1}$ -- переход вправо. Ибо если считать $d_1$ переходом вправо, то МТ переходит за крайнюю правую позицию на первом шаге для каждого слова.

Однако тогда получается, что поскольку все данные слова оканчиваются на 10, на каждом из них МТ пройдёт последовательно состояния 1-2-3-4-5, в пятом состоянии будет обозревать крайнюю правую ячейку. За это время последние две цифры 10 она заменит на 01 (на другие даже на посмотрит) и затем попытается перейти в состояние 6 и одновременно сдвинуть головку за крайнюю правую позицию. Получается, что эта МТ неприменима ко всем данным числам. Такое, конечно, возможно, но "меня терзают смутные сомнения".

Я нигде не ошибаюсь?

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение03.05.2017, 08:42 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Как минимум, дико выглядит наличие состояния $p_{15}$ внизу самой последней колонки состояний, поскольку больше нигде это состояние не упоминается.
qx87 в сообщении #1213787 писал(а):
Я понял так, что здесь лента полубесконечная, но простирается влево, $d_1$ означает переход влево, $d_{-1}$ -- переход вправо.

Это вы "по гуглу" учитесь? :shock: Ведь иначе вы бы обязательно знали, как обозначается команда перемещения каретки, упомянутая в задании, такие вещи обязательно разъясняются на лекциях и семинарах.

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение03.05.2017, 16:18 
Аватара пользователя


05/11/11
91
Я в своё время учился вот по этим книгам. Их же в своё время оцифровал и выложил в открытый доступ. Лектор мой по дискретной математике, Алексей Иванович Белоусов, -- автор одноимённого учебника (номер XIX) из этой серии. У меня даже этот учебник есть свой, с его автографом (который он ставит только после пятёрки на экзамене). У нас переходы обозначались буквами S, L, R, что исключало всякую неоднозначность. И как работать с нашими, "бауманскими" машинами Тьюринга я хорошо знаю.

Здесь же в задании всё по-другому, ничего не пояснено, приходится додумывать. В этом и прошу помощи.

Состояние $p_{15}$, как я понимаю, заключительное. Поэтому и не упоминается больше нигде.

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение03.05.2017, 16:39 


06/06/13
71
qx87 в сообщении #1213787 писал(а):
Я понял так, что здесь лента полубесконечная, но простирается влево, $d_1$ означает переход влево, $d_{-1}$ -- переход вправо.
Почему не считать, что лента простирается вправо, $d_1$ означает переход вправо, $d_{-1}$ -- переход влево? Такое соглашение более стандартно.

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение03.05.2017, 19:08 
Заслуженный участник


27/04/09
28128
Потому что в задании написано, что
qx87 в сообщении #1213787 писал(а):
в начальный момент времени МТ находится в первом состоянии и обозревает крайнюю правую ячейку

Вообще, конечно (здравствуйте, я К. О.), перво-наперво надо узнать, откуда такое задание, и нет ли там чего-то ещё кроме этого задания. Если нет, а не ну ли его тогда?

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение03.05.2017, 19:20 
Аватара пользователя


05/11/11
91
3D Homer в сообщении #1213895 писал(а):
Почему не считать, что лента простирается вправо, $d_1$ означает переход вправо, $d_{-1}$ -- переход влево? Такое соглашение более стандартно.

Я ж написал:
qx87 в сообщении #1213787 писал(а):
Ибо если считать $d_1$ переходом вправо, то МТ переходит за крайнюю правую позицию на первом шаге для каждого слова.


-- 03.05.2017, 20:25 --

arseniiv в сообщении #1213923 писал(а):
Вообще, конечно (здравствуйте, я К. О.), перво-наперво надо узнать, откуда такое задание, и нет ли там чего-то ещё кроме этого задания. Если нет, а не ну ли его тогда?


Здравия желаю, товарищ капитан!
Само собой, в этом направлении я тоже работаю. Но в силу специфичности моей ситуации матожидание времени получения ответа с той стороны на $N$ порядков может превосходить оное времени расколупывания истины коллективным разумом. И на $n$ порядков -- собственным :)

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение03.05.2017, 19:27 
Заслуженный участник


27/04/09
28128
Не завидую вам. :|

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


01/03/06
13626
Москва

(Оффтоп)

qx87 в сообщении #1213926 писал(а):
Но в силу специфичности моей ситуации матожидание времени получения ответа с той стороны на $N$ порядков может превосходить оное времени расколупывания истины коллективным разумом. И на $n$ порядков -- собственным :)

Решаете за копейку малую контрольные выдающимся дубкам, которые только и способны, что скопировать и выслать текст своей к.р., но дать пояснения не могут, поскольку "он эти куклы десять минут назад впервые увидел"? :shock:

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение03.05.2017, 23:39 
Аватара пользователя


05/11/11
91
Да. Пишете забесплатно комменты, не имеющие смысла?

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение04.05.2017, 00:14 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва

(Оффтоп)

qx87 в сообщении #1213968 писал(а):
Да. Пишете забесплатно комменты, не имеющие смысла?
Много среди нас тех, кто дюже не любит жлобов, извращающих смысл высшего образования, решая за деньги дубкам их д.з., поэтому смысл у моего комментария и вашего ответа есть. Вполне недвусмысленный смысл.

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение04.05.2017, 10:01 
Аватара пользователя


05/11/11
91
Подскажи тогда, как по-твоему вернуть его, этот смысл?

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение04.05.2017, 20:15 


20/03/14
12041
 !  qx87
Замечание за фамильярность. На форуме принято общение на "Вы".


qx87 в сообщении #1213997 писал(а):
как по-твоему вернуть его, этот смысл?

А он никуда не ушел.

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение06.05.2017, 23:22 
Аватара пользователя


05/11/11
91
Lia в сообщении #1214127 писал(а):
 !  qx87
Замечание за фамильярность. На форуме принято общение на "Вы".



Жлобами людей на форуме тоже принято называть, это не считается фамильярностью? За это участник замечание не получит, я правильно вас понимаю?

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение06.05.2017, 23:28 


20/03/14
12041
 !  qx87
Большая просьба не выяснять проблемы, связанные с модерированием и т.п. в тематических разделах. Для этого есть ЛС и раздел "Работа форума". Вы можете обратиться туда.

 Профиль  
                  
 
 Re: Номенклатура машины Тьюринга
Сообщение09.05.2017, 20:27 
Аватара пользователя


05/11/11
91
Не буду. Я вас понял: жлобами можно, на ты -- нельзя. Всё же просто.

Тему можно закрывать, всё равно стараниями гражданина она скатилась незнамо во что.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 16 ]  На страницу 1, 2  След.

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



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

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


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

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