2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Машины Тьюринга
Сообщение10.05.2013, 00:17 
Аватара пользователя


12/05/12
604
Оттуда
Здравствуйте, уважаемые участники форума.Мне нужно научиться умножать, проверять на чётность,возводить в $n$ степень числа в унарном коде на машине Тьюринга. Идей - 0. Умею разве что добавлять целое число, проверять простейшие условия. Везде уже готовые коды, в которых обозначения меня приводят в ступор - куча решёток, плюсиков, чёрточек. Умею вот в таком виде работать : $1SX_{1}$ и т.д. Остальное мне совершенно непонятно. Прошу помочь разобраться с этой темой.

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 07:44 
Заслуженный участник


08/04/08
8556
cool.phenon в сообщении #721737 писал(а):
Умею вот в таком виде работать : $1SX_{1}$ и т.д.
А что это за вид? Обычно же вид такой: $a_iq_j\to a_kq_rT, T\in\{L,R,S\}$.

cool.phenon в сообщении #721737 писал(а):
Мне нужно ... в унарном коде на машине Тьюринга.
Унарный код - это $A=\{1\}$ или $A=\{\epsilon,1\}$, где $\epsilon$ - пустое слово. Первый вариант вроде не бывает, а 2-й более чем стандартен.

cool.phenon в сообщении #721737 писал(а):
Мне нужно научиться умножать, проверять на чётность,возводить в $n$ степень числа
В алфавите $A=\{\epsilon,1\}$ проверка на четность ну очень проста: стираем по две единички, пока это возможно, потом смотрим на результат.
Умножение сводится к сложению через соотношение $x\cdot (y+1)=x\cdot y+x$, т.е. умножение сводится к сложению. Возведение в степень аналогично сводится к умножению.

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 11:53 
Аватара пользователя


12/05/12
604
Оттуда
Цитата:
А что это за вид? Обычно же вид такой: .

Этот вид предложил преподаватель, впоследствии такой же я обнаружил в учебнике "Введение в дискретную математику" Яблонского.

Цитата:
или , где - пустое

Ну тут тоже вроде похоже, только вместо $\varepsilon$ использую 0.

Цитата:
проверка на четность ну очень проста: стираем по две единички, пока это возможно, потом смотрим на результат.

А вот тут можно поподробнее? Не очень понятно, как это конкретно делается. Вообще не понятно, как на этом языке реализовать условие. Предполагаю
$X_{1},1 \to 1RX_{2} ;X_{2},1 \to 0LX_{1}; X_{2},0 \to 0SX_{3}$

A вот умножать- что- то совсем глухо. Не могли бы вы поподробнее объяснить?

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 13:51 
Заслуженный участник


08/04/08
8556
cool.phenon в сообщении #721842 писал(а):
Цитата:
А что это за вид? Обычно же вид такой: $a_iq_j\toa_kq_rT, T\in\{L,R,S\}$.
Этот вид предложил преподаватель, впоследствии такой же я обнаружил в учебнике "Введение в дискретную математику" Яблонского.
Так, я домыслю: $A=\{0;1\}$, $X_j$ - состояния МТ, $L,R,S$ - шаги.

cool.phenon в сообщении #721842 писал(а):
А вот тут можно поподробнее? Не очень понятно, как это конкретно делается. Вообще не понятно, как на этом языке реализовать условие. Предполагаю
$X_{1},1 \to 1RX_{2} ;X_{2},1 \to 0LX_{1}; X_{2},0 \to 0SX_{3}$
А из $X_3$ никуда не уходим? Или $X_3$ - конечное состояние? (обычно пишут $q_0$).
Воспроизвел работу программы, это больше похоже на вычисление $x\div 1$ (здесь $\div$ - усеченная разность).
Вам надо такую рекурсию воспроизвести: если на входе $0$ или $1$, то $0$ следует интепретировать как четность входа, а $1$ - как нечетность (если задана другая схема кодирования выхода - перекодировать после вычисления). А если на входе $x>1$, то нужно вычислить $x-2$ - просто стереть две единички. (можно проще описать, но полностью решать за Вас не могу).
Еще играют роль технические вещи: у Вас лента потенциально неограниченна в одну сторону или в две? Если в одну, то как определить начало левого края входа? Если он слева ноликом не обрамлен - придется это сначала сделать.
Попытайтесь, это несложно.

cool.phenon в сообщении #721842 писал(а):
A вот умножать- что- то совсем глухо. Не могли бы вы поподробнее объяснить?
Рекурсия такая:
$f(x,0)=0$
$f(x,y)=f(x,y-1)+x$,
т.е. пока $y$ ненулевое, выполнять сложение (сначала нужно написать МТ для сложения, а затем ее юзать как подпрограмму в искомой МТ). Вы МТ для сложения можете написать?

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 14:20 
Заслуженный участник


09/09/10
3729

(Оффтоп)

Sonic86 в сообщении #721900 писал(а):
Если в одну, то как определить начало левого края входа?

На нем стоит неперезаписываемый черный треугольник $\blacktriangle$. МТ можно вводить очень по-разному, но различия, в целом, технические. Например, можно условиться, что если $A$ — алфавит, то в ячейках стоят символы из $A\cup\{\wedge\}$, где $\wedge$ символизирует пустую ячейку ($\wedge\notin A$, но опять же, это технические детали).

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 14:22 
Аватара пользователя


12/05/12
604
Оттуда
Цитата:
Так, я домыслю: , - состояния МТ, - шаги.

Да, так и есть.

Лента бесконечная в обе стороны, здесь считается, что считывающая головка стоит в начале (на первой единице), то есть, искать начало не нужно, что уже хорошо.

Цитата:
Попытайтесь, это несложно

Вот, попробовал нечто другое.
$1,X_{1}\to 1RX_{2}; 0,X_{2}\to 0SX_{1}; 1,X_{2} \to 1RX_{3}; 1,X_{3}\to 1LX_{4}; 1,X_{4} \to 0X_{5}; 1,X_{5}\to 0LX_{6}; 0,X_{6}\to 0RX_{6}; 1,X_{6}\to 1RX_{1} $

Сложение на 1 бесконечной ленте я знаю, 2 группы единичек разделены нулём, нуль заменяем на 1, идём в самый конец и убираем 1 единицу.

Но вот тут у меня проблема, допустим, сложил один раз, но дальше мне уже нужно знать, сколько именно единиц слева или справа нужно приписать, а этого в машине Тьюринга никак не напишешь. Что здесь можно сделать?

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


06/10/08
6422
cool.phenon в сообщении #721920 писал(а):
Что здесь можно сделать?
Сначала разберитесь, как скопировать число, то есть из строки $1^n$ получить $1^n01^n$

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


06/04/10
3152
А не элегантнее ли воспользоваться китайским методом умножения? :wink:

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 15:35 
Аватара пользователя


12/05/12
604
Оттуда
Xaositect
Кажется, я догадываюсь, как это нужно сделать. Идем вправо по циклу, на каждом шаге возвращаемся в самый конец, дописываем единицу и идём дальше. Но как дописать в нужном месте нуль?
nikvic
Расскажите, пожалуйста, в чём заключается этот метод?

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 16:04 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Один из множителей последовательно делится на два с остатком, второе - удваивается. Из последовательности остатков и удвоений сложением формируется произведение.
Для теории алгоритмов это несущественно.

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 17:23 
Заслуженный участник


08/04/08
8556

(сущий оффтоп)

cool.phenon в сообщении #721920 писал(а):
$1,X_{1}\to 1RX_{2}$
А зачем писать запятые?

Joker_vD в сообщении #721919 писал(а):
На нем стоит неперезаписываемый черный треугольник $\blacktriangle$.
:shock: чОрный треугольник был заложен в основание ленты в глубокой древности. ЧОООрный треугольник повергает головку МТ в дикий темный древний ужас и она отказывается ходить влево! Выполнить переход головки влево может сделать лишь Чак Норрис. Или Сталин.


cool.phenon в сообщении #721920 писал(а):
Вот, попробовал нечто другое.
$1,X_{1}\to 1RX_{2}; 0,X_{2}\to 0SX_{1}; 1,X_{2} \to 1RX_{3}; 1,X_{3}\to 1LX_{4}; 1,X_{4} \to 0X_{5}; 1,X_{5}\to 0LX_{6}; 0,X_{6}\to 0RX_{6}; 1,X_{6}\to 1RX_{1} $
Не очень понятно, что Вы хотели.
Вообще, ясно, что либо для каждой комбинации $aX_j$ должна быть задана инструкция, либо, если есть команда $aX_i\to bX_j$, то среди инструкций должна быть и команда $bX_j\to ...$ (т.е. у графа комбинаций должны из каждой вершины выходить стрелки). У Вас вот есть команда $1,X_{4} \to 0X_{5}$, а для комбинации $0X_5$ команды нет.
И еще нет команды с заключительным состоянием $X_0$ - машина не остановится.

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 17:46 
Заслуженный участник
Аватара пользователя


06/04/10
3152

(Оффтоп)

Sonic86 в сообщении #721975 писал(а):
Вообще, ясно, что либо для каждой комбинации должна быть задана инструкция

Нужно их заставлять ещё писать симулятор на Паскале :wink:

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 18:14 
Аватара пользователя


12/05/12
604
Оттуда
Вначале стрелка стоит в начале строки единиц, поэтому начинаем и двигаем вправо.
$1X_{1}\to 1RX_{2}$.
Далее проверяем следующую единицу. Если там её нет, можно оставаться на месте, можно идти вправо - без разницы. То есть, число нечётное. Если единица - идём вправо. $0X_{2}\to 0SX_{1}$
$1X_{2}\to 1RX_{3}$.
Теперь вытираем 2 нуля.
$1X_{3}\to  1LX_{4}$.
$1X_{4}\to 0LX_{5}$.
$1X_{5}\to 0LX_{6}$.
В состоянии X_{6} двигаемся вправо до первой единицы.
$0X_{6}\to 0RX_{6}$
Если единица встретилась, начинаем всё по новой, переходим в состояние 1.
$1X_{6}\to 1RX_{1}$

(Оффтоп)

nikvic
Не судите прям так сразу, я работаю с этими машинами 3 раз за всё моё существование. После 1 лекции и 1 практики. Эта тема полностью предоставлена на самостоятельное изучение. Поэтому прошу понимания.

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 18:17 
Заслуженный участник


27/04/09
28128

(О структурном подходе.)

Не может быть удобнее сначала нарисовать отображение из частично рекурсивных функций в машины Тьюринга?

 Профиль  
                  
 
 Re: Машины Тьюринга
Сообщение10.05.2013, 18:27 
Аватара пользователя


12/05/12
604
Оттуда

(Оффтоп)

arseniiv
Это вы имеете в виду что-то вроде $*A_{5}A_{1}pA_{2}A_{4}pA_{10}w$?

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

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



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

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


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

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