Машина Тьюринга (МТ) не сферический конь в вакууме программистского бытия. Она не про «единички-нолики» и елозанье вдоль ленты, а про гимнастику мозгов для программистов. Продолжим тему МТ, начатую в [1]. Ее программирование увлекательная и, без сомнения, серьезная работа по созданию алгоритмов при миним миниморум средств на их реализацию Тем и привлекательна. Особенно на этапах обучения алгоритмическому мышлению.
Продолжим тему нахождения наибольшего общего делителя (НОД) двух чисел для МТ. Только теперь это будет обычное программирование. По счастью ли по совпадению нужный нам алгоритм приведен в книге Н.Вирта [2]. Его блок-схема (БС) приведена на рис. 1. Обычная и ни чем не примечательная БС и совсем простой алгоритм. Особенно в сравнении с рассмотренными для МТ. Привел он его, преследуя другие цели, но сейчас не это главное.
А теперь следите. Ни что не мешает эту БС преобразовать в эквивалентную и похожую на нее (см. рис. 2). Надеюсь, вы видите, что разница не очень большая. Иначе - меняйте профессию программиста на любую другую. Возможно, вы рождены, чтобы крутить гайки (кстати, востребованная и почетная профессия).
А теперь большего внимания. Превратим граф на рис.2 в граф переходов для машины Тьюринга или граф конечного автомата (КА). Он на рис. 3. Сравните его с графами на рис.1 и рис.2. Заметим, что метки w0, w1, w2 на рис. 2 это имена будущих состояний автомата и/или МТ. Их места и сам переход к автомату определены процедурой нахождения эквивалентного любой блок-схеме автомата, описанной Барановым С.И. [3].
Итак, мы перешли от блок-схемы к графу переходов машины Тьюринга или к конечному автомату. В данном случае термины МТ и КА по сути синонимы. В подобной машине/автомате мы не оперируем единичками и ноликами, и нет ленты. Эти мелочи воображение должно игнорировать.
Мы дополнили машину Тьюринга операциями языка программирования, ленту смоделировали памятью программы, а граф переходов МТ превратили в КА с входными и выходными сигналами и сопоставленными им функциями-предикатами (входы) и функциями-действиями (выходы). Ну чем не ловкость рук? И где тут мошенничество?! Преобразования столь просты, что не надо напрягаться, переходя от одной формы алгоритма к другой. Позже и это, поверьте, не понадобится.
Осталось запрограммировать «автоматную машину» на языке С++. Ее код приведен в листинге 1.
Листинг 1
class FGrCmDivWirth: public FTuringMashine { public: void virtual FResetActions(); FGrCmDivWirth(string strNam); int x{4}; int y{6}; int NOD{0}; protected: int x1(); int x2(); void y1(); void y2(); void y3(); void y4(); void y5(); void y6(); int a{0}; int b{0}; char buf[20]; }; // Вирт Н. Систематическое программирование. Введение. Пер с англ. – М.:Мир, 1977. – 184 с. // Алгоритм нахождение НОД // стр. 40 (5.18) // 20/08/2026 LArc TBL_GrCmDivWirth[] = { LArc("w0","w1","--","y1y5"), LArc("w1","w1","x1x2","y3y5"), LArc("w1","w1","x1^x2","y2y5"), LArc("w1","w2","^x1","y4y5"), LArc("w2","w2","^--","y6"), LArc() }; FGrCmDivWirth::FGrCmDivWirth(string strNam): FTuringMashine(strNam, TBL_GrCmDivWirth) { sprintf(buf, "%d,%d", x, y); strSrc = buf; strSrc = buf; strSaveTape = strTape = strSrc; } void FGrCmDivWirth::FResetActions() { strTape = strSaveTape; FTuringMashine::FResetActions(); }; // ПРЕДИКАТЫ int FGrCmDivWirth::x1() { return a != b; } int FGrCmDivWirth::x2() { return a > b; } // ДЕЙСТВИЯ void FGrCmDivWirth::y1() { vector<string> strList = splitString(strTape, ","); x = stod(strList[0]); y = stod(strList[1]); a = x; b = y; } void FGrCmDivWirth::y2() { b = b - a; } void FGrCmDivWirth::y3() { a = a - b; } void FGrCmDivWirth::y4() { NOD = a; } void FGrCmDivWirth::y5() { sprintf(buf, "%d,%d", a, b); strTape = buf; } void FGrCmDivWirth::y6() { sprintf(buf, "НОД=%d", NOD); strTape = buf; Stop(); }
Можно было бы в качестве родительского объекта взять автоматный класс LFsaAppl библиотеки VCPa, которому в свойства добавить «ленту». Но мы взяли класс FTuringMashine, описанный в предыдущей статье [1], чтобы воспользоваться диалогом для отображения процесса нахождения НОД. Результат демонстрирует gif1 (см. диалог GrCmDivWirth).
Когда еще не было современного ИИ, программисты, желая создавать надежные и понятные программы, стремились к использованию автоматной модели. Им, как минимум, ее убедительно рекомендовали. Называлось это, порой, по-другому, например, метод преобразования неструктурированных программ Ашкрофта-Манны, таблицы решений и т.д и т.п.[4]. Они больше внимания уделяли созданию качественных и надежных программ, не надеясь на методы типа model checking, которые сложны и на практике, порой, неприменимы (см. свежую статью на эту тему на Хабре – сложно, путано и без ответов на простые вопросы [5]).
Давайте сравним новый алгоритм НОД для расширенной МТ с его аналогом на чистой МТ (на gif 3 они представлены оба). Например, прогнав алгоритмы в пошаговом режиме. Так, при числе состояний у МТ (берем программу из книги Трахтенброта Б.А. в листинге 1 [1]) – пять (q1, q2, q3, q4, q5), а у Н.Вирта – 3 мы получаем достижения результата в тактах: для МТ – без малого 100, для КА – 5 (следите за мышкой на gif 1).
Сложность алгоритмов в рамках МТ/КА можно оценить по числу состояний и переходов, а скорость по числу затраченных тактов на достижение результата. Просто, наглядно, точно! Чтобы получить подобные оценки на «обычной машине» надо очень постараться. А у нас - из коробки.
Разница между блок-схемным программированием и тьюринговым образно сравнима с различием между обычным передвижением и с ходьбой на костылях. Удивляет, что многие этого не понимают и упорно цепляются за «костыли». Особенно в многопоточном программировании. Видимо, перестали читать книги и статьи, где дана объективная оценка многопоточности и приведено множество аргументов в пользу использования тех же автоматов.
Сравним подходы, например, только на уровне управления процессами. На видео, используя диалог CoreSetting, можно:
1) перезапускать процессы – кнопка Restart VCPa,
2) останавливать/запускать процессы – StopAll Tasks,
3) переводить систему в пошаговый режим – флаг step-by-step
4) выполнять один шаг – кнопка step-by-step,
5) управлять скоростью работы процессов и если необходимо его подправлять - два поля Delta Time.
Все эти возможности создает автоматная, а по ее истокам – модель вычислений на базе МТ. При этом на уровне ядра VCPa это уже не одна машина Тьюринга, а их параллельное множество (см. на работу процессов на gif 3).
И вы все еще будете настаивать, что машина Тьюринга «интересна сама по себе» (см. обсуждение [1])?! «Тогда мы спешим к вам!»
Литература
1. По заветам Макконнела. https://habr.com/ru/articles/1072292/
2. Вирт Н. Систематическое программирование. Введение. Пер с англ. – М.:Мир, 1977. – 184 с.
3. Баранов С.И. Синтез микропрограммных автоматов. -Л.: Энергия, 1979. -232с.
4. Йодан Э. Структурное проектирование и конструирование программ. М.: Мир,1979 - 415с.
5. 5ⁿ → 4n+1: сколько на самом деле дают редукции в explicit‑state model checking. https://habr.com/ru/articles/1072376/