Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Нужна помощь,Cрочно! Задание по теории алгоритмов

Pablo Котовщиков Ученик (97), открыт 3 недели назад
Построить машины Тьюринга для правильного вычисления функций (в скобках
указана система счисления):f(x)=4x+4, (10); не первый день решаю эту задачу, с правилами использования ознакомлен, работал на эмуляторе.
3 ответа
V̲i̲s̲t̲a̲s̲t̲e̲r̲ Искусственный Интеллект (264355) 3 недели назад
ой мля. тут побитово над решать.. никто не поможет
AaacoB Aaac Мудрец (14208) 3 недели назад
мало инфы... что ты еще делал "не первый день"? что кушал, как какал?
Андрей Высший разум (461434) 3 недели назад
Изначально стоим над самой правой цифрой числа
_ - обозначение пустой ячейки
 увеличиваем x на 1: 4x + 4 = 4(x + 1)

q1,0 -> q2,1,L
...
q1,9 -> q1,0,L
q1,_ -> q2,1,L

ставим # слева от x: это разделитель f(x) и x

q2,0 -> q2,0,L
...
q2,9 -> q2,9,L
q2,_ -> q3,#,R

движемся к правой цифре x

q3,# -> q3,#,R
q3,0 -> q3,0,R
...
q3,9 -> q3,9,R
q3,_ -> q4,_,L

отнимаем 1 от x

q4,# -> q8,_,R
q4,0 -> q4,9,L
q4,1 -> q5,0,L
...
q4,9 -> q5,8,L

движемся к правой цифре f(x)

q5,# -> q6,#,L
q5,0 -> q5,0,L
...
q5,9 -> q5,9,L

прибавляем 4 к f(x)

q6,0 -> q3,4,R
...
q6,5 -> q3,9,R
q6,6 -> q7,0,L
q6,7 -> q7,1,L
q6,8 -> q7,2,L
q6,9 -> q7,3,L
q6,_ -> q3,4,R

перенос 1 в следующий разряд f(x)

q7,0 -> q3,1,R
...
q7,8 -> q3,9,R
q7,9 -> q7,0,L
q7,_ -> q3,1,R

f(x) вычислено - стираем 9...9, оставшиеся от x

q8,9 -> q8,_,R
q8,_ -> стоп
Pablo КотовщиковУченик (97) 3 недели назад
Большое спасибо!
Похожие вопросы