Программа для сложения чисел на машине Тьюринга

[Anna87]

Здравствуйте. Задача такая:
составить функциональныю схему для машины тьюринга, с помощью которой на ленте будет записано следующее: число+число=результат. Например: $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
А вот если другое число, то никак не удаётся написать.

[Legioner93]

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

[Anna87]

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

[Anna87]

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

[Legioner93]

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

[Sender]

Anna87 в сообщении #634120 писал(а):

Как прибавить 1, я поняла

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

[Pavia]

Цитата:

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

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

Цитата:

Как прибавить 1, я поняла:

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

Цитата:

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

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

[Sender]

Pavia в сообщении #635547 писал(а):

Ничего у неё не получается

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

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

[Anna87]

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

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

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

[Anna87]

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

[Legioner93]

Не затруднит Примите мои извинения, редко проверяю форум.
- Программу я не писал, за работоспособность не ручаюсь.
- Опечатки, в том числе и критические, не исключены , хотя я вроде проверил.
- Формальную реализацию на языке МТ я пока оставлю вам. Алгоритм опишу на словам (немного кода будет в первом пункте).
- У вас этот момент не освещён: будем считать, что на вход подается строка вида "$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$ за одно, а не за сто ). Если этот монстр вам подойдёт (в чём я сомневаюсь), то отвечу на любые вопросы, связанные с написанием кодов по моему словесному описанию.

[Legioner93]

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

[Sender]

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

[Anna87]

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

-- 01.11.2012, 09:19 --

Sender в сообщении #638609 писал(а):

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

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

[Legioner93]

Sender в сообщении #638609 писал(а):

но они отсутствуют в алфавите МТ явно заданном в условии.

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