Контрольная работа на тему Моделирование машины Тьюринга

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

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

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

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

Выполнил:

студент группы АСУ-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, но с учетом переноса. Программа останавливается, когда одно из состояний, преобразую частичную сумму, после младшего разряда находит символ =.


Алгоритм решения

Код программы

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


Вывод

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

Похожие рефераты:

Курсовая работа на тему Мой компьютер Дипломная работа на тему Моніторинг інформаційних потреб споживачів як необхідна умова організації інформаційного обслуговування Реферат на тему Надежность программного обеспечения Курсовая работа на тему Настольные системы управления базами данных (СУБД) Курсовая работа на тему Научно-методическая деятельность преподавателей Курсовая работа на тему Необходимость проведения маркетинговых исследований в сфере образования Курсовая работа на тему Облік зареєстрованих автомобілів в ДАІ Курсовая работа на тему Обработка динамических структур Учебное пособие: Объектно-ориентированная среда программирования "Object Pascal" в профильном курсе информатики Учебное пособие: Операционные системы "тонких" клиентов Курсовая работа на тему Операційна система Linux Контрольная работа на тему Основные возможности Microsoft Оffice Outlook Курсовая работа на тему Основы криптологии Отчет по практике: Основы программирования в среде Delphi Контрольная работа на тему Отчеты Microsoft Office Access Курсовая работа на тему Оформление служебных документов Реферат на тему Плоттеры нового поколения Курсовая работа на тему Построение компоненты в Builder C++ Курсовая работа на тему Потоковое видео и открытые системы Курсовая работа на тему Предметная область "тестирование" Реферат на тему Применение компьютерных технологий при проектировании нефтеперерабатывающего завода Контрольная работа на тему Проведение АВС анализа в среде MS EXCEL Курсовая работа на тему Проектування каталогу мобільних телефонів у Access Курсовая работа на тему Проектування офісу САПР-одяг Курсовая работа на тему Разработка автоматизированной системы управления "Трехмерная печать" Контрольная работа на тему Разработка информационной системы "Производство продукции/услуг" Курсовая работа на тему Разработка мультимедийного сайта Курсовая работа на тему Разработка приложения средствами VBA Курсовая работа на тему Разработка программного обеспечения виртуальной библиотеки Курсовая работа на тему Разработка программы сжатия и восстановления файлов с помощью фиксированного блочного кода постоянного смещения Курсовая работа на тему Разработка специализированного процессора для исполнения элементарных функций Курсовая работа на тему Разработка устройства "Светодиодный пробник p-n переходов" Курсовая работа на тему Решение проблемы топологии и установки устройств физического уровня Курсовая работа на тему Решение транспортной задачи Лабораторная работа на тему Решение уравнений, неравенств и их систем Курсовая работа на тему Розвиток сучасних структур програмного забезпечення Реферат на тему Середовище навчання Moodle. Його переваги та недоліки Курсовая работа на тему Система баз данных MS SQL Server 2000 Реферат на тему Система непрерывной подачи чернил Курсовая работа на тему Система съема данных с оптопар Доклад: Сканеры и принтеры, сфера их применения Курсовая работа на тему Современные информационные системы управления государством Реферат на тему Современный уровень развития переносной флэш-памяти и USB-брелков Курсовая работа на тему Создание базы данных "Аттестация сотрудников" Контрольная работа на тему Создание презентации Курсовая работа на тему Спортивная программа и организация базы данных Курсовая работа на тему Суперэлементное моделирование пространственной системы "плита грунтовое основание" Курсовая работа на тему Сутність та принципи роботи ЕОМ Курсовая работа на тему Сучасне інтерактивне спілкування Реферат на тему Сучасний стан інформаційної безпеки. Проблеми захисту комп'ютерної інформації Реферат на тему Сучасні антивірусні програми та принцип їх роботи Реферат на тему Сучасні комп'ютерні технології Курсовая работа на тему Сучасні операційні системи, архітектура, відмінні характеристики, функціональність, виробництво і перспективи розвитку Реферат на тему Сучасні програмні продукти для управління маркетинговою діяльністю Контрольная работа на тему Сучасні системи автоматизованого проектування графічних проектів Реферат на тему Сущность алгоритмов Контрольная работа на тему Сущность защиты информации Реферат на тему Сущность искусственного интеллекта Курсовая работа на тему Схема електрична принципова модуля на базі 8-розрядного мікропроцесора Контрольная работа на тему Схема контроллера Реферат на тему Схема радиомодема Реферат на тему Схемы шифрования AES, RC4, RC5, RC6, Twofish, Mars Курсовая работа на тему Счетчик обратного отсчета Курсовая работа на тему Технологии компьютерных игр Реферат на тему Функции и возможности текстового редактора Дипломная работа на тему Функціонування системи інформаційного обслуговування користувачів бібліотек у сучасних умовах Реферат на тему Характеристика качества ПО "практичность" Курсовая работа на тему Цвет и графика на ЭВМ Реферат на тему Что такое компьютерная сеть. Виды сетей Контрольная работа на тему Экономические информационные системы Дипломная работа на тему Электронная почта Курсовая работа на тему Язык программирования высокого уровня С++ Курсовая работа на тему Языки программирования Контрольная работа на тему Установка и настройка программного обеспечения локальной сети Курсовая работа на тему Датчики скорости коррозии как элементы АСУ общей системы мониторинга Курсовая работа на тему Динамическое формирование и преобразование списков и структур Шпаргалка: Дискретная техника Реферат на тему Устройство персонального компьютера Курсовая работа на тему Устройство управления системой измерения веса Контрольная работа на тему Утилиты, буфер обмена, автоформат MS Excel Доклад: Файловая система для операционной системы Windows Лабораторная работа на тему Дослідження файлової структури Курсовая работа на тему Економічні задачі лінійного програмування і методи їх вирішення Курсовая работа на тему Емпіричне дослідження програмного забезпечення Курсовая работа на тему Автоматизация системы управления холодильной установкой Курсовая работа на тему Автоматизированная система управления климатом в тепличных хозяйствах Реферат на тему Автомобильная электроника Курсовая работа на тему Анализ доходов отдела фирмы, занимающейся розничной торговлей офисной мебелью Курсовая работа на тему База данных "Магазин по продаже дисков" Курсовая работа на тему Безпровідна мережа Wi-Fi, її будування Контрольная работа на тему Компьютерная графика Реферат на тему Компьютерная графика Контрольная работа на тему Компьютерная графика Реферат на тему Компьютерная графика и решаемые ею задачи Курсовая работа на тему Компьютерная лингвистика Дипломная работа на тему Компьютерная модель СГ в координатах d, q, 0 в режиме ХХ Курсовая работа на тему Назначение и возможности 3d's МАХ 9.0 Реферат на тему Назначение и основные функции электронных таблиц Лабораторная работа на тему Настройка ОС Windows Контрольная работа на тему Методы информационных технологий в делопроизводстве