Оценка времени проверки булевой функции на линейность на машине Тьюринга

Введение 3
Теоретическая часть 6
1. Булевы функции 6
2. Машина Тьюринга 8
Практическая часть 10
1. Разработка алгоритма 10
2. Реализация алгоритма на машине Тьюринга 13
3. Тестирование и определение параметров работы программы 25
Заключение 28
Список использованной литературы 29

9 – Конечное состояние машины Тьюрингав эмуляторе ПоляковаРис. 10 – Конечное состояние машины Тьюрингав эмуляторе КуприяноваРезультаты выполнения программы на эмуляторах Полякова и Куприянова совпадают. В результате вектор коэффициентов АНФ разделен на блоки.2.4. Блок IV. Дизъюнкцияэлементов вектора коэффициентов АНФПредыдущий программный блок закончил выполнение в положении, когда каретка расположена над самым правым коэффициентом вектора, соответствующим свободному члену арифметической нормальной формы. Коэффициент при xn (если он имеется) расположен слева от каретки через две пустых ячейки, а остальные блоки коэффициентов отделены друг от друга одной пустой ячейкой.Задача финального блока заключается в обнуление первых (справа) элементов каждой из полученных частей (соответствующих коэффициентам перед одночленами первой и нулевой степени) и нахождение дизъюнкции всех элементов вектора коэффициентов.Разобьем задачу на две части: вначале последовательно обнулим первые элементы каждого блока (табл. 6), затем найдем дизъюнкцию элементов вектора (табл. 7).Таблица 6 – Подпрограмма обнуления первых элементов каждого блокаQ\A_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 – Подпрограмма нахождениядизъюнкции коэффициентов вектораQ\A_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 = 11000010, нелинейна(результат выполнения программы равен 1).3. Тестированиеи определение параметров работы программыПротестируем работу программы на булевых функциях малой арности.Для каждой функции укажем ее десятичный номер, соответствующий двоичный вектор значений булевой функции, полином Жегалкина, определим линейность функции (на основе полинома Жегалкина), приведем результат выполнения программы на машине Тьюринга и число шагов программы.Таблица 8 – Нульарные булевы функцииНомерВекторПолиномЛинейностьРезультатЧисло шагов000да022111да022Таблица 9 – Унарные булевы функцииНомерВекторПолиномЛинейностьРезультатЧисло шагов0000да0451011 + xда045210xда0453111да045Таблица 10 – Бинарные булевы функцииНомерВекторПолиномЛинейностьРезультатЧисло шагов000000да0122100011 + x + y + x yнет112220010y + x yнет1122300111 + xда012240100x + x yнет1122501011 + yда012260110x + yда0122701111 + x yнет112281000x yнет1122910011 + x + yда0122101010yда01221110111 + x + x yнет1122121100xда01221311011 + y + x yнет1122141110x + y + x yнет11221511111да0122Проверим также работу программы для функций большей арности и определим число шагов, необходимых для ее выполнения, в зависимости от числа переменных функции и длины вектора значений.Таблица 11 – Зависимость числа шагов от числа переменных и длины вектораЧисло переменных0123456Длина вектора1248163264Число шагов22451223611188424715994Построим график найденной эмпирической зависимости числа шагов программы от длины вектора булевой функции и аппроксимируем ее с помощью полиномиального тренда второй степени:Рис. 15 – Аппроксимация зависимости числа шагов от длины вектораОпределим погрешность аппроксимации:Таблица 12 – Определение погрешности аппроксимации эмпирической функцииЧисло переменных0123456Длина вектора1248163264Число шагов22451223611188424715994Оценка20.747.2122.2360.01187.24247.815993.8Округление21471223601187424815994Погрешность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 с.