Машина Тюринга

[nbyte]

Здравствуйте.
Помогите пожалуйста понять как например решить следующий пример

Цитата:

Напишите машину Тюринга со следующим множеством $\[\Sigma = \{ 0,1,\beta \}$, которая считает функцию:

$$\[f(x) = \{ _{0}^{1}\]$$

1, если в слове x нечетное число едениц
0, в другом случае

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

P.S. У меня из MathTyp'а невыходит никак скопировать формулу с русскими буквами, как правильно оформить формулу?

[Профессор Снэйп]

nbyte в сообщении #261153 писал(а):

как правильно оформить формулу?

$$ f(x) = \begin{cases} 1, &\text{в слове }x\text{ нечётное число единиц} \\ 0, &\text{в противном случае} \end{cases} $$

[math]$$
f(x) =
\begin{cases}
1, &\text{в слове }x\text{ нечётное число единиц} \\
0, &\text{в противном случае}
\end{cases}
$$[/math]

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

Вот первые вопросы, которые приходят в голову:

1) Машина с одной лентой или с несколькими?
2) Если лента одна, то она неограничена с обоих концов или ограничена слева?
3) Какие команды допускаются?
4) Каков формат входных данных?
5) Каков формат выходных данных?
6) $\beta$ у Вас символ пустой ячейки или что-то иное?

-- Чт ноя 12, 2009 16:12:31 --

nbyte в сообщении #261153 писал(а):

Очень былобы хорошо если ктонибудь подсказал каконибудь ресурс

Пишите по русски грамотно!!! На такие вопросы даже реагировать не хочется.

[Maslov]

Ещё пара вопросов по поводу приведённой задачи:
1. Каково начальное положение каретки относительно анализируемого слова?
2. Где должен быть напечатан ответ?

[Профессор Снэйп]

Maslov в сообщении #261177 писал(а):

Ещё пара вопросов по поводу приведённой задачи:
1. Каково начальное положение каретки относительно анализируемого слова?
2. Где должен быть напечатан ответ?

Это мои вопросы под номерами 4 и 5

[nbyte]

Попытаюсь ответить на вопросы, насколько смогу

Цитата:

Вот первые вопросы, которые приходят в голову:

1) Машина с одной лентой или с несколькими?
2) Если лента одна, то она не ограничена с обоих концов или ограничена слева?
3) Какие команды допускаются?
4) Каков формат входных данных?
5) Каков формат выходных данных?
6) $\beta$ у Вас символ пустой ячейки или что-то иное?

1)С одной
2)С обоих сторон ограничена c "b"
3)
Вправо - R
Влево - L
В некуда - N
4)Лента, где посередине некая последовательность символов ограниченных с двух сторон пустыми символам (b), каретка стоит на первом элементе (не пустом).
5)Ответ ограниченный пустыми символами с обоих сторон.
6) Символ пустой ячейки

Цитата:

1. Каково начальное положение каретки относительно анализируемого слова?
2. Где должен быть напечатан ответ?

1)На первом не пустом элементе.
2)На ленте вместо входящих символов (ограниченных с двух сторон пустыми символами)

Вроде так надо, возможно я где-то ошибаюсь.

[nbyte]

Цитата:

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

Самая простая, с одной лентой.
Ну или я могу ещё больше уточнить если нужно.

[Xaositect]

А гуглить сами не пробовали?

http://lib.custis.ru/index.php/Машина_Тьюринга
http://lib.custis.ru/index.php/Машина_Тьюринга:Распознавание_четности

[nbyte]

Спасибо Xaositect, за статьи.
Очень помогло, что оказывается вместо $q_1, q_2... q_n$, в принципе можно использовать другие названия.
Только у нас почему-то такого никто не использует. Пишут $q_1, q_2... q_n$, что очень сбивает с толку.

[Maslov]

nbyte в сообщении #261391 писал(а):

Только у нас почему-то такого никто не использует. Пишут $q_1, q_2, ..., q_n$, что очень сбивает с толку.

В формальном определении машины Тьюринга множество состояний принято обозначать буквой $Q$, поэтому элементы этого множества логично обозначать $q_1, q_2, ...$.
А что в этом сбивающего с толку?

[nbyte]

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

[Профессор Снэйп]

nbyte в сообщении #261277 писал(а):

3)
Вправо - R
Влево - L
В некуда - N

Команды обычно не состоят из одного символа! Из четырёх или из пяти (не считая стрелочки).

Напишите пример команды.

-- Пт ноя 13, 2009 02:07:06 --

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

А гуглить сами не пробовали?

http://lib.custis.ru/index.php/Машина_Тьюринга
http://lib.custis.ru/index.php/Машина_Тьюринга:Распознавание_четности

Боюсь, что там по ссылкам совершенно не то, что ему надо.

-- Пт ноя 13, 2009 02:08:22 --

nbyte в сообщении #261277 писал(а):

2)С обоих сторон ограничена c "b"

У Вас лента конечная, что ли?

[nbyte]

Не там нужная информация для меня.
Я уже разобрался.

Цитата:

У Вас лента конечная, что ли?

Нет. Она ограничена бесконечным числом пустых символов с обоих сторон.