2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Программа для сложения чисел на машине Тьюринга
Сообщение22.10.2012, 14:39 


22/10/12
7
Здравствуйте. Задача такая:
составить функциональныю схему для машины тьюринга, с помощью которой на ленте будет записано следующее: число+число=результат. Например: $123+99=222$. Алфавит, используемый в машине: пробел (обозначается а0), $+,=$ 0,1,2,3,4,5,6,7,8,9. Количество внутренних состояний не ограничено.
Как прибавить 1, я поняла:
a q1 q2
0 0Пq1 1Cq2
1 1Пq1 2Cq2
2 2Пq1 3Cq2
3 3Пq1 4Cq2
4 4Пq1 5Cq2
5 5Пq1 6Cq2
6 6Пq1 7Cq2
7 7Пq1 8Cq2
8 8Пq1 9Cq2
9 9Пq1 0Cq2
- -Лq1 1Cq2
А вот если другое число, то никак не удаётся написать.

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


28/07/09
1178
А двоичные числа можете сложить? Задача ровно та же самая, а вот мороки явно меньше будет.

 Профиль  
                  
 
 Re: Программа для сложения чисел на машине Тьюринга
Сообщение23.10.2012, 00:30 


22/10/12
7
В том то и дело, что нет. По заданию надо работать именно с десятичными числами в традиционном представлении. С двоичными действительно проблем меньше. Но не так-то всё просто :(

 Профиль  
                  
 
 Re: Программа для сложения чисел на машине Тьюринга
Сообщение24.10.2012, 20:24 


22/10/12
7
Помогите, пожалуйста! Неужели ни у кого нет мыслей как это сделать?

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


28/07/09
1178
Я тут набросал решение, но есть одно "но". Программа состоит из 4 подпрограмм, каждую из которых выполняет отдельная машина Тьюринга. То есть у меня есть 4 "маленькие" МТ, которые работают последовательно и передают друг другу ленту после окончания. Первая переворачивает второе число задом наперед, вторая добавляет недостающие нули меньшему из чисел, третья складывает числа "начиная с центра", при этом не перенося разрядов (то есть 2+2=4, 4+5=9, 5+6=B, 9+9=I), четвертая выполняет собственно перенос этих разрядов. Так мне оказалось написать гораздо проще, чем городить всё в одной "большой" машине. Хотя ЕМНИП объединение последовательных МТ тривиальная задача.
Вам такое решение подойдёт?

 Профиль  
                  
 
 Re: Программа для сложения чисел на машине Тьюринга
Сообщение25.10.2012, 10:08 


14/01/11
2916
Anna87 в сообщении #634120 писал(а):
Как прибавить 1, я поняла


По-моему, у вас получается "9+1=0".

 Профиль  
                  
 
 Re: Программа для сложения чисел на машине Тьюринга
Сообщение25.10.2012, 12:18 
Аватара пользователя


31/10/08
1244
Цитата:
Здравствуйте. Задача такая:
составить функциональныю схему для машины тьюринга, с помощью которой на ленте будет записано следующее: число+число=результат.

Задача сформулированна неправильна, вернее недоконца. Так как не указанно что подается на вход.
Цитата:
Как прибавить 1, я поняла:

А вот и неправильно. Ваша табличка не соотвествует алфавиту.
Откуда взялся "-" ? Куда пропали "a0", "+", "=" ?

Цитата:
По-моему, у вас получается "9+1=0".

Ничего у неё не получается машина дойя до знака "-" зациклится переходя влево на один пунтк заетм в право. Это легко проверить так как из q1 отсутсвует перехода в q2.

 Профиль  
                  
 
 Re: Программа для сложения чисел на машине Тьюринга
Сообщение25.10.2012, 13:23 


14/01/11
2916
Pavia в сообщении #635547 писал(а):
Ничего у неё не получается


Если только она не стартует из состояния q2. :-)

Кстати, если есть алгоритм уменьшения и увеличения на 1, можно было бы где-нибудь рядом записать два исходных слагаемых и уменьшать одно из них на 1, пока оно не станет нулём, а второе увеличивать.

 Профиль  
                  
 
 Re: Программа для сложения чисел на машине Тьюринга
Сообщение25.10.2012, 20:52 


22/10/12
7
Sender, у меня тоже была такая мысль. Но как-то не получилось реализовать. Очень громоздко.

Legioner93, если можно, поделитесь пожалуйста. Я посмотрю. Может подойдёт. Объединить знаю как. Но если уж очень громодзко получится, то не буду.

Pavia, возможно опечаталась, когда с бумажки переписывала, извините.

 Профиль  
                  
 
 Re: Программа для сложения чисел на машине Тьюринга
Сообщение29.10.2012, 11:15 


22/10/12
7
Legioner93, напишите программу, пожалуйста, если Вас не затруднит

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


28/07/09
1178
Не затруднит :D Примите мои извинения, редко проверяю форум.
- Программу я не писал, за работоспособность не ручаюсь.
- Опечатки, в том числе и критические, не исключены :facepalm: , хотя я вроде проверил.
- Формальную реализацию на языке МТ я пока оставлю вам. Алгоритм опишу на словам (немного кода будет в первом пункте).
- У вас этот момент не освещён: будем считать, что на вход подается строка вида "$a+b$", например "$27563+823$"
МТ1 - переворачивает второе число задом наперёд.
Идём вправо по левому числу до плюса, состояние $q$. Как только натыкаемся на плюс, меняем состояние на $\tilde{q}$ и начинаем работу. Передвигаемся вправо, считываем первую цифру $n$. Запоминаем её, помечаем штрихом, двигаемся вправо. 10 правил вида $\tilde{q}n - q_n n' R$. Идём до $\lambda$ или штрихованной цифры, меняем состояние на $\tilde{q_n}$, передвигаемся влево. Если там стоит уже штрихованная цифра, значит работа закончена. Если нештрихованная, то ставим вместо неё цифру $n'$, которую мы заботливо несли всё это время. А эту цифру $k$, вместо которой мы поставили $n'$ запоминаем в $\hat{q_k}$. То есть правила вида $\tilde{q_n}k - \hat{q_k}n' L$. Дальше идём влево и действуем полностью аналогичным образом. Завершение работы, как я уже говорил, когда не останется нештрихованных цифр. Можно сразу закончить, а можно пройтись по всей строке от лямбды до лямбды, удаляя эти некрасивые штрихи.
МТ2 - добавляет недостающее число нулей к меньшему из чисел.
Тут та же самая идея со штрихами, я не буду подробно расписывать. Идея примерно такая. Начинаем с центра (с плюса), идём влево, штрихуем первую нештрихованную цифру, идём вправо, делаем аналогичную операцию. Если справа не нашлось "свободной" цифры, значит ставим 0 (штрихованный, чтобы не перепутать), и снова идем влево. Если же слева не оказалось "свободной цифры", то идём вправо и ищем свободные цифры. Если их там нет, то завершаем работу. Если они там есть, то идём влево до лямбды, ставим нуль, после чего всё повторяем. Примерно так. И в самом конце тоже нужно удалить штрихи.
МТ3 - сложение без переноса разрядов.
Тут нам и пригодится то, что числа развернуты друг к другу. Чем ближе к плюсу с обеих сторон - тем меньше разряд. Расстояние до плюса собственно и равно разряду. Как складываем? Проще простого. Идём вправо от плюса, запоминаем цифру и удаляем её, идём влево, складываем её с первой же попавшейся цифрой, её тоже удаляем, ставим на её месте результат. Повторяем, пока не останется цифр (не забываем штриховать "результатные" цифры, чтобы не перепутать с ещё не сложенными). Не забываем, что сложение у нас без переноса разрядов, то есть $6+6=B$, $9+9=I$ (как в шестнадцатеричной СС, только ещё с 3 буквами).
В итоге мы получим ответ в уже правильном порядке цифр (так как пошли сначала именно вправо), но с дырками между ними. Можно их удалить, но это не принципиально (не помешает работе четвёртой МТ). А вот штрихи, как обычно, удалить нужно.
МТ4 - нормализация.
А теперь будем переносить разряды. Выполняем в один проход справа налево (в отличие от чехарды в предыдущих трёх пунктах). Если цифра больше 9, то отнимаем от неё десятку (то есть вместо $G$ ставим $6$), 10 в уме, переходим на разряд влево, прибавляем. Повторяем операцию. Ничего сложного. Тут нам понадобится ещё цифра $J=19$, которая, например, понадобится при нормализации результата сложения $9999+9999$.

Вот собственно и всё. Правил получается не так уж и много на самом деле (особенно если считать правила $\tilde{q_n}k - \hat{q_k}n' L$ за одно, а не за сто 8-) ). Если этот монстр вам подойдёт (в чём я сомневаюсь), то отвечу на любые вопросы, связанные с написанием кодов по моему словесному описанию.

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


28/07/09
1178
Впрочем, первую задачу можно решить проще. Просто берём и перекидываем цифры вправо, начиная с последней цифры второго числа, а не тасуем симметрично стоящие. Правда тогда между вторым числом и плюсом образуется дырка, равная по размеру длине этого числа минус один. Но во-первых она не мешает дальнейшей работе, а во-вторых дырки всё равно появятся в четвёртом пункте.

 Профиль  
                  
 
 Re: Программа для сложения чисел на машине Тьюринга
Сообщение01.11.2012, 08:01 


14/01/11
2916
Все эти дополнительные символы вроде цифр, больших 9, или штрихованных цифр здорово облегчают жизнь, но они отсутствуют в алфавите МТ явно заданном в условии.

 Профиль  
                  
 
 Re: Программа для сложения чисел на машине Тьюринга
Сообщение01.11.2012, 09:16 


22/10/12
7
Legioner93, спасибо. попробую сделать и проверить что к чему попозже вопросы задам, если возникнут

-- 01.11.2012, 09:19 --

Sender в сообщении #638609 писал(а):
Все эти дополнительные символы вроде цифр, больших 9, или штрихованных цифр здорово облегчают жизнь, но они отсутствуют в алфавите МТ явно заданном в условии.

да. согласна. подумаю как без них сделать.
к тому же эта программа стирает числа. то есть в итоге получится просто ответ. а надо "123+123=246" :(
буду думать

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


28/07/09
1178
Sender в сообщении #638609 писал(а):
но они отсутствуют в алфавите МТ явно заданном в условии.

А слона-то я и не заметил :mrgreen:
Тогда моё решение никуда не годится. Будем думать.

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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