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

Цель – сформировать формальное определение алгоритма в виде трех аналитических моделей, написать программную реализацию машины Тьюринга, распознающей язык L = { wcv│w, v ∈ {0, 1}* & │w│=2k & │v│=2n+1 & k!=n & k, n≥0}, построить график временной сложности. Результат – формальное определение алгоритмов на основе рекурсивных функций, машин Тьюринга и нормальных алгоритмов Маркова, программная реализация машины Тьюринга, распознающей язык L = { wcv│w, v∈{0, 1}* & │w│=2k & │v│=2n+1 & k!=n & k, n≥0}, график временной сложности машины Тьюринга, файловый вариант протокола работы машины Тьюринга.

На ленту подаётся слово сначала мы проверяем условие (k!=n) для этого мы по очереди передвигаем каретку из слова w,заменяя его на пометку, к слову v,также заменяя его. Если слова w полностью заменено, а слово v имеет символ 1/0 то мы двигаем каретку вправо, и если там пустой символ, значит условие ложно, мы стираем запись и ставим 0, иначе делаем обратную замену и переходим к условию (|w| = 2k && |v| = 2n+1). Здесь мы заменяем символы и стираем их попарно, если следующий символ “c” (для w) или пустой символ(для v), то ставим 0 слева или справа, что означает нечетность, иначе 1, если справа или слева “c” пустой символ. Верное условие будет, когда предфинальный вид слова обретает вид “1c0”, это будет означать, что слова w и v соответствуют условиям четности/нечестности. Далее на основании этих результатов, “c” будет равно либо 1,либо 0.

На вход подаётся слово, проверяем наличие символов 1/0/c, если их нет, то ставим 0, если символов c больше 1, то 0, иначе записываем на вторую ленту пошагово символы с первой до встречи символа “c”, после мы его стираем. Следующий шаг, проверяем условие (k!=n) одновременно сдвигаем каретки, если достигаем конца слова второй ленты, но не достигаем конца слова первой лент, то проверяем, стоит ли за ним символ, если да, то переходим к проверке слов на четность/нечетность, иначе стираем слова с обеих лент и ставим в первой ленте 0. Проверка на четность/нечетность аналогична одноленточной машине. После проверки, смотрим, если первая лента в результате выдаёт 0, а вторая 1, то стираем вторую, а в первой ставим 1, иначе стираем вторую и в первой ставим 1. Алгоритмы похожи, однако за счёт дополнительной памяти (второй ленты) двуленточная машина Тьюринга работает быстрее и требует меньше тактов для вычислений.

• Проект написан с применением Windows Forms
• При написании проекта было применено асинхронное программирование, позволяющее вести одновременное вычисление слова для ОМТ и ММТ
• Построения графика временной сложности
• Логгирование команд вычисления в файл

1. Клонируйте репозиторий.
2. Откройте файл решения в Visual Studio.
3. Постройте решение.
4. Запустите приложение.