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

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

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

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