Читать контрольная по информатике, вычислительной технике, телекоммуникациям: "Моделирование машины Тьюринга" Страница 1

(Назад) (Cкачать работу)

Саратовский государственный технический университет Кафедра «Системотехника» Расчетно-графическая работа по математической логике на тему: «Моделирование машины Тьюринга» Выполнил: студент группы АСУ-21 Мустафин Ш. Р. Проверил: преподаватель Минаев С.В. Саратов 2010 Цель Изучение принципов работы машины Тьюринга, приобретение практических навыков программирования машины Тьюринга. Задание Изучить правила написания алгоритмов на эмуляторе машины Тьюринга; Получить у преподавателя вариант задания для реализации алгоритма; Разработать алгоритм в соответствии с полученным заданием; Отладить написанный алгоритм на эмуляторе машины Тьюринга. Задача Сложение нескольких чисел в двоичной системе. Описание метода решения Для более удобной реализации алгоритма на эмуляторе, сложение будет выполняться поэтапно. Сначала будем складывать два первых слагаемых, затем результат этого сложения с третьим и так далее, пока не дойдем до знака «=». Первым шагом ищется самый младший, неиспользованный разряд первого слагаемого. В зависимости от его значения переходим в следующие соответствующие состояния. Далее ищем самый младший, неиспользованный разряд второго слагаемого и записываем на его место результат сложения этих двух разрядов. Затем снова возвращаемся на первый шаг. Этот цикл осуществляется до тех пор, пока у одного из слагаемых не кончатся разряды. Записываем оставшиеся старшие разряды к результату, с учетом переноса, если он есть. Стираем лишние символы, находящиеся до старших разрядов результата. Проверяем какой знак стоит после результата. Если «+», то возвращаемся к первому шагу, если «=», то конец подсчетам. Описание программы Для удобства в программе все 1 и 0 заменяются на I и O соотвественно. Далее состояние q5 доходит до + и переходит в состояние q6, в зависимости от того, какой символ стоит перед + q6 переходит в q16 – i, q15 – o. q16, q7, q9 – это состояния которые несут единицу во второе слагаемое без переноса, и в зависимости от значения, записывают в самый младший, неиспользованный разряд результат сложения. Если переноса нет, то переходим в состояние q11, есть – q10. Q11,q13 – бегут к первому слагаемому и анализируют самый младший, неиспользованный разряд и в зависимости от значения переходят в состояния q16 и q15, если разрядов нету, то в q14. Q14 и q17 затирают ненужные символы и переходят в состояние q6. Q15, q37,q39 - это состояния которые несут ноль во второе слагаемое без переноса, и в зависимости от значения, записывают в самый младший, неиспользованный разряд результат сложения и переходят в состояние q11. Q10,q23 – бегут с переносом к первому слагаемому и анализируют самый младший, неиспользованный разряд и в зависимости от значения переходят в состояния q16 и q26, если разрядов нету, то в q24. Q26 аналог q15, только несет значение 0 с переносом. Q24 аналог q14, но с учетом переноса. Программа останавливается, когда одно из состояний, преобразую частичную сумму, после младшего разряда находит символ «=». Алгоритм решения Код программы [MoT Data] 1110111+111111+10101010101010101010+…++11= q1s q1s dR q1s1q1sidR q1s0q1sodR q1s+q1s+dR q1s=q2s=dL q2siq2sidL q2soq2sodL q2s+q2s+dL q2s q5s dR q5s q5s dR q5siq5sidR q5soq5sodR q5s+q6s+dL q5s=q100s=dE q6siq16s*dR (если цифра первого слагаемого 1 без переноса) q6soq15s*dR ( если цифра первого

Похожие работы