Машина Тьюринга(умножение)

[MestnyBomzh]

Добрый вечер! Подскажите пожалуйста, как сделать умножение числа на три, или вообще на произвольное число... Без копирования здесь не обойтись же?

[nikvic]

В каком виде вход/выход?

[Lukum]

Без копирования не обойтись.

[MestnyBomzh]

nikvic
n*m, унарная система

-- 12.02.2014, 21:31 --

я так понимаю, мы должны сделать такое число: $n*m*m$, вычитать из $n$ единицу и прибавлять к $m$ себя же

[Lukum]

$ M(a,0)=0 $
$ M(a,b)=M(a,b-1)+a $

[mihailm]

(Оффтоп)

MestnyBomzh в сообщении #825669 писал(а):

Добрый вечер! Подскажите пожалуйста, как сделать умножение числа на три...

Я ее помню! (так как это первая и единственная моя прога на машине Тьюринга)
Попалась как это ни смешно на экзамене, программа заняла то ли две то ли три страницы (помог, кстати опыт программирования на МК-61).

[Lukum]

(Оффтоп)

думаю строк в 20-30 должно влезть

[nikvic]

Lukum в сообщении #825690 писал(а):

$ M(a,0)=0 $
$ M(a,b)=M(a,b-1)+a $

Насколько понимаю, нужно умножать на константу.
0/ Бежать направо, выставить звёздочку.
1/ Бежать налево, стереть палочку. Если нет - к звезде, стереть, закончить.
2/ Бежать направо, с пустого места выставить 3 палочки.
3/ Бежать до звезды, перейти к 1/.

[MestnyBomzh]

Вот, для умножения двух произвольных чисел сделал, может кому-нибудь потом понадобится:

1q0->Bq1R//звезда в конце
1q1->1q1R
*q1->*q1R
Bq1->*q2L

1q2->1q2L//перемотка в начало второго числа
*q2->*q3R

1q3->0q4R//проверка символа
*q3->*q6L

1q4->1q4R//копирование одного символа
*q4->*q4R
Bq4->1q5L

1q5->1q5L//перемотка назад
*q5->*q5L
0q5->0q3R

0q6->1q6L//восстановление числа
1q6->1q6L
*q6->*q6L
Bq6->Bq7R//переход в начало

1q7->Bq8R
*q7->Bq9R

1q8->1q8R
*q8->*q3R

1q9->Bq9R//стирание лишнего числа
*q9->BSTOPR

-- 13.02.2014, 01:16 --

И для умножения на три:
1q1->1q1R//пробегаем назад и ставим * и три единицы
Bq1->*q2R
Bq2->1q3R
Bq3->1q4R
Bq4->1q5R
Bq5->*q6L

*q6->*q6L//В начало
1q6->1q6L
Bq6->Bq7R

1q7->Bq8R//n=n-1
*q7->Bq13R

1q8->1q8R//перемотка до первой звездочки
*q8->*q9R

1q9->0q10R//Алгоритм копирования стройки за вторую звезду
*q9->*q12L

1q10->1q10R
*q10->*q10R
Bq10->1q11L

1q11->1q11L
*q11->*q11L
0q11->0q9R

0q12->1q12L
*q12->*q12L
1q12->1q12L
Bq12->Bq7R

1q13->Bq13R
*q13->BSTOPR

Я не уверен только в рациональности отведения трех состояний под то, чтобы поставить три единицы в конце....Но как это сделать иначе я не представляю

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

MestnyBomzh
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.