Написание программы на машине Тьюринга

СХЕМА ПРИМИТИВНОЙ РЕКУРСИИ ФУНКЦИИ q(x,y) Личного ОТ ЦЕЛОГО ДЕЛЕНИЯ y НА x

Схему примитивной рекурсии для функции q(x,y) личного от целого деления y на x смотрится последующим образом:

(1)

Функция q(x,y) примитивно рекурсивная, потому что функции r(x,y), сложение, усечённая разность, sg(x) и Написание программы на машине Тьюринга отрицание являются примитивно рекурсивными.

Проверим данную схему рекурсии, будим вычислять значения q(x,y). Возьмём x=4 и y=14. (табл. 1)

Таблица 1 – Проверка ПР.

y y/x ]y/x[ r(x,y) f=|x-(r(x,y)+1)| sg(f) ⌐sg(f) q(x,y) Состояние
_ _ _ _ -
0,25 Сохранение значения
0,5 Сохранение значения
0,75 Сохранение значения
Переход Написание программы на машине Тьюринга
1,25 Сохранение значения
1,5 Сохранение значения
1,75 Сохранение значения
Переход
2,25 Сохранение значения
2,5 Сохранение значения
2,75 Сохранение значения
Переход
3,25 Сохранение значения
3,5 Сохранение значения

Набросок 1 – графическое отображение ПРФ

Разумеется, что функция перебегает в новое значение в точках, в каких y делится на x без остатка. (Рис.1)

РАЗРАБОТКА Программки ДЛЯ МАШИНЫ ПОСТА

Мысль решения

Мысль решения состоит в том, что Написание программы на машине Тьюринга наибольший порядок постова слова равен 3 и как количество попорядку стоящих пробелов будет больше 3, то это значит, что постово слово завершилось и необходимо ворачиваться к началу. (Рис.2; рис.3)

Набросок 2 – Начальное состояние машины Поста

Набросок 3 – Конечное состояние машины Поста

Составление схем

Процесс проектирования заключается в составлении алгоритмов, которые будут исполняться позднее на машине Поста Написание программы на машине Тьюринга. Основными вспомогательными элементами являются большая схема метода (рис.4), позволяющая представить способ решения в целом; и детализированная схема метода, отображающая будущий код в доступном восприятию человека схематическом виде (рис.5).

Набросок 4 – Большая схема метода

Набросок 5 – Детализированная схема метода. Лист 1

Рис. 5 Лист 2

Написание программки на машине Поста

Результатом написания кода на машине Поста является Написание программы на машине Тьюринга работающая программка, позволяющая уменьшать порядок постова слова на 1, при условии, что наибольший порядок 3.

Снимки экрана работающей программки представлены на рисунках 6-9.

Набросок 6 – Работающая программка Поста (Снимок 1)

Набросок 7 – Работающая программка Поста (Снимок 2)

Набросок 8 – Работающая программка Поста (Снимок 3)

Набросок 9 – Работающая программка Поста (Снимок 4)

Анализ результата

Приобретенная программка на сто процентов делает намеченную цель Написание программы на машине Тьюринга. Программка была написана для постова слова порядка 3. Содержит 21 строчку кода.

РАЗРАБОТКА Программки ДЛЯ МАШИНЫ ТЬЮРИНГА

Мысль решения

Мысль решения состоит в том, что, начиная с первой буковкы моей фамилии, буковкы копируются за знак *.

Наружный алфавит машины Тьюринга: A={ ,г,и,з,т,д,н,о,в,*}

Составление ГСП и ТСП

Набросок 10 – ГСП программки

Таблица Написание программы на машине Тьюринга 2 – ТСП программки.

Q\A г и з т д н о в * λ
q1 q1 г R q1 и R q1 з R q1 т R q1 д R q1 н R q1 о R q1 в R _ q2 * R
q2 _ _ _ _ _ _ _ _ _ q3 г L
q3 _ q4 и Написание программы на машине Тьюринга L _ q3 т L _ q3 н L q3 о L q3 в L q3 * L _
q4 q5 г R _ q3 з L _ q3 д L _ _ _ _ _
q5 q5 г R q5 и R q5 з R q5 т R q5 д R q5 н R q5 о R q5 в R q5 * R Написание программы на машине Тьюринга q6 и L
q6 q6 г L q6 и L q7 з R q6 т L q6 д L q6 н L q6 о L q6 в L q6 * L _
q7 q7 г R q7 и R _ q7 т R q7 д R q7 н R Написание программы на машине Тьюринга q7 о R q7 в R q7 * R q8 з L
q8 _ q9 и L _ q8 т L _ q8 н L q8 о L q8 в L q8 * L _
q9 q8 г L _ q10 з R _ q8 д L _ _ _ _ _
q10 q10 г R q10 и R q10 з R q10 т R Написание программы на машине Тьюринга q10 д R q10 н R q10 о R q10 в R q10 * R q11 и L
q11 q11 г L q11 и L q11 з L q12 т R q11 д L q11 н L q11 о L q11 в L q11 * L _
q12 q12 г Написание программы на машине Тьюринга R q12 и R q12 з R _ q12 д R q12 н R q12 о R q12 в R q12 * R q13 т L
q13 q13 г L q13 и L q13 з L _ q14 д R q13 н L q13 о L q13 в L q13 * L _
q14 q Написание программы на машине Тьюринга14 г R q14 и R q14 з R q14 т R _ q14 н R q14 о R q14 в R q14 * R q15 д L
q15 _ q16 и L _ q15 т L _ q15 н L q15 о L q15 в L q15 * L _
q16 q15 г L _ q15 з Написание программы на машине Тьюринга L _ q17 д R _ _ _ _ _
q17 q17 г R q17 и R q17 з R q17 т R q17 д R q17 н R q17 о R q17 в R q17 * R q18 и L
q18 q18 г L q18 и L q18 з L q18 т L q18 д Написание программы на машине Тьюринга L q19 н R q18 о L q18 в L q18 * L _
q19 q19 г R q19 и R q19 з R q19 т R q19 д R _ q19 о R q19 в R q19 * R q20 н L
q20 q20 г L q20 и L q Написание программы на машине Тьюринга20 з L q20 т L q20 д L _ q21 о R q20 в L q20 * L _
q21 q21 г R q21 и R q21 з R q21 т R q21 д R q21 н R _ q21 в R q21 * R q22 о L
q22 q22 г L q22 и L q22 з Написание программы на машине Тьюринга L q22 т L q22 д L q22 н L _ q23 в R q22 * L _
q23 q23 г R q23 и R q23 з R q23 т R q23 д R q23 н R q23 о R _ q23 * R q24 в L
q24 q24 г L q24 и Написание программы на машине Тьюринга L q24 з L q24 т L q24 д L q24 н L q24 о L q24 в L q24 * L qz λ R

Написание программки на машине Тьюринга

На рисунках 11 – 12 представлен кусок программки с наружным алфавитом машины Тьюринга: A={ ,г,и,з,т,д,*}.

Набросок 11 – Работающая программка Тьюринга (Снимок Написание программы на машине Тьюринга 1)

Набросок 12 – Работающая программка Тьюринга (Снимок 2)

На рисунках 13 – 15 представлена написанная программка по ТСП.

Набросок 13 – Работающая программка Тьюринга (Снимок 3)

Набросок 14 – Работающая программка Тьюринга (Снимок 4)

Набросок 15 – Работающая программка Тьюринга (Снимок 5)

Анализ результата

Написанная программка позволяет скопировать мою фамилию и возвратить каретку в начало. Программка содержит 24 состояния.

ВЫВОД

Была решена задачка на примитивную рекурсию, спроектированы и написаны Написание программы на машине Тьюринга программки: уменьшение порядка постова слова на 1 и копирование собственной фамилии на машине Тьюринга.

Перечень ЛИТЕРАТУРЫ

1. Ершов, С. С. Элементы теории алгоритмов: учебное пособие/ С. С. Ершов. — Челябинск: Изд-во ЮУрГУ, 2009. — 64 с.

2. Ершов С.С., Надточий И.Л., Самохвалов А.В. Прикладная математика: Учебное пособие по практическим занятиям Написание программы на машине Тьюринга. – Челябинский ЧТУ, 1992. – 85с.

3. 100 ЮУрГУ 04–2008 Эталон организации. Курсовое и дипломное проекти-рование. Общие требования к содержанию и оформлению / составители: Т.И. Парубочая, Н.В. Сырейщикова, В.И. Гузеев, Л.В. Винокурова. – Челябинск: Изд-во ЮУрГУ, 2008. – 56 с.


namereniya-v-segmentah-izbiratelnaya-filtraciya.html
nami-012-obrazca-1949-goda-na-zimnih-ispitaniyah-interesno-esli-zagruzhennij-les-pustit-na-toplivo-na-skolko-kilometrov-hoda-ego-hvatit.html
naming-ili-nashi-na-zapade-referat.html