9 — Конечное состояние машины Тьюрингав эмуляторе Полякова.
Рис. 10 — Конечное состояние машины Тьюрингав эмуляторе Куприянова.
Результаты выполнения программы на эмуляторах Полякова и Куприянова совпадают. В результате вектор коэффициентов АНФ разделен на блоки.
2.4. Блок IV. Дизъюнкцияэлементов вектора коэффициентов АНФПредыдущий программный блок закончил выполнение в положении, когда каретка расположена над самым правым коэффициентом вектора, соответствующим свободному члену арифметической нормальной формы. Коэффициент при xn (если он имеется) расположен слева от каретки через две пустых ячейки, а остальные блоки коэффициентов отделены друг от друга одной пустой ячейкой. Задача финального блока заключается в обнуление первых (справа) элементов каждой из полученных частей (соответствующих коэффициентам перед одночленами первой и нулевой степени) и нахождение дизъюнкции всех элементов вектора коэффициентов. Разобьем задачу на две части: вначале последовательно обнулим первые элементы каждого блока (табл. 6), затем найдем дизъюнкцию элементов вектора (табл. 7).Таблица 6 — Подпрограмма обнуления первых элементов каждого блокаQA_01Комментарийq1-q28 — формирование блоков вектора коэффициентов полинома Жегалкина (блок III) q29_ R q29_ L q30_ L q30q29 — удаляем свободный член, смещаемся влевоq30_ L q31halthaltq30 — пропускаем пустую ячейкуq31_ L q32halthaltq31 — пропускаем вторую пустую ячейкуq320N 360 L q330 L q33q32 — обнуляем коэффициент при xn, смещаемся влевоq33_ L q34halthaltq33 — пропускаем пустую ячейкуq34_ R q360 L q350 L q35q34 — обнуляем первый элемент блока, шаг влевоq35_ L q340 L q351 L q35q35 — смещаемся в начало след. блока, возврат в q34q36_ R q36halthaltq36 — возврат в первую непустую ячейку, останов.
Таблица 7 — Подпрограмма нахождениядизъюнкции коэффициентов вектораQA_01Комментарийq1-q35-обнуление первых элементов каждого блока (блок IVа) q36_ R q36_ R q37_ R q38q36 — запоминаем и удаляем текущее значение, вправоq37_ R q39_ R q37_ R q38q37 — дизъюнкция с 0/пропуск пустой ячейки, вправоq38_ R q40_ R q38_ R q37q38 — дизъюнкция с 1/пропуск пустой ячейки, вправоq390 N q41_ R q37_ R q38q39 — дизъюнкция с 0/записываем результат (0)q401 N q41_ R q38_ R q37q40 — дизъюнкция с 1/записываем результат (1)q41halthalthaltq41 — завершение выполнения программы.
Результат обнуления первых элементов каждого блока:
Рис. 11 — Конечное состояние машины Тьюрингав эмуляторе Полякова.
Рис. 12 — Конечное состояние машины Тьюрингав эмуляторе Куприянова.
Результаты выполнения программы на эмуляторах Полякова и Куприянова совпадают. В результате первые элементы каждого блока (соответствующие коэффициентам перед одночленами первой и нулевой степени) обнулены. Результат нахождениядизъюнкции элементов вектора коэффициентов полинома Жегалкина, соответствующих нелинейным одночленам:
Рис. 13- Конечное состояние машины Тьюрингав эмуляторе Полякова.
Рис. 14 — Конечное состояние машины Тьюрингав эмуляторе Куприянова.
В результате получаем, что булева функция, заданная вектором значений f = 11 000 010, нелинейна (результат выполнения программы равен 1).
3. Тестированиеи определение параметров работы программы.
Протестируем работу программы на булевых функциях малой арности. Для каждой функции укажем ее десятичный номер, соответствующий двоичный вектор значений булевой функции, полином Жегалкина, определим линейность функции (на основе полинома Жегалкина), приведем результат выполнения программы на машине Тьюринга и число шагов программы. Таблица 8 — Нульарные булевы функции.
НомерВектор
ПолиномЛинейность.
РезультатЧисло шагов000да22 111да022Таблица 9 — Унарные булевы функции.
НомерВектор
ПолиномЛинейность.
РезультатЧисло шагов0000да451 011 + xда4 5210xда453 111да045Таблица 10 — Бинарные булевы функции.
НомерВектор
ПолиномЛинейность.
РезультатЧисло шагов0да122 100 011 + x + y + x yнет11 222 0010y + x yнет1 122 300 111 + xда1 224 0100x + x yнет1 122 501 011 + yда1 226 0110x + yда122 701 111 + x yнет11 228 1000x yнет1 122 910 011 + x + yда12 210 1010yда1 221 110 111 + x + x yнет112 212 1100xда1 221 311 011 + y + x yнет112 214 1110x + y + x yнет11 221 511 111да0122.
Проверим также работу программы для функций большей арности и определим число шагов, необходимых для ее выполнения, в зависимости от числа переменных функции и длины вектора значений. Таблица 11 — Зависимость числа шагов от числа переменных и длины вектора.
Число переменных123 456.
Длина вектора1 248 163 264.
Число шагов22 451 223 611 188 424 212 480.
Построим график найденной эмпирической зависимости числа шагов программы от длины вектора булевой функции и аппроксимируем ее с помощью полиномиального тренда второй степени:
Рис. 15 — Аппроксимация зависимости числа шагов от длины вектора.
Определим погрешность аппроксимации:
Таблица 12 — Определение погрешности аппроксимации эмпирической функции.
Число переменных123 456.
Длина вектора1 248 163 264.
Число шагов22 451 223 611 188 424 212 480.
Оценка20.
747.
2122.
2360.
1 187.
24 247.
815 993.8Округление21 471 223 601 187 426 140 160.
Погрешность1−2011;10Итак, с высокой степенью точности число шаговN программы машины Тьюринга описывается квадратичной зависимостью от длины вектора Lзначений булевой функции. Зависимость имеет вид: N (L) 3.662L2 + 15.511L + 1.
551.Т.к. для булевой функции от n аргументов задающий ее вектор имеет длину: L = 2n, то искомая зависимость числа шагов N программы от числа аргументов nфункции: N (n) = 3.66222n + 15.5112n + 1.
551.Таким образом, зависимость числа шагов программы машины Тьюринга, определяющей принадлежность заданной вектором своих значений булевой функции к классу линейных функций, имеет показательную зависимость от числа переменных n и квадратичную зависимость от длины вектора 2n булевой функции.
Заключение
.
В данной работе дан краткий исторический обзор развития таких имеющих важное прикладное и теоретическое значение математических дисциплин как логика, математическая логика, теория булевых функций, дискретная математика, теория автоматов. В теоретической части рассмотрены понятие булевой функции, способы задания булевой функции, понятие линейности булевой функции, полином Жегалкина, алгебраическая нормальная форма, описаны способы задания машины Тьюринга. В практической части рассмотрен метод треугольника Паскаля построения полинома Жегалкина для заданной своим вектором значений булевой функции. Разработан алгоритм проверки произвольной булевой функции, заданной своим вектором значений, на принадлежность к классу линейных булевых функций. Построена программамашины Тьюринга, реализующая этот алгоритм. Для написания и отладки программ для машины Тьюринга использовались эмуляторы «Тренажер для изучения универсального исполнителя.
Машина Тьюринга"Константина Полякова и «Эмулятор Машины Тьюринга"Максима Куприянова, позволяющий автоматически подсчитывать число шагов исполняющейся программы машины Тьюринга. Результаты тестирования показывают, что программа дает верные результаты для всех нульарных, унарных и бинарных булевых функций. На основании проведенных исследований сделан вывод о том, что зависимость числа шагов программы машины Тьюринга, определяющей принадлежность заданной вектором своих значений булевой функции к классу линейных функций, имеет показательную зависимость от числа переменных n и квадратичную зависимость от длины вектора 2n булевой функции. Список использованной литературы1. Игошин В. И. Математическая логика и теория алгоритмов: учеб.
пособие для студ. высш. учеб. заведений / В. И. Игошин. — М.: Издательский центр «Академия», 2008. — 448 с.
2. Карпов Ю. Г. Теория автоматов / Ю. Г. Карпов. — СПб.: Питер, 2003. — 208 с.
3. Куприянов М. Эмулятор Машины Тьюринга [Электронный ресурс] / М. Куприянов. — Режим доступа:
https://kouprianov.com/2011/11/turing-machine-emulator/4. Марченков С. С. Замкнутые классы булевых функций / С. С. Марченков. — М.: ФИЗМАТЛИТ, 2000. — 128 с.
5. Пильщиков В. Н. Машина Тьюринга и алгоритмы Маркова. Решение задач / В. Н. Пильщиков, В. Г. Абрамов, А. А. Вылиток, И. В. Горячая. — М.: МГУ, 2006. — 47 с.
6. Поляков К. Ю. Тренажер для изучения универсального исполнителя"Машина Тьюринга"[Электронный ресурс]/ К. Ю. Поляков. — Режим доступа:
http://kpolyakov.spb.ru/prog/turing.htm7. Яблонский С. В.
Введение
в дискретную математику: Учеб.
пособие для вузов / С. В. Яблонский. — М.: Наука, 1986. — 384 с.
