Если вы начинающий программист и у Вас нет машины, то лучшее решение — машина Тьюринга (МТ)! Я в этом вам помогу, а еще Макконнел. Но и не только он один.
Первая моя статья на Хабре о машинах Тьюринга это про тяжелый грузовик [1]. А оно такое надо? Начинать лучше с чего‑то полегче. Этим и займемся. Хотя основа или, так сказать, базис по большому счету будет один. Но, ведь, между карьерным самосвалом и самой простой «инвалидкой» тоже есть много общего? И то и другое явно не самолет.
В монографиях Макконнела [2], Карпова [3] и еще много где устройство МТ расписано по винтикам, которых не так уж и много. Я, например, когда‑то начинал с книги А.Трахтенброта [4]. Также можно, не мудрствуя лукаво, запустить эмулятор МТ. Их в Инете найти не сложно. И сразу погонять, не вникая в «винтики». Но это для самых отвязных, то есть тех, кто не боится снести крышу.
Я предпочитаю среднее. Глубины теории для любителей. По мне гораздо лучше через «ручки». Для этого нужно иметь «конструктор», на котором можно не только тренироваться, но и реализовать любые фантазии.
Подобие конструктора можно найти у Карпова Ю.Г. Но это пара набросков на псевдокоде. Мы же возьмем конкретный язык и конкретную реализацию. А для совсем уж ленивых будет доступен код по ссылке на Git‑репозитарий.
Подобно Макконнелу я за «активный обучающий подход». Т.е. следую его заветам. Хотя следовал я им задолго до знакомства с его идеями. И это даже хорошо, так как не отвлекало. В результате я пошел даже немного дальше. Для анализа алгоритмов использовал не псевдокод, а другой вариант — формальную вычислительную модель и ее реализацию. Такой «математический псевдокод» позволяет делать анализ проще, глубже и точнее. По результатам написал статью во времена, когда журналы еще издавались [5].
Реализация «псевдокода» позволяет непосредственно ощутить алгоритм, делая процесс воистину активным. А поскольку модель универсальная, то реализовать на ней можно все что угодно. Вот и получился весьма активный и универсальный подход к изучению и анализу алгоритмов. А если анализ дополнить визуализацией, как завещал Роберт Седжвик [6], то картина становится более полной, объемной и наглядной.
Поскольку мы можем реализовать любую машину Тьюринга, которая, как известно, может все, то универсальность подхода не вызывает сомнений. А поскольку такая модель совершеннее любого псевдокода (в том числе псевдокода Макконнела), то будем иметь и более широкие возможности для изучения алгоритмов.
Не тяни уж, скажете вы, что это за модель? Это достаточно известная модель конечного автомата (КА). Прочтя указанные книги, вы, если даже не знали про нее, то уж точно будете знать о КА практически все. По крайней мере, на уровне конструкции, описания и принципов функционирования.
Текущая цель — машина Тьюринга. Ее код на С++ столь прост, что не будем его даже приводить. В рамках понятий ООП это базовый объект, содержащий ленту машины в форме текстовой строки и методы, реализующие действия МТ — перемещения головки, инициализацию ленты и остановку машины. Перемещение имитирует индекс, указывающий на текущий символ. Собственно он же будет и головкой машины.
Программы, имитирующие любую МТ, будут представлять собой автоматные объекты, использующие базовый объект в качестве родительского. Они будут содержать таблицу переходов конечного автомата и методы конкретизирующие процедуры чтения и изменения ленты. В сумме все это составляет реализацию того или иного конкретного алгоритма. Но это уже, следуя заветам Алана Тьюринга.
На рис. 1 приведен граф переходов МТ и отдельные ее конфигурации в процессе нахождения наибольшего общего делителя двух чисел (НОД), приведенный у Карпова Ю.Г.. На рис. 2. приведен граф конечного автомата. Как говорится, найдите пару отличий.
Листинг 1 демонстрирует код машины Тьюринга на С++. В нем реализованы даже две МТ, где вторая — реализация по книге Трахтенброта Б.А. В ней приведена табличная форма, находящая тот же НОД. Ее вид представлен в табл. 1. Комментируя в коде ту или иную таблицу переходов, мы получаем разные машины.
Листинг 1
#include "stdafx.h" #include "FTGrCmDiv.h" static LArc TBL_TGrCmDiv[] = { //===== программа МТ нахождения НОД (Greatest Common Divider) ============== //* // Ю.Г. Карпов Теория автоматов, - СПб.: Питер, 2003. - 208 с. // стр.194 LArc("s","s","x1", "y16"), LArc("s","s","x2", "y16"), LArc("s","p","x3", "y1"), LArc("s","r","x4", "y15"), LArc("p","p","x1", "y15"), LArc("p","p","x2", "y15"), LArc("p","s","x3", "y2"), LArc("p","q","x4", "y16"), LArc("q","q","x1", "y3y16"), LArc("q","q","x2", "y14y16"), LArc("q","s","x3", "y15"), LArc("q","s","x4", "y15"), LArc("r","r","x1", "y14y15"), LArc("r","r","x2", "y3y15"), LArc("r","s","x3", "y16"), LArc("r","!","x4", "y18"), LArc("!","!","--", "--"), //*/ /* // Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М.: Советское радио, 1974, - 200с. // рис. 14, стр 72 LArc("q1","q4","x4","y15"), LArc("q1","q2","x3","y1"), LArc("q1","q1","x1","y16"), LArc("q1","q1","x2","y16"), LArc("q2","q3","x4","y16"), LArc("q2","q1","x3","y2"), LArc("q2","q2","x1","y15"), LArc("q2","q2","x2","y15"), LArc("q3","q1","x4","y15"), LArc("q3","q1","x3","y15"), LArc("q3","q3","x1","y3y16"), LArc("q3","q3","x2","y4y16"), LArc("q4","q5","x4","y16"), LArc("q4","q1","x3","y16"), LArc("q4","q4","x1","y4y15"), LArc("q4","q4","x2","y3y15"), LArc("q5","q5","x4","--"), LArc("q5","q5","x3","--"), LArc("q5","q5","x1","--"), LArc("q5","q5","x2","--"), */ LArc() }; FTGrCmDiv::FTGrCmDiv(string strNam): FTuringMashine(strNam, TBL_TGrCmDiv) { strSrc = "#1111111111#"; strSaveTape = strTape = strSrc; nIndexHead = nHeadPosition = 4; } void FTGrCmDiv::FResetActions() { FTuringMashine::FResetActions(); nIndexHead = nHeadPosition = 4; strTape = strSaveTape; }; int FTGrCmDiv::x1() { return strTape[nIndexHead] == 'a'; } int FTGrCmDiv::x2() { return strTape[nIndexHead] == 'b'; } int FTGrCmDiv::x3() { return strTape[nIndexHead] == '1'; } int FTGrCmDiv::x4() { return strTape[nIndexHead] == '#'; } void FTGrCmDiv::y1() { strTape[nIndexHead] = 'a'; } void FTGrCmDiv::y2() { strTape[nIndexHead] = 'b'; } void FTGrCmDiv::y3() { strTape[nIndexHead] = '1'; } void FTGrCmDiv::y4() { strTape[nIndexHead] = '#'; } void FTGrCmDiv::y14() { WriteAnEmptyCharacter(); } void FTGrCmDiv::y15() { MoveToTheRight(); } void FTGrCmDiv::y16() { MoveToTheLeft(); } void FTGrCmDiv::y18() { Stop(); }
| q1 | q2 | q3 | q4 |
# | Rq4 | Lq3 | Rq1 | L! |
1 | aq2 | bq1 | Rq1 | Lq1 |
a | L | R | 1L | #R |
b | L | R | #L | 1R |
Табл 1. Программа для МТ
Таблица — лишь другая форма МТ. Ее столбцы пронумерованы знаками состояний, а строки — знаками внешнего алфавита. Каждая ячейка таблицы содержит тройку знаков, где первый — новый символ на ленте, второй — перемещение головки, третий — новое состояние машины. Элемент тройки опускается, если символ на ленте не меняется, головка остается на месте или не меняется текущее состояние машины. Такая таблица, называется, если следовать терминологии Трахтенброта Б.А., функциональной схемой машины.
Современной модели программирования, созданной во времена Дж. фон Неймана, тьма лет. Весьма привлекательная поначалу она морально устарела. В еще большей степени это высвечивает параллельное программирование. Она проста и эффективна с точки зрения аппаратной реализации, но все больше тормозит развитие программирования. Так, попытки ускорить процессоры уперлись не только в объективные физические проблемы, но и в проблемы моральной отсталости. Тьюринг изначально предложил более совершенную модель, которая в силу определенных предпочтений так и не пошла в жизнь.
На рис. 3 приведена реализация алгоритма нахождения НОД в рамках существующей модели программирования. Ее внешний вид в сравнении с функциональными схемами машин Тьюринга просто удручает. Теперь понятна нелюбовь программистов к блок‑схемам. Хотя именно они рекомендуются существующими нормативными документами. Но на практике это, как правило, просто листинги, поскольку создавать «монстры» из блок‑схем занятие не из легких.
Например, тот же Microsoft Visio серьезно помогает при создании блок‑схем, но утешения в этом мало. С другой стороны, создание автоматных графов при наличии адекватных методов их реализации формирует более комфортную и эффективную среду для всего комплекса этапов проектирования программного продукта.
Приведенные ниже гифки оживляют картинку заветов. Первая — Gif. 1 демонстрирует работу МТ в Qt. Вторая Gif 2 — это МТ в VSCode. Их коды на С++ фактически идентичны. Для машин Тьюринга совпадают один в один. Отличия проявляются на уровне интерфейсов приложений. На Qt это виджеты библиотеки Qt, а в VS Code — WEB‑страничка, подключенная по WiFi к микроконтроллеру типа ESP32. И если первый интерфейс полностью спроектирован автором, то второй создан ИИ DeepSeek. Совместное творчество с ним позволило добиться идентичности интерфейсов.
Обратите внимание на диалог Core Setting. С его помощью можно управлять «на ходу» работой автоматных процессов: изменять скорость их работы, останавливать/продолжать работу, переводить в пошаговый режим, перезапускать. Соответственно диалог МТ отражает текущее состояние машины, позицию головки, содержит кнопку перезапуска и остановки «машины».
Если признаться, то меня по‑прежнему больше привлекают заветы академика Глушкова В.М, практические идеи Майорова С.А. и Баранова С.И. Теория автоматов в изложении Мелихова А.Н. и Поспелова Д.А. Не забыть бы параллелизм в изложении Котова В.Е. и так далее и так далее
Выше я перечислил авторов наиболее близких мне по духу. Их «заветы» я впитал задолго до Макконнела. Но это отнюдь не умаляет значения Дж. Макконела, Марвина Минского, Дж. фон Неймана и, безусловно, Алана Тьюринга. А вспомним «программистские заветы» Н.Вирта и Э.Дейкстры? А когда‑то настольные для меня книги по структурному программированию Э.Йодана и надежности программного обеспечения Г.Майерса?
Жизнь промелькнула перед глазами, пока я перечислял авторов, заветам которых я следовал и следую до сих пор. К сожалению, не могу припомнить сравнимых с ними современников. Но это, может, моя вина и/или следствие того, что многие тенденции современного программирования мне совсем не по нутру. Особенно в «многопоточной реализации» и так называемой, тьфу‑тьфу, не к ночи будет упомянуто — конкурентности.
Кто тут и с кем конкурирует и конкурирует ли?
А чьим заветам следуете вы? Или не ведаете, что они есть, а весь этот «культур‑мультур» с заветами вам «по барабану»?
Времена, говорят, не выбирают, но их или впитывают или отвергают. Неужели вас не корежит вся эта истерия вокруг ИИ? Следуя известному анекдоту о доме нужно больше думать, о доме. Ну, или о «машинах» и, конечно, заветах.
Литература
Машина Тьюринга, как модель автоматных программ. https://habr.com/ru/articles/481998/
Дж.Макконнелл Анализ алгоритмов. Активный обучающий подход. 3-е дополненное издание. — М.: Техносфера, 2013. — 415 с.
Карпов Ю.Г. Теория автоматов. — СПб.: Питер, 2003. — 208 с.
Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М.: Советское радио, 1974, — 200с.
Любченко В.С. Параллельные сортировки: быстрее, проще... умнее. “Открытые системы”, № 5/2004, https://www.osp.ru/os/2004/05/184293
Роберт Седжвик. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. — К.: Издательство «ДиаСофт», 2001. — 688 с.
