Саратовский
государственный технический университет
Кафедра
«Системотехника»
Расчетно-графическая
работа
по математической
логике
на тему:
«Моделирование машины Тьюринга»
Выполнил:
студент группы АСУ-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
Вывод
Входе выполнения задания были изучены принципы работы
машины Тьюринга, приобретены практические навыки программирования машины Тьюринга.
Другие работы по теме:
Параллельное и последовательное моделирование
Порядок и разновидности соединений звеньев, их характеристика и отличительные черты. Амплитудно-частотные характеристики при различных соединениях, порядок их расчета и анализа. Методика и этапы моделирования последовательного соединения звеньев.
Алан Тьюринг и его машины: новый взгляд на загадку
Логично, что величайший шифровальщик Второй мировой войны остается загадкой и сейчас, когда прошло уже сто лет со дня его рождения. Алан Тьюринг, блестящий, оригинальный математик, который считается отцом информатики.
Клиодинамика
Введение 1 Общие сведения 2 Соотношение между клиодинамикой и клиометрией 3 Основоположники клиодинамики 4 Основные достижения клиодинамики Список литературы
Фейгенбаум, Эдвард Альберт
Введение 1 Биография 2 Награды Список литературы Введение Эдвард Альберт Фейгенбаум (англ. Edward Albert Feigenbaum, 20 января 1936 года, Уихокен, США) — учёный в области теории вычислительных систем, награждён в 1994 году премией Тьюринга за достижения в исследовании искусственного интеллекта, в частности экспертных систем.
Яо, Эндрю
Введение 1 Биография 2 Награды (выдержка) Список литературы Введение Эндрю Яо Цичжи (англ. Andrew Chi-Chih Yao, кит. 姚期智, пиньинь Yбo Qīzhм, 24 декабря 1946 года, Шанхай, Китай) — учёный в области теории вычислительных систем, профессор университета Цинхуа в Пекине. Награждён в 1996 году премией Кнута.
Текер, Чарльз
Введение 1 Биография 2 Премии и награды Список литературы Введение Чарльз Текер (Charles P. Thacker, 26 февраля 1943 года, Пасадина (Калифорния)) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга 2009 года.
Лисков, Барбара
Введение 1 Биография 2 Награды 3 Библиография Список литературы Введение Барбара Лисков (англ. Barbara Liskov, род. Барбара Джейн Хьюберман — Barbara Jane Huberman; род. 7 ноября 1939) — учёная в области теории вычислительных систем, лауреат премии Тьюринга 2008 года.
Грей, Джим
Введение 1 Биография 1.1 Исчезновение 2 Книги 3 Награды Список литературы Введение Джеймс Николас «Джим» Грей (англ. James Nicholas "Jim" Gray, 1944, Сан-Франциско) — учёный в области теории вычислительных систем. Награждён в 1998 году премией Тьюринга за вклад в развитие баз данных.
Эмерсон, Эрнест Аллен
Введение 1 Биография 2 Награды Список литературы Введение Эрнест Аллен Эмерсон (англ. Ernest Allen Emerson, Даллас, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга. В настоящее время является профессором информатики в университете Техаса.
Аллен, Фрэнсис Элизабет
План Введение 1 Биография 2 Награды Список литературы Введение Фрэнсис Элизабет Аллен (англ. Frances Elizabeth Allen, 1932 года, Нью-Йорк, США) — американский учёный в области теории вычислительных систем. Первая женщина, награждённая премией Тьюринга.[1]
Стернс, Ричард Эдвин
План Введение 1 Биография 2 Награды Список литературы Введение Ричард Эдвин Стернс (англ. Richard Edwin Stearns, 5 июля 1936 года, Колдуэлл (Нью-Джерси), США) — учёный в области теории вычислительных систем, награждён в 1993 году премией Тьюринга за достижения в исследовании теории сложности вычислений.
Кларк, Эдмунд Мельсон
План Введение 1 Биография 2 Книги 3 Награды Список литературы Введение Эдмунд Мельсон Кларк младший (англ. Edmund Melson Clarke, Jr., 27 июля 1945 года, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга. В настоящее время является профессором информатики в университете Карнеги — Меллон.
Блюм, Мануэль
План Введение 1 Биография 2 Награды Список литературы Введение Мануэль Блюм (исп. Manuel Blum; 26 апреля 1938 года, Каракас, Венесуэла) — учёный в области теории вычислительных систем, профессор по информатике в университете Карнеги — Меллон. Награждён в 1995 году премией Тьюринга за достижения в исследовании основ теории сложности вычислений и их применении в криптографии и верификации программ.
Скотт, Дана Стюарт
Да́на Стю́арт Скотт (англ. Dana Stewart Scott , р. 1932) — американский учёный в области математики и информатики. Исследования Скотта связанны с теорией моделей, теорией автоматов, модальной и интуиционистской логиками, конструктивной математикой и связью между логикой и теорией категорий.
Маккарти, Джон
Джон Маккарти (4 сентября 1927, Бостон) — выдающийся американский информатик, автор термина «искусственный интеллект» (1955), изобретатель языка Лисп (1958), основоположник функционального программирования, лауреат Премии Тьюринга (1971) за огромный вклад в область исследований искусственного интеллекта.
Формализация понятия "алгоритм"
Более строгое описание алгоритма, чем общее или формализация понятия алгоритма. Три подхода к формализации: теория конечных и бесконечных автоматов, теория вычислимых (рекурсивных) функций и л-исчисление Черча. Воображаемые машины Поста и Тьюринга.
Машина Тьюринга
Простое вычислительное устройство машина Тьюринга и ее алгоритмические свойства. Тезис Черча–Тьюринга и моделирование машины Тьюринга (операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке с учетом изменения состояния машины).
Проблемы создания искусственного интеллекта
Многие годы продолжается дискуссия: могут ли машины думать? Много разных мнений. Задавая вопрос "возможно ли искусственное разумное существо?" выдающийся советский учёный академик А. Н. Колмогоров отвечает: "...в рамках материалистического мировоззрения не существует никаких состоятельных принципиальных аргументов против положительного ответа на этот вопрос."
Формализация понятия алгоритма
Для глубокого, строгого изучения свойств алгоритма и его организации необходима формализация, хотя бы для того, чтобы иметь возможность делать доказательные утверждения о свойствах алгоритма.
Имитационное моделирование станции технического обслуживания
Построение имитационной модели станции технического обслуживания, на основе системы Micro Saint. Определение комплекса работ модели, основных параметров для них, связей между работами. Оценка распределения числа полицейских машин, находящихся в ремонте.
Классы вычислительных машин
Здесь выделяют аналоговые (непрерывного действия); цифровые (дискретного действия); гибридные (на отдельных этапах обработки используются различные способы физического представления данных).
Бэббидж Чарльз
В начале 19 века Чарльз Бэббидж сформулировал основные положения, которые должны лежать в основе конструкции вычислительной машины принципиально нового типа.
Тьюринг (Turing) Алан Матисон
Тьюринг (Turing) Алан Матисон (1912 — 54) — гениально одаренный английский математик. В возрасте 24 лет написал работу "О вычислимых числах", которой суждено было сыграть исключительно важную роль в развитии вычислительной математики.
Отец информатики и первый «хакер» Алан Тьюринг
В 1935 году, будучи студентом Кембриджского королевского колледжа, Алан Тьюринг начинает вплотную заниматься созданием «мыслящей машины» – теоретического прообраза современного компьютера.