Моделирование машины Тьюринга

Саратовский государственный технический университет

Кафедра “Системотехника”

Расчетно-графическая работа

По математической логике

На тему: “Моделирование машины Тьюринга”

Выполнил:

Студент группы АСУ-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 ( если цифра первого слагаемого 0 без переноса)

Q16s+q16s+dR

Q16s*q16s*dR

Q16siq7sidR

Q16soq7sodR(проход по звездочкам и + до еденичек или и и о)

Q16s1q40s1dL

Q16s0q40s0dL

Q40s+q12s1dL(q12 когда разряды кончились во втором слагаемом)

Q7siq7sidR

Q7soq7sodR

Q7s+q9s+dL(q7 и q9 – несу 1 без переноса )

Q7s1q9s1dL

Q7s0q9s0dL

Q7s=q9s=dL

Q9siq10s0dL (q10 – c переносом единичкой)

Q9soq11s1dL (q11 без переноса )

Q9s+q12s1dE (q12 когда разряды кончились во втором слагаемом без переноса)

Q11siq11sidL

Q11soq11sodL(бежит назад без переноса )

Q11s+q11s+dL

Q11s*q13s*dL

Q13s*q13s*dL

Q13siq16s*dR

Q13soq15s*dR

Q13s q14s dR( q14 если разряды закончились в первом слагаемом без переноса )

Q14s q14s dR

Q14s*q14s dR (восстановления числа в i и o )

Q14s+q14s dR

Q14siq14sidR

Q14soq14sodR

Q14s1q17s1dE

Q14s0q17s0dE

Q17s1q17sidR

Q17s0q17sodR(вернуться в q6 после воосстановления)

Q17s+q6s+dL

Q17s=q100s=dE

Q12s*q12s*dL(записать число без переноса )

Q12s q21s dR

Q12siq18s*dR

Q12soq19s*dR

Q18s*q18s*dR(нести единицу к цифрам через + и *)

Q18s+q18s+dR

Q18s1q20s1dL

Q18s0q20s0dL

Q20s+q12s1dL

Q20s*q12s1dL

Q19s*q19s*dR

Q19s+q19s+dR (нести 0)

Q19s1q22s1dL

Q19s0q22s0dL

Q22s+q12s0dL

Q22s*q12s0dL

Q21s q21s dR

Q21s*q21s dR (q21 – шагает вправо стирает * и делает 1 и 0 – i и o до + или =)

Q21siq21sidR

Q21soq21sodR

Q21s1q21sidR

Q21s0q21sodR

Q21s+q6s+dL

Q21s=q100s=dE

Q10siq10sidL (бежит назад с переносом )

Q10soq10sodL

Q10s+q10s+dL

Q10s*q23s*dL

Q23s*q23s*dL (бежит назад c переносом )

Q23siq26s*dR

Q23soq16s*dE

Q23s q24s dR

Q26s+q26s+dR проход по звездочкам и + до еденичек или и и о)

Q26s*q26s*dR

Q26siq25sidR

Q26soq25sodR

Q26s1q43s1dL

Q26s0q43s0dL

Q43s+q27s0dL

Q25siq25sidR (q25 несу с переносом )

Q25soq25sodR

Q25s+q28s+dL

Q25s1q28s1dL

Q25s0q28s0dL

Q25s=q28s=dL

Q28siq10s1dL(q10 – c переносом единичкой)

Q28soq10s0dL

Q28s+q27s0dL

Q24s*q24s dR

Q24s+q24s dR ( q24 если разряды закончились в первом слагаемом с переносом)

Q24siq24sidR

Q24soq24sodR (восстановления числа в i и o )

Q24s1q29s1dL

Q24s0q29s0dL

Q29siq29s0dL

Q29soq30sodE

Q29s q30s dE

Q30soq17s1dE

Q30s q17s1dE

Q27s*q27s*dL (q27? когда разряды кончились во втором слагаемом с переносом)

Q27s q31s dR

Q27siq32s*dR

Q27soq33s*dR

Q32s*q32s*dR(нести единицу к цифрам через + и *)

Q32s+q32s+dR

Q32s1q34s1dL

Q32s0q34s0dL

Q34s+q27s0dL

Q34s*q27s0dL

Q33s*q33s*dR (нести 0)

Q33s+q33s+dR

Q33s1q35s1dL

Q33s0q35s0dL

Q35s+q12s1dL

Q35s*q12s1dL

Q31s*q31s*dR(q31 – шагает вправо стирает * и делает 1 и 0 – i и o до + или = надо дорисовать 1)

Q31s0q36s0dL

Q31s1q36s1dL

Q36s*q21s1dL

Q15s+q15s+dR

Q15s*q15s*dR

Q15siq37sidR

Q15soq37sodR

Q15s1q42s1dL

Q15s0q42s0dL

Q42s+q12s0dL

Q37s*q37s*dR

Q37siq37sidR

Q37soq37sodR

Q37s+q39s+dL

Q37s1q39s1dL

Q37s0q39s0dL

Q37s=q39s=dL

Q39siq11s1dL

Q39soq11s0dL

Q39s+q12s0dL

Q100s=q100s=dL

Q100siq100s1dL

Q100soq100s0dL

Q100s qz

Вывод

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


Моделирование машины Тьюринга