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

В данной работе дан краткий исторический обзор развития таких имеющих важное прикладное и теоретическое значение математических дисциплин как логика, математическая логика, теория булевых функций, дискретная математика, теория автоматов.
В теоретической части рассмотрены понятие булевой функции, способы задания булевой функции, понятие линейности булевой функции, полином Жегалкина, алгебраическая нормальная форма, описаны способы задания машины Тьюринга.
В практической части рассмотрен метод треугольника Паскаля построения полинома Жегалкина для заданной своим вектором значений булевой функции. Разработан алгоритм проверки произвольной булевой функции, заданной своим вектором значений, на принадлежность к классу линейных булевых функций. Построена программа машины Тьюринга, реализующая это ...

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

Логика образует такой пласт общечеловеческой культуры, без освоения которого в настоящее время не может состояться ни одна мыслящая личность. Основы логической культуры закладываются в школе и в первую очередь на уроках математики, ибо, как точно подметил еще Л.Н. Толстой, «математика имеет задачей не обучение исчислению, но обучение приемам человеческой мысли при исчислении».
Математическая логика – вершина развития логики, достигнутая ею в XX в. Органично соединив в себе традиционную логику, восходящую к Аристотелю, и методы современной математики, она получила глубокие результаты, которые легли в основу проектирования и создания электронно-вычислительных машин и программного обеспечения к ним, нашли широчайшее применение в областях информатики и систем искусственного интеллекта.
Теория булевых функций, возникшая из алгебры логики, лежит в фундаменте современной дискретной математики. Наряду с булевыми предикатами булевы функции являют собой самые простые объекты дискретной природы. Язык булевых функций хорошо приспособлен для описания подразделения целого на части и взаимосвязи этих частей. Поэтому он широко используется в самых разнообразных областях человеческого знания: будь то собственно математика или кибернетика (теория множеств и математическая логика, алгебра, теория графов и комбинаторика, теория информации, теория формальных языков и языков программирования, синтез управляющих систем и распознавание образов и т.д.), техника (анализ и построение различных устройств коммутации, управления и переработки информации, включая современные ЭВМ, тестирование сложных систем и построение надежных схем из ненадежных элементов), экономика, биология или социология. Список областей, где могут применяться и с успехом применяются результаты и методы теории булевых функций, нетрудно продолжить и далее.
В вопросах приложений булевых функций наиболее часто встречаются две основные задачи: можно ли выразить заданную функцию или заданный класс функций булевыми функциями из имеющегося запаса булевых функций, и если это возможно, то каким образом и с какой сложностью? Это в свою очередь приводит к задаче описания замкнутых классов булевых функций и проверки функции на принадлежность к заданному классу.
Теория автоматов – раздел дискретной математики, изучающий абстрактные автоматы – вычислительные машины, представленные в виде математических моделей – и задачи, которые они могут решать. В 30-е гг. XX в., задолго до появления компьютеров, Алан Тьюринг исследовал абстрактную машину, которая, по крайней мере в области вычислений, обладала всеми возможностями современных вычислительных машин. Целью Тьюринга было точно описать границу между тем, что вычислительная машина может делать, и тем, чего она не может. Полученные им результаты применимы не только к абстрактным машинам Тьюринга, но и к реальным современным компьютерам.
Затем, в 60–70-х гг. Стивен Кук развил результаты Тьюринга о вычислимости и невычислимости. Ему удалось разделить задачи на те, которые могут быть эффективно решены вычислительной машиной, и те, которые, в принципе, могут быть решены, но требуют для этого так много машинного времени, что компьютер оказывается практически бесполезным для решения почти всех экземпляров задачи, за исключением небольшого числа. Задачи последнего класса называют «трудно разрешимыми» или «NP-трудными». Даже при экспоненциальном росте быстродействия вычислительных машин («закон Мура») весьма маловероятно, что нам удастся достигнуть значительных успехов в решении задач этого класса на классических компьютерах.
Моделирование алгоритмов на машине Тьюринга помогает нам уяснить принципиальные возможности программного обеспечения. В частности, теория сложности вычислений позволяет определить, можем ли мы решить ту или иную задачу «в лоб» и написать соответствующую программу для ее решения (если эта задача не принадлежит классу «трудно разрешимых»), или же нам следует искать решение данной трудно разрешимой задачи в обход, используя приближенный, эвристический, или какой-либо другой метод, с помощью которого удастся ограничить время, затрачиваемое программой на ее решение.
Оценка времени проверки булевой функции на линейность на машине Тьюринга является примером одной из таких задач, имеющих как практическую, так и теоретическую ценность.
В данной работе будет рассмотрен класс линейных булевых функций и задача проверки произвольной булевой функции, заданной своим вектором значений, на принадлежность к этому классу c помощью машины Тьюринга.

Некоторые состояния машины Тьюринга могут быть помечены как терминальные (конечные), и переход в любое из них означает конец работы и остановку алгоритма.Конкретная машина Тьюринга задается перечислением элементов множества символов алфавита A, множества состояний Q и набором правил, по которым работает машина.Все правила имеют вид:(qi, aj) (qi1, aj1, dk),означающий, что если головка находится в состоянии qi и в текущей ячейке записан символ aj, то головка переходит в состояние qi1, в ячейку вместо символа aj записывается символ aj1 и головка совершает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N).Для каждой возможной конфигурации (qi, aj) имеется ровно одно правило, за исключением терминального состояния, попав в которое машинаостанавливается. Также необходимо указать начальное и конечное состояния, начальную конфигурацию на ленте и расположение головки машины.Практическая часть1. Разработка алгоритмаИтак, задача проверки линейности булевой функции сводится к построению полинома Жегалкина и проверке его коэффициентов.Рассмотрим подробнее один из способов сведения заданной булевой функции к алгебраической нормальной форме: метод треугольника (также называется методом треугольника Паскаля).Данный метод позволяет преобразовать таблицу истинности в полином Жегалкина путем построения вспомогательной треугольной таблицы в соответствии со следующими правилами:000001010011100101110111x1x2x3f1x3x2x2x3x1x1x3x1x2x1x2x3000110101001001111111010100000011011000010100000111010010110111f = 1 x1 x2 x1x2x311100Рис. 1 – Метод треугольника1. Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 00…0 до 11…1.2. Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.3. Ячейка в каждом последующем столбце получается путем суммирования по модулю 2 двух ячеек предыдущего столбца – стоящей в той же строке и строкой ниже.4. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.5. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций, в которых стоят единицы.6. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.Метод треугольника для построения полинома Жегалкина допускает достаточно очевидную реализацию на машине Тьюринга:1. Задаем булеву функцию от n переменных вектором длины 2n из алфавита A = {0, 1}, окруженную с обеих сторон пустыми символами , головку машины Тьюринга располагаем в крайней слева ячейке.2. Свободный член полинома Жегалкина равен f(0, 0, …, 0) и расположен в крайней ячейке слева – копируем его влево от заданного вектора, отделив от него пустым символом, и возвращаемся к началу вектора.3. Последовательно суммируем по модулю 2 соседние значения вектора значений функции, записывая результат на место первого аргумента слева – в результате длина вектора значений уменьшается на 1.4. Возвращаемся к началу вектора значений и копируем следующий коэффициент полинома Жегалкина из крайней слева ячейки влево от вектора, непосредственно за последним из ранее скопированных коэффициентов, и возвращаемся к началу вектора.5. Если вектор пуст, останавливаемся, иначе возвращаемся к пункту 3.В результате слева от заданного вектора значений функции (который к данному моменту пуст) будет расположен вектор коэффициентов полинома Жегалкина от младших (крайняя правая позиция) к старшим (крайняя левая позиция), а головка машины Тьюринга будет расположена через клетку справа от вектора коэффициентов.Теперь необходимо выяснить, имеются ли в построенном многочлене слагаемые степени выше первой с ненулевыми коэффициентами.Заметим, что коэффициенты одночленов первой и нулевой степени располагаются в позициях …0002 = 0; …0012 = 1; …0102 = 2; …1002 = 4 – т.е. в общем случае в позиции 0 или 2k, где 0 ≤ k < n.Таким образом, достаточно определить, имеется ли хотя бы один ненулевой (т.е. равный 1) коэффициент на позициях, отличных от 0 и 2k.Сделать это можно следующим образом:1. Разделим полученный вектор коэффициентов на две равные части – начальным коэффициентом второй части (считая справа налево) будет являться коэффициент при одночлене первой степени – обнулим его.2. Разделим первую (справа) часть вектора коэффициентов на две равные части и обнулим начальный коэффициент новой второй части.3. Будем продолжать процесс до тех пор, пока каждая из вновь полученных частей не будет содержать по одному коэффициенту – их также обнулим (как свободный член и коэффициент при xn).4. Теперь найдем дизъюнкцию всех полученных элементов – если она равна 1, то многочлен Жегалкина содержит слагаемые выше первой степени и заданная булева функция не является линейной. Если же результат дизъюнкции равен 0, то заданная булева функция линейна.Таким образом, общая схема алгоритма состоит из следующих основных блоков:I. Попарное суммирование по модулю 2 рядом расположенных элементов вектора значений функции и получение нового вектора значений.II. Копирование на каждом шаге первого элемента вектора значений в новый вектор коэффициентов полинома Жегалкина.III. Последовательно деление полученного вектора коэффициентов на две равные части с сохранением одной из частей (левой) и делением второй.IV. Обнуление первых (справа) элементов каждой из полученных частей (соответствующих коэффициентам перед одночленами первой и нулевой степени) и нахождение дизъюнкции всех элементов разделенного вектора коэффициентов.2. Реализация алгоритма на машине ТьюрингаБудем последовательно осуществлять реализацию каждого из описанных выше блоков общей схемы алгоритма.Пусть вектор значений функции записан на ленту в алфавите {0, 1} и каретка обозревает первую ячейку слева, соответствующую набору аргументов (x1, x2, …, xn) = (0, 0, …, 0) = 00…0.Команды машины Тьюринга будем записывать в формате:aiqj a\eq \o(';i)Dq\eq \o(';i), где D{L, R, N} – направление смещения каретки.Начальное состояние: q1, конечное (терминальное) состояние: q0.Пустой символ  будем обозначать символом подчеркивания _.2.1. Блок I. Суммирование элементов вектора значений по модулю 2Переход от одного вектора значений к следующему в методе треугольника можно осуществить с помощью следующей программы для машины Тьюринга:Таблица 2 – Программа суммирования по модулю 2НомерКомандаКомментарий_q1 _Nq0Если в начальном состоянии текущая ячейка пуста, останавливаемся0q1 0Rq2Иначе смещаемся в ячейку справа1q1 1Rq2_q2 _Lq5Если вектор закончился, возвращаемся влево в состояние q50q2 0Lq3Запоминаем значение в текущей ячейке и смещаемся в ячейку слева1q2 1Lq40q3 0Rq1Выполняем сложение по модулю 2 и смещаемся вправо, возвращаясь в начальное состояние q11q3 1Rq10q4 1Rq11q4 0Rq10q5 _Nq5Затираем последний элемент вектора1q5 _Nq5_q5 _Nq0Останавливаем выполнение программыДля написания и отладки программ для машины Тьюринга воспользуемся двумя реализациями эмуляторов: «Тренажер для изучения универсального исполнителя Машина Тьюринга» Константина Полякова и «Эмулятор Машины Тьюринга» Максима Куприянова.Рис. 2 – Вид машины Тьюринга в начальном состоянииРис. 3 – Вид машины Тьюринга в конечном состоянииИсполним ту же программу на эмуляторе Куприянова:Рис. 4 – Вид машины Тьюринга в начальном состоянииРис. 5 – Вид машины Тьюринга в конечном состоянииЭмулятор Куприянова позволяет получать сведения о времени выполнения и числе шагов программы:Рис. 6 – Информация о времени выполнения и числе шаговТакже доступен протокол выполнения программы:Шаг #1: (q2,0) → (q3,0,L)Шаг #2: (q3,1) → (q1,1,R)Шаг #3: (q1,0) → (q2,0,R)Шаг #4: (q2,1) → (q4,1,L)Шаг #5: (q4,0) → (q1,1,R)Шаг #6: (q1,1) → (q2,1,R)Шаг #7: (q2,0) → (q3,0,L)Шаг #8: (q3,1) → (q1,1,R)Шаг #9: (q1,0) → (q2,0,R)Шаг #10: (q2,_) → (q5,_,L)Шаг #11: (q5,0) → (q5,_,N)Шаг #12: Встретилась стоп-клетка (q5,_), конечное состояниеВозможен экспорт текста программы в форматы .txt и .xls:Таблица 3 – Программа суммирования по модулю 2 (экспорт в файл Excel)Q\A_01q1halt0 R q21 R q2q2_ L q50 L q31 L q4q3halt0 R q11 R q1q4halt1 R q10 R q1q5halt_ N q5_ N q5Результаты выполнения программы на эмуляторах Полякова и Куприянова совпадают и соответствуют преобразованию исходного вектора значений булевой функции с помощью попарного сложения элементов по модулю 2.2.2. Блок II. Формирование вектора коэффициентов АНФТеперь дополним первый блок вычислений копированием на каждом шаге начальной ячейки вектора значений в новый вектор коэффициентов полинома Жегалкина.Т.к. подпрограмма копирования предваряет блок формирования нового вектора значений, номера состояний первого блока будут перенумерованы.Таблица 4 – Программа получения вектора коэффициентов полинома ЖегалкинаНомерКомандаКомментарий_q1 _Nq0Если в состоянии q1 текущая ячейка пуста, останавливаемся0q1 0Lq2Иначе запоминаем значение в текущей ячейке и смещаемся влево1q1 1Lq3_q2 _Lq4Пропускаем одну пустую ячейку и смещаемся влево_q3 _Lq5_q4 0Rq6Записываем запомненное ранее значение и смещаемся вправо_q5 1Rq6_q6 _Rq7Пропустив пустую ячейку, возвращаемся в начало вектора значений0q4 0Lq4Проход в конец вектора коэффициентов (справа налево)1q4 1Lq40q5 0Lq51q5 1Lq50q6 0Rq4Проход в начало вектора коэффициентов (слева направо)1q6 1Rq4_q7 _Nq0Подпрограмма формирования нового вектора значений (блок I)0q7 0Rq81q7 1Rq8_q8 _Lq110q8 0Lq91q8 1Lq100q9 0Rq11q9 1Rq10q10 1Rq11q10 0Rq10q11 _Lq12Затираем последний элемент вектора значений и смещаемся влево1q11 _Lq121q12 1Lq12Проход в начало вектора значений (справа налево)0q12 0Lq12_q12 0Lq1При достижении начала вектора значений возвращаемся в q1Рис. 7 – Начальное и конечное состояние машины Тьюринга в эмуляторе ПоляковаВыполним программу на эмуляторе Полякова (рис. 7) и Куприянова (рис. 8).Рис. 8 – Состояния машины Тьюринга в эмуляторе КуприяноваРезультаты выполнения программы на эмуляторах Полякова и Куприянова совпадают и соответствуют вектору коэффициентов АНФ 10101001.2.3. Блок III. Деление вектора коэффициентов АНФ на блокиПредыдущий программный блок закончил выполнение в положении, когда каретка расположена справа от вектора коэффициентов через одну пустую клетку, а коэффициенты самого вектора расположены в обратном порядке справа налево. Задача текущего блока заключается в последовательном делении полученного вектора коэффициентов на две равные части с сохранением одной из частей и дальнейшим делением второй. Процесс деления заканчивается, когда каждая из вновь полученных частей содержит по одному элементу.