Математическая логика и теория алгоритмов

Математическая логика и теория алгоритмов
Задание:
1) Сделать 3 любые задачи. Задачи находятся в PDF файле.
2) Написать на машине Тьюринга следующие программы:
1. Таймер от 0 до 99 с последующей его остановкой и сбросом на 0.
2. Программа сложения двухзначных чисел
3. Программа, заменяющая входное слово на обратное ему (дано слово, вывести его в обратном порядке)
4. Программа, удаляющая символы А в слове
5. Программа, удаляющая каждый третий символ в слове

Содержание отчета:
1. Задание
2. Код программы
3. Скриншот программы на машине Тьюринга

...

Отсутствует

Отсутствует

Алгоритм.Выходим на последнюю цифру первого числа.Вычитаем единицу из последнего разряда с возможным заемом.Выходим на конец второго числа, Прибавляем единицу в последний разряд с возможным переносом.Когда в обоих позициях первого числа окажутся нули, стираем эти нули, идем направо и останавливаемся на первой непустой клетке.0123456789%Q1Q20RQ21RQ22RQ23RQ24RQ25RQ26RQ27RQ28RQ29RQ2Q40LQ30RQ31RQ32RQ33RQ34RQ35RQ36RQ37RQ38RQ3Q8%RQ4Q5%RQ60RQ61RQ62RQ63RQ64RQ65RQ66RQ67RQ68RQ5Q7%RQ6Q39RQ7Q150HQ151HQ152HQ153HQ154HQ155HQ156HQ157HQ158HQ159HQ7%RQ8Q90RQ91RQ92RQ93RQ94RQ95RQ96RQ97RQ98RQ99RQ8%RQ9Q90RQ91RQ92RQ93RQ94RQ95RQ96RQ97RQ98RQ99RQ10%LQ10Q111LQ112LQ113LQ114LQ115LQ116LQ117LQ118LQ119LQ120LQ11Q110LQ111LQ112LQ113LQ114LQ115LQ116LQ117LQ118LQ119LQ13%LQ12Q111LQ112LQ113LQ114LQ115LQ116LQ117LQ118LQ119LQ140LQ13Q20HQ21HQ22HQ23HQ24HQ25HQ26HQ27HQ28HQ29HQ14Q111LQ15Эмуляция(q15:=STOP,λ:=%,q15:=начальное состояние на %):Текст программы:%q15->%q1R0q1->0q2R1q1->1q2R2q1->2q2R3q1->3q2R4q1->4q2R5q1->5q2R6q1->6q2R7q1->7q2R8q1->8q2R9q1->9q2R0q2->0q4L1q2->0q3R2q2->1q3R3q2->2q3R4q2->3q3R5q2->4q3R6q2->5q3R7q2->6q3R8q2->7q3R9q2->8q3R%q3->%q8R0q4->%q5R1q4->0q6R2q4->1q6R3q4->2q6R4q4->3q6R5q4->4q6R6q4->5q6R7q4->6q6R8q4->7q6R9q4->8q6R0q5->%q7%q7->%q7R0q7->0STOPH1q7->1STOPH2q7->2STOPH3q7->3STOPH4q7->4STOPH5q7->5STOPH6q7->6STOPH7q7->7STOPH8q7->8STOPH9q7->9STOPH0q6->9q3R%q8->%q8R0q8->0q9R1q8->1q9R2q8->2q9R3q8->3q9R4q8->4q9R5q8->5q9R6q8->6q9R7q8->7q9R8q8->8q9R9q8->9q9R%q9->%q10L0q9->0q9R1q9->1q9R2q9->2q9R3q9->3q9R4q9->4q9R5q9->5q9R6q9->6q9R7q9->7q9R8q9->8q9R9q9->9q9R0q10->1q11L1q10->2q11L2q10->3q11L3q10->4q11L4q10->5q11L5q10->6q11L6q10->7q11L7q10->8q11L8q10->9q11L9q10->0q12L0q11->0q11L1q11->1q11L2q11->2q11L3q11->3q11L4q11->4q11L5q11->5q11L6q11->6q11L7q11->7q11L8q11->8q11L9q11->9q11L%q11->%q13L%q13->%q13L0q13->0q2H1q13->1q2H2q13->2q2H3q13->3q2H4q13->4q2H5q13->5q2H6q13->6q2H7q13->7q2H8q13->8q2H9q13->9q2H0q12->1q11L1q12->2q11L2q12->3q11L3q12->4q11L4q12->5q11L5q12->6q11L6q12->7q11L7q12->8q11L8q12->9q11L9q12->0q14L%q14->1q11LНачальная конфигурация.Результат выполнения(сложение выполнено):Программа, заменяющая входное слово на обратное ему (дано слово, вывести его в обратном порядке)Пусть алфавит машины , причем слова состоят из символов А,В, а символ * используется как вспомогательный.Используем следующий алгоритм:Идем в конец слова и после него ставим разделяющий маркер *.Идем влево от маркера, если встречаем букву, запоминаем ее в соответствующем состоянии, пишем вместо нее маркер *, идет вправо до пустой ячейки, пишем в нее соответствующую букву, идем влево до первого маркера, начинаем программу с начала пункта 2.Если идя влево по маркерам вышли на пустую ячейку, идем вправо и стираем все маркеры, на первой букве останавливаемся.ABλ*Q1Q1ARQ1BRQ2*LQ2Q3*RQ4*RQ5λRQ2*LQ3Q3ARQ4BRQ6ALQ3*RQ4Q4ARQ4BRQ6BLQ4*RQ5Q7HQ7HQ5λRQ6Q6ALQ6BLQ2*LQ7Код программы в эмуляторе(Q7=STOP,%-пустая клетка, q7:=старт на %):%q7->%q1Raq1->aq1Rbq1->bq1R%q1->*q2Laq2->*q3Rbq2->*q4R*q2->*q2L%q2->%q5R*q3->*q3Raq3->aq3Rbq3->bq3R%q3->aq6L*q4->*q4Raq4->aq4Rbq4->bq4R%q4->bq6L*q5->%q5Raq5->aSTOPHbq5->bSTOPHaq6->aq6Lbq6->bq6L*q6->*q2HНачальное состояние:Результат выполнении(слово обращено):Программа, удаляющая символы А в словеПусть алфавит машины , причем слова состоят из символов А,В, а символ * используется как вспомогательный.Используем следующий алгоритм:Заменяем каждый символ А на * и возвращаемся в начало преобразованного слова.Q1Q2A->*RB->BRλ->λL*->*LB->BLQ3λ->λRВыходим на самую первую звездочку справа, если ее нет, то в начало слова:end.Q3Q4B->BR*->*НQ5λ->λLB->BLλ->λRСтоя на звездочке, идем вправо, до первого символа, отличного от звездочки.