Машина Тьюринга, как модель автоматных программ


1. Введение


Программирование нуждается в новых универсальных алгоритмических моделях, а аппаратные средства реализуют алгоритмы не только в другой форме, но и на базе другой алгоритмической модели — автоматной. Заимствование технологии из сферы разработки аппаратных средств ключевая идея автоматного программирования. Однако синтез цифровых устройств отличается от программирования. Но, заимствуя модель, с одной стороны, ее не желательно существенно изменять, а, с другой стороны, нельзя не учитывать уже существующую теорию и практику программирования.

Далее мы рассмотрим SWITCH-технологию проектирования автоматных программ, в которой с подобными процессами сталкиваешься сплошь и рядом. С одной стороны, она так изменила модель конечного автомата, что фактически вывела ее за рамки теории автоматов. А, с другой стороны, вводит в программирование понятия, которые с трудом воспринимаются программистами, а, порой, просто являются лишними, т.к. существуют более привычные аналоги из теории программ и практики программирования.

За основу обсуждения проблем автоматного программирования возьмем недавнюю лекцию Шалыто А.А. [1] и его «программные» статьи к определению парадигмы автоматного программирования [2, 3].

1. Автоматизированные объекты, схемы программ

В лекции достижением автоматного программирования объявлено введение в него понятия автоматизированных объектов управления, заимствованное из теории автоматического управления (ТАУ). Но, напомним, что в ТАУ рассматривают не столько объекты, а системы, среди которых выделяют следующие [4]:

image

Исходя из этого, правильнее было бы говорить о системах автоматического управления (САУ). Теперь посмотрим на типовую функциональную схему САУ, показанную рис. 1. Если ленту машины Тьюринга считать объектом управления, то исполнительными устройствами (ИсУ) будут элементы МТ, реализующие изменение содержимого ленты и передвигающие головку, а измерительными устройствами (ИзУ) — элементы, читающие информацию с ленты.

image
Рис.1. Функциональная схема САУ

Но зачем обращаться к ТАУ, если есть более близкая к программированию практика проектирования вычислительных систем, в которой операционные устройства (ОУ), к которым, безусловно, относится и МТ, рассматриваются в виде комбинации операционного (ОА) и управляющего (УА) автоматов. И это ближе к тому, к чему мы в конечном итоге стремимся — обоснованию мощности автоматного программирования. На рис. 2 представлен скрин текста из монографии Майорова С.А., Новикова Г.И. Структура электронных вычислительных машин [5], в которой вопросы проектирования ОУ рассмотрены весьма детально.

image
Рис.2. Концепция управляющего и операционного автоматов

Но, если сравнивать теорию проектирования ЭВМ и теорию программ, то между ними прослеживается явная структурная аналогия. В теории программирования модель любой программы на структурном уровне можно представить, как схему программы S = (M, A, C), где M – множество элементов памяти, A – множество операторов, C – управление [10]. Следуя этому подходу, любую программу машины Тьюринга также можно определить как схему программы, в которой множество M представлено ячейками ленты, множество операторов – действиями МТ, связанными 1) с анализом ячеек, 2) изменением символов в ячейках ленты и 3) перемещением головки.

Таким образом понятие схемы программы полностью аналогично рассмотренной концепции операционного и управляющего автоматов, где моделью УА является модель рассматриваемого далее структурного конечного автомата (СКА), а ОА «является структурой для выполнения действий над информацией». При этом ОА включает элементы хранения данных (выше – это память) и блоки для обработки информации, реализующих вычисление логических условий и реализацию тех или иных действий (выше – множество операторов).

Из сказанного можно понять, что лента лишь условно может считаться объектом управления для МТ. Хотя бы потому, что устройство управления машины Тьюринга не имеет к ней прямого доступа, т.к. все операции с ячейками реализуют опосредован-но блоки ОА. Кроме того, как представляется, не очень привычно или, если не сказать, странно считать целью управления программы, как системы управления, объект, представляющий собой память (ленту).
Таким образом, для формального определения машины Тьюринга, а в ее контексте места для модели конечного автомата, достаточно понятий теории программ. Теперь, в отличие от весьма расплывчатого определения автоматных программ, данного в рамках SWITCH-технологии, можно сказать, что автоматной программой считается программа, имеющая управление в форме модели конечного автомата.

Какая при этом будет сама программа – с простым или сложным поведением, какова ее «разновидность» – с логическим управлением, «с явным выделением состояний» и т.д. и т.п. не имеет абсолютно значения. Главное – вид управления. Остальные же элементы программы могут определяться в широких пределах – от простейших, как, например, у машины Тьюринга, до самых сложных – любых форм операторов, функций и структур данных языков программирования – ассемблера, языка высокого уровня и т.п.

Можно также вспомнить, что машину Тьюринга уже давно принято считать авто-матом [6] или уж, в крайнем случае, его простым расширением [7]. Но необходимо понимать, что это за автомат, что это за расширение, и эквивалентны ли они моделям классических конечных автоматов. Попробуем это как раз и уточнить.

2. Тьюрингово программирование в среде автоматного программирования

На рис. 3 показан автомат для МТ функции инкремента из монографии [8]. По форме это явно не программа для МТ, но уже и не классический конечный автомат. На рис. 4 приведен граф классического структурного конечного автомата (СКА) и его реализация в среде ВКПа (среда визуально-компонентного автоматного программирования на языке С++ в рамках библиотеки Qt и среды Qt Creator), реализующего тот же самый алгоритм блока управления (БУ) МТ.

image
Рис.3. Увеличение числа на единицу с помощью машины Тьюринга

image
Рис.4 Модель программы инкремента для МТ в форме СКА

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

Данный СКА имеет то же множество состояний, что и автомат на рис.3. При этом кроме собственно автоматного отображения, представленного СКА, он реализует еще два отображения – отображение множества предикатов (x1, …, xM) на множество одноименных входных каналов автомата, и множество выходных каналов автомата на множество одноименных действий – y1, …, yN. Например, предикат x3 вернет значение true (значение 1 для одноименного входного сигнала), если в текущей ячейке будет символ 1, а действие y4, которое будет запущено, когда одноименный выходной сигнал автомата примет значение 1, будет соответствовать перемещение головки влево (L) и т.д. и т.п.

Обратим внимание, что СКА не управляет напрямую лентой, а реализует [дополнительные] отображения, связывая сигналы автомата с функциями, определяющими множество операций машины Тьюринга. Это еще раз убеждает, что нет необходимости вводить понятие автоматизированного объекта управления в ситуации, когда достаточно «старомодного», но математически строго понятия отображение.

Сравнивая автоматы на рис. 3 и рис. 4, можно видеть, что СКА не использует команду «*» (см. рис. 1). В подобной ситуации ему достаточно не выдавать сигнал, связанный с данной командой. Кроме того, два и более сигналов (как входных, так и выходных) на одном переходе параллельны. Поэтому, когда возникает конфликт доступа к общим объектам (например, необходимо изменить ячейку и переместить головку) используется соглашение: действия на одном переходе исполняются последовательно в порядке следования их номеров, т.е. действие с большим номером выполняется после действия с меньшим номером. Это соглашение не распространяется на предикаты, т.к. они не изменяют ленту. Так мы делаем автомат более компактным и наглядным (не на-до вводить промежуточные состояния).

В процессе тестирования программы инкремента были выявлены ситуации, когда в процессе работы МТ могут возникнуть проблемы. Во-первых, реальная лента не бесконечна и выход за ее пределы может вызвать «крах» программы. Во-вторых, нужно обязательно указывать начальное положение головки. Без этого, если, например, число находится в произвольном месте ленты, а начальное состояние головки слева от числа и напротив пробела, то головка сразу начнет движение влево. Далее она может выйти за границы ленты, вызвав «крах» программы, или, переместившись, на шаг влево запишет в ячейку 1 и, зависнув, завершит «успешно» работу. Или, если число содержит во всех разрядах 1 и записано с начала ленты, то заключительная попытка переноса 1 в старший разряд вызовет тот же самый «крах».

2.1. Объектная реализация МТ на языке С++

Рассмотрим объектную программную реализацию машины Тьюринга на языке C++ в среде ВКПа, реализующую любую программу для МТ, в том числе и программу вычисления инкремента.

С этой целью создан базовый класс, представляющий любую машину Тьюринга, который и наследуют программные объекты, реализующие ту или иную программу МТ. Данный базовый представлен на листинге 1, а программа, реализующая задачу инкремента, на листинге 2.

Листинг 1. Программная реализация базового класса МТ

#include "lfsaappl.h"
class FTuringMashine : public LFsaAppl
{
public:
    FTuringMashine(string strNam, CVarFsaLibrary *pCVFL, LArc* pTBL);
protected:
    int x15(); int x16();
    void y14(); void y15(); void y16(); void y17();
    QString strSrc;             // исходное состояние ленты
    QString strTape;            // лента
    QString strHead;            // головка
    int nIndexHead{0};          // индекс головки
    bool bRestart{false};       // признак рестарта
    int nHeadPosition{0};       // текущее положение головки
};

#include "stdafx.h"
#include "FTuringMashine.h"
FTuringMashine::FTuringMashine(string strNam, CVarFsaLibrary *pCVFL, LArc* pTBL):
    LFsaAppl(pTBL, strNam, nullptr, pCVFL)
{
    nHeadPosition = 0;
    strHead = "________________________________________";
    nIndexHead = nHeadPosition;
}
//==============================================================
// ПРЕДИКАТЫ
// пустой символ?
int FTuringMashine::x15() { return strTape[nIndexHead] == '#'; }
// рестарт?
int FTuringMashine::x16() { return bRestart; }
//==============================================================
// ДЕЙСТВИЯ
// записать пустой символ на ленту
void FTuringMashine::y14() { strTape[nIndexHead] = '#'; }
// головка сместить вправо (нарастить индекс)
void FTuringMashine::y15() { nIndexHead++; }
// головка сместить влево (уменьшить индекс)
void FTuringMashine::y16() { nIndexHead--; }
// установить в исходное состояние
void FTuringMashine::y17() {
    strTape = strSrc; nIndexHead = 0;
    bRestart = false;
    nIndexHead = nHeadPosition;
}

Листинг 2. Программа инкремента для машины Тьюринга

#include "FTuringMashine.h"
class FTIncrement : public FTuringMashine
{
public:
    LFsaAppl* Create(CVarFSA *pCVF) { 
	Q_UNUSED(pCVF)return new FTIncrement(nameFsa, pCVarFsaLibrary); 
    }
    FTIncrement(string strNam, CVarFsaLibrary *pCVFL);
protected:
    int x1(); int x2(); int x3();
    void y1(); void y2();
};

#include "FTIncrement.h"
static LArc TBL_TIncrement[] = {
// см. Н. Поликарпова, А. Шалыто Автоматное программирование, 2-е издание, 2011 г.,
// стр.17-18
//===== функция переходов МТ (см. Ю.Г. Карпов Теория автоматов, - СПб.: Питер, 2003. - 208 с.) ==============
//     f(Пп,^` `) = (Пп,`*`,R)
//     f(Пп,` `)  = (Оп,` `,L)
//     f(Оп,`1`)  = (Оп,`0`,L)
//     f(Оп,` `)  = (К,`1`,R)
//     f(Оп,`0`)  = (К,`1`,R)
//=========================================
	LArc("Прямой проход",   "Прямой проход",   "^x1", "y15"),    	
	LArc("Прямой проход",	 "Обратный проход", "x1",  "y16"),    	
	LArc("Обратный проход", "Обратный проход", "x2",  "y2y16"),    	
	LArc("Обратный проход", "Конец",           "x1",  "y1"),
	LArc("Обратный проход", "Конец",           "x3",  "y1"),
	LArc("Конец",           "Прямой проход",   "x16", "y17"),
	LArc()
};

FTIncrement::FTIncrement(string strNam, CVarFsaLibrary *pCVFL):
    FTuringMashine(strNam, pCVFL, TBL_TIncrement)
{
    strSrc = "11011110011111 ";
    strTape = strSrc;
}
// ПРЕДИКАТЫ
int FTIncrement::x1() { return strTape[nIndexHead] == ' '; }
int FTIncrement::x2() { return strTape[nIndexHead] == '1'; }
int FTIncrement::x3() { return strTape[nIndexHead] == '0'; }
// ДЕЙСТВИЯ
void FTIncrement::y1() { strTape[nIndexHead] = '1'; }
void FTIncrement::y2() { strTape[nIndexHead] = '0'; }

2.2. Примеры программ для МТ с реализацией на С++

Рассмотрим пример программы для МТ, которая «выступает как акцептор языка, т.е. она может распознавать язык» из [9]. Ее функция переходов представлена на рис. 5, а эквивалентный ей автомат в форме СКА на рис. 6.

?(1, a) = (2, x, R)		?(1, y) = (4, y, R)
?(2, a) = (2, a, R)		?(2, y) = (2, y, R)
?(2, b) = (3, y, L)		?(3, y) = (3, y, L)
?(3, a) = (3, a, R)		?(3, x) = (1, x, R)
?(4, y) = (4, a, R)		?(4, #) = (F, #, L)

Рис. 5. Функция переходов машины Тьюринга, распознающая язык {anbn: n?1}

image
Рис. 6. Граф СКА машины Тьюринга, распознающей язык {anbn: n?1}

Блок управления МТ в форме СКА имеет 6 входных и 7 выходных каналов. Про-грамма акцептора включает также соответствующее им число предикатов и действий, которые представлены на рисунке справа от графа автомата. Реализация программы на С++ в среде ВКПа представлена на листинге 3.

Листинг 3. Программа для машины Тьюринга, распознающей язык {anbn: n?1}

#include "FTuringMashine.h"

extern LArc TBL_TAcceptor[];
class FTAcceptor : public FTuringMashine
{
public:
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTAcceptor(nameFsa, pCVarFsaLibrary); }
    FTAcceptor(string strNam, CVarFsaLibrary *pCVFL, LArc* pTB = TBL_TAcceptor);
protected:
    int x1(); int x2(); int x3(); int x4();
    void y1(); void y2(); void y3(); void y18();
    int nState{1};
friend class CDlgTAcceptor;
};

#include "stdafx.h"
#include "FTAcceptor.h"

LArc TBL_TAcceptor[] = {
// см. Дж.Maкконнелла Анализ алгоритмов. Активный обучающий подход. 2013 г.,
// Машина Тьюринга как акцептор языка, стр.304
//===== функция переходов МТ ==============
//     f(1,a) = (2,x,R)   f(1,y) = (4,y,R)
//     f(2,a) = (2,x,R)   f(2,y) = (2,y,R)
//     f(2,b) = (2,x,R)   f(3,y) = (3,y,L)
//     f(3,a) = (3,a,R)   f(3,x) = (1,x,R)
//     f(4,y) = (4,a,R)   f(4,#) = (F,#,L)
//=========================================
    LArc("1",		"2","x1",	"y1y15"),	// 1,a,2,x,R
    LArc("1",		"4","x3",	"y15"),		// 1,y,4,R
    LArc("2",		"2","x1",	"y15"),		// 2,a,2,R
    LArc("2",		"3","x2",	"y2y16"),	// 2,b,3,y,L
    LArc("2",		"2","x3",	"y15"),		// 2,y,2,R
    LArc("3",		"3","x1",	"y16"),		// 3,a,3,L
    LArc("3",		"3","x3",	"y16"),		// 3,y,3,L
    LArc("3",		"1","x4",	"y15"),		// 3,x,1,R
    LArc("4",		"4","x3",	"y2y15"),	// 4,y,4,a,R
    LArc("4",		"F","x15",	"-"),		// 4,#,F,-,-
    LArc("F",		"1","x16",	"y17"),     //
    LArc("1",		"1","x16",	"y17"),     //
    LArc("2",		"1","x16",	"y17"),     //
    LArc("3",		"1","x16",	"y17"),     //
    LArc("4",		"1","x16",	"y17"),     //
//    LArc("1",		"1","--",	"y18"),	    //
    LArc()
};

FTAcceptor::FTAcceptor(string strNam, CVarFsaLibrary *pCVFL, LArc* pTB):
    FTuringMashine(strNam, pCVFL, pTB)
{
    strSrc = "aaaaaaaaaabbbbbbbbbb#";
    strTape = strSrc;
}

int FTAcceptor::x1() { return strTape[nIndexHead] == 'a'; }
int FTAcceptor::x2() { return strTape[nIndexHead] == 'b'; }
int FTAcceptor::x3() { return strTape[nIndexHead] == 'y'; }
int FTAcceptor::x4() { return strTape[nIndexHead] == 'x'; }

void FTAcceptor::y1() { strTape[nIndexHead] = 'x'; }
void FTAcceptor::y2() { strTape[nIndexHead] = 'y'; }
void FTAcceptor::y3() { strTape[nIndexHead] = 'a'; }
void FTAcceptor::y18() {
    switch(nState) {
    case 1:
        if (x1()) { nState = 2; y1(); y5(); break; }
        if (x3()) { nState = 4; y5();  break; }
        break;
    case 2:
        if (x1()) { nState = 2; y5(); break; }
        if (x2()) { nState = 3; y2();y6(); break; }
        if (x3()) { nState = 2; y5(); break; }
        break;
    case 3:
        if (x1()) { nState = 3; y6(); break; }
        if (x3()) { nState = 3; y6(); break; }
        if (x4()) { nState = 1; y5(); break; }
        break;
    case 4:
        if (x3()) { nState = 4; y2(); y5(); break; }
        if (x5()) { nState = 5; break; }
        break;
    case 5:
        if (x6()) { y7(); nState = 1; break; }
        break;
    }
}

На листинге 3 действие y18 представляет вариант программы для МТ в соответствии с подходом SWITCH-технологии. В рамках реализации автоматного программирования среды ВКПа в этом случае вместо автомата на рис. 6 необходимо будет реализовать автомат с одним состоянием, который выдает в цикле сигнал y18. Ему соответствует закомментированная строка таблицы переходов на листинге 3. Для работы автомата по типу SWICH необходимо снять комментарий с данной строки, а остальные строки закомментировать.

Рассмотрим еще один пример программы для машины Тьюринга из [7], где МТ определяется, как «весьма простое расширение модели конечного автомата». В этом случае программа для машины Тьюринга представляет собой конечный список пятерок частично-определенной функции переходов и выходов ?: S?X?S?X?Г.

Программа для МТ, находящая наибольший общий делитель (НОД) двух чисел, показана на рис. 7. Эквивалентный ей граф СКА представлен на рис. 8. Заметим, что и здесь не используются команда перезаписи символов. Реализация на С++ представлен листингом 4.

image
Рис. 7. Граф переходов машины Тьюринга, вычисляющей НОД двух чисел, и несколько ее конфигураций при обработке пары чисел <4, 6>

image
Рис. 8. Граф СКА, эквивалентный графу на рис. 7

Листинг 4. Программа для машины Тьюринга нахождения НОД двух чисел

#include "FTuringMashine.h"

class FTGrCmDiv: public FTuringMashine
{
public:
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTGrCmDiv(nameFsa, pCVarFsaLibrary); }
    FTGrCmDiv(string strNam, CVarFsaLibrary *pCVFL);
protected:
    int x1(); int x2(); int x3(); int x4();
    void y1(); void y2(); void y3(); void y17();
};

#include "FTGrCmDiv.h"
static LArc TBL_TGrCmDiv[] = {
//===== программа МТ нахождения НОД (Greatest Common Divider) ==============
// см. Ю.Г. Карпов Теория автоматов, - СПб.: Питер, 2003. - 208 с.
// стр.194
// см. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М.: Советское радио, 1974, - 200с.
// стр.76, 84-87
    LArc("s","s","x1",	"y16"),		//
    LArc("s","s","x2",	"y16"),		//
    LArc("s","p","x3",	"y1"),		//
    LArc("s","r","x15",	"y15"),		//
    LArc("p","p","x1",	"y15"),		//
    LArc("p","p","x2",	"y15"),		//
    LArc("p","s","x3",	"y2"),		//
    LArc("p","q","x15",	"y16"),		//
    LArc("q","q","x1",	"y3y16"),	//
    LArc("q","q","x2",	"y14y16"),	//
    LArc("q","s","x3",	"y15"),		//
    LArc("q","s","x15",	"y15"),		//
    LArc("r","r","x1",	"y14y15"),	//
    LArc("r","r","x2",	"y3y15"),	//
    LArc("r","s","x3",	"y16"),		//
    LArc("r","!","x15",	"--"),		//
    LArc("!","s","x16",	"y17"),		//
    LArc()
};

FTGrCmDiv::FTGrCmDiv(string strNam, CVarFsaLibrary *pCVFL):
    FTuringMashine(strNam, pCVFL, TBL_TGrCmDiv)
{
    nHeadPosition = 4;
    strSrc = "#1111111111## ";
    strTape = strSrc;
    nIndexHead = nHeadPosition;
}

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::y17() {
    strTape = strSrc; nIndexHead = 4;
    bRestart = false;
    nIndexHead = nHeadPosition;
}

В заключение еще одна программа для МТ от разработчиков SWITH-технологии, рассмотренная в статье [11], где приведена задача распознавание скобок в двух варианта. Один в форме автомата Мили, второй – смешанный автомат (соответственно на рис. 9 и рис. 11). Соответствующие им структурные автоматы приведены на рис. 10 и рис. 12. Реализацию программы на С++ демонстрирует листинг 5.

image
Рис. 9. Распознавание скобок произвольной глубины. Граф переходов Мили

image
Рис. 10. Распознавание скобок произвольной глубины. Граф СКА Мили

image
Рис. 11. Распознавание скобок произвольной глубины. Граф переходов смешанного автомата

image
Рис. 12. Распознавание скобок произвольной глубины. Граф СКА переходов сме-шанного автомата

Листинг 5. Программа для машины Тьюринга распознавания вложенности скобок

#include "../FTuringMashine.h"

class FTListing2 : public FTuringMashine
{
public:
    void MooreAction();
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTListing2(nameFsa, pCVarFsaLibrary); }
    FTListing2(string strNam, CVarFsaLibrary *pCVFL);
protected:
    int x1(); int x2(); int x3(); int x4();
    void y1(); void y2(); void y3(); void y4(); void y5();
    int i{0};
};

#include "FTListing2.h"

static LArc TBL_TListing2[] = {
// см. Туккель Н.И., Шалыто А.А. От Тьюрингова программирования к автоматному, МирПК, №2, С.144-149
//===== функция переходов МТ (см. Ю.Г. Карпов Теория автоматов, - СПб.: Питер, 2003. - 208 с.) ==============
//     f(Пп,^` `) = (Пп,`*`,R)
//     f(Пп,` `)  = (Оп,` `,L)
//     f(Оп,`1`)  = (Оп,`0`,L)
//     f(Оп,` `)  = (К,`1`,R)
//     f(Оп,`0`)  = (К,`1`,R)
//=========================================
/*
// Мили
    LArc("0",		"1",    "x2",	"y2"),	// '(';движение вправо
    LArc("0",		"3",    "x3",	"--"),	// '(';
    LArc("1",		"1",  "x2",     "y2"),	// '(';движение вправо
    LArc("1",		"1",  "x3",     "y3"),	// ')';движение влево
    LArc("1",		"3",  "^x1x4",	"--"),	// i!=0;' '; Отвергнуть
    LArc("1",		"3",  "x1x3",	"--"),	// i==0;')'; Отвергнуть
    LArc("1",		"2",  "x1x4",	"--"),	// i==0;' '; Допустить
    LArc("2",		"0",  "x16",    "y17"),	// bRestart; перезапуск
    LArc("3",		"0",  "x16",    "y17"),	// bRestart; перезапуск
*/
//*
// Смешанный автомат Мили-Мура
    LArc("0",		"1",  "x2",     "y2"),		// '('
    LArc("0",		"3",  "x3",     "--"),		// ')'
    LArc("1",		"1",  "x2",     "y2"),		//'(';движение вправо
    LArc("1",		"1",  "x3",     "y3"),		// ')';движение влево
    LArc("1",		"2",  "x1x4",	"--"),      // i==0;' ';
    LArc("1",		"3",  "^x1x4",	"--"),		// i!=0;' ';
    LArc("1",		"3",  "x1x3",	"--"),		// i==0;')';
    LArc("2",		"0",  "x16",    "y17"),     // bRestart; перезапуск
    LArc("3",		"0",  "x16",    "y17"),     // bRestart; перезапуск
//*/
    LArc()
};

FTListing2::FTListing2(string strNam, CVarFsaLibrary *pCVFL):
    FTuringMashine(strNam, pCVFL, TBL_TListing2)
{
    strSrc = "(()()) ";
    strTape = strSrc;
}
// ПРЕДИКАТЫ
int FTListing2::x1() { return i == 0; }
int FTListing2::x2() { return strTape[nIndexHead] == '('; }     //
int FTListing2::x3() { return strTape[nIndexHead] == ')'; }     //
int FTListing2::x4() { return strTape[nIndexHead] == ' '; }     //
// ДЕЙСТВИЯ
void FTListing2::y1() { i = 0; }                    // z1_0
void FTListing2::y2() { i++; }                      // z1_1
void FTListing2::y3() { i--; }                      // z1_2
void FTListing2::y4() { strTape = "допустить"; }    // z2_0
void FTListing2::y5() { strTape = "отвергнуть"; }   // z2_1

void FTListing2::MooreAction()
{
    string strState = FGetState();
    if (strState=="0")	{ y1(); }           // сброс счетчика
    else if (strState=="1")	{ y15(); }      // сдвиг головки влево
    else if (strState=="2")	{ y4(); }       // Допустить
    else if (strState=="3")	{ y5(); }       // Отвергнуть
}

Поскольку автомат на рис. 12 отказался работать, то было решено перейти к автомату на рис. 9. Эквивалентный ему автомат в форме СКА, показан на рис. 10. Правда, формально это тоже смешанный автомат, у которого от первой реализации (рис. 12) был оставлен сигнал при состоянии «0» и сигнал y15 при состоянии «1». Первый необходим при начальной установке, а сигнал y15 реализует смещение головки вправо в целях чтения очередного символа ленты. В остальном СКА соответствует автомату Мили на рис. 9.

После того, как автомат на рис. 10 был успешно протестирован, вернулись к автомату на рис. 11. И стало понятно, что у него лишним является сигнал z1_1 при состоянии «1»(у автомата на рис. 12 это сигнал y2). Проблема в том, что он, обнаружив «левую скобку», наращивает счетчик на две единица, а при обнаружении «левой скобки» не изменяет его совсем. Так, при обнаружении «левой скобки» он вызывается дважды – один раз на петле,, помеченной x2/y2, а второй раз при входе в состояние. А при обнаружении «правой скобки» счетчик сначала на петле уменьшается, а затем при входе в состояние увеличивается.

Причина такой работы управления МТ, в неверной трактовке авторами функционирования автомата типа Мура. Видимо, они полагают, что сигнал при состоянии у автомата Мура исполняется только при входе в это состояние (см. переход из состояния «0» в «1»), а на самом деле он выдается всякий раз при входе в это состояние. В том числе и при переходе по петле. Таким образом, мы имеет дело не с ошибкой (кто не ошибался?), а с более серьезной проблемой — неверной трактовкой в рамках SWITH-технологии функционирования автоматов типа Мура. Тестирование эквивалентной модели это и показало.

3. Заключение

Подводя итог, можно сказать, что нет формальных отличий тьюрингового программирования от автоматного, т.к. машина Тьюринга – это абстрактная модель автоматных программ. Просто в последнем случае используется более широкий набор операторов и структур данных (памяти). Теперь можно уверенно ответить и на вопрос, чем отличается машина Поста, как модель обычных программ, от машины Тьюринга — модели автоматных программ. Моделью управления и лишь только ею, т.к. остальное – память и операторы могут быть одними и теми же.
Следовательно, обычное программирование отличается от программирования автоматного только одним – моделью управления. Таким образом, пока для реализации автоматов используются обычные операторы управления типа switch и им подобные нельзя, строго говоря, такое программирование считать автоматным. Это может быть имитация автоматов с утратой их определенных свойств и не более того.

Итак, давая определение понятий автоматной программы и автоматного программирования, говорить надо не об «автоматизированных объектах управления», а о программах и только программах, имеющих управление в форме классического конечного автомата.
И еще интересный факт, на который хотелось бы обратить внимание. В начале 2000-х годов, авторы озвучили свое понимание автоматного программирования на широкую аудиторию. Их статьи по поводу абстрактных машин были напечатаны в журнале «Мир ПК» №2 за 2002 г. [11, 12, 13]. Можно утверждать, что годы на убеждения сторон не повлияли. Хотя, возможно, это отражает только степень их уверенности в выбранных решениях.

Например, в «новую лекцию по автоматному программированию» Шалыто А.А. по сравнению с предыдущей «лекцией со слайдами» (десятилетней давности) добавлено лишь видео примера на базе «автоматного пакета» Stateflow. Казалось бы, это подтверждает правоту идей Шалыто А.А., т.к. то, что не удалось реализовать в рамках UniMod (проект, похоже, «заморожен»), воплотили разработчики Stateflow. И, наверное, не так уж важно кто это сделал…

Однако, на момент публикации упомянутых статей авторам SWITCH-технологии уже была известна критика в ее адрес. Это не было тайной, т.к. с ней можно было ознакомиться на сайте SoftCraft [14]. На нем же были созданы разделы, посвященные автоматному программированию вообще и SWITH-технологии и КА-технологии в частности. Позиции авторов обсуждались на форуме сайта (он был на тот момент открыт). Но все так и остались при своем мнении.

Итоги на текущий момент таковы. Критика, высказанная в отношении SWITH-технологии когда-то давно, актуальна и на текущий момент. Она же относится и к пакету Stateflow. В SWITH-технологии как не было, так и нет четкого определения автоматного программирования, не изменился подход к реализации автоматов, сама модель не является классической, нет модели параллельных вычислений и т.д. и т.п. Без устранения этих проблем подобное автоматное программирование в лучшем случае претендует на достаточно ограниченную роль.

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

Список литературы
1. Шалыто А. А. Новая лекция по автоматному программированию. 2019, [Электронный ресурс], Режим доступа: www.youtube.com/watch?v=PPWTxceMutk&feature=youtu.be, свободный. Яз. рус. (дата обращения 5.12.2019).
2. Шалыто А.А. Парадигма автоматного программирования. Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. Вып. 53. Автоматное программирование. 2008, с. 3–23.
3. Шалыто А.А. Парадигма автоматного программирования. Материалы XI Всероссийской конферен-ции по проблемам науки и высшей школы «Фундаментальные исследования и инновации в технических университетах». СПбГПУ. 2007, с. 202–205., [Электронный ресурс], Режим доступа: is.ifmo.ru/works/_2007_09_27_shalyto.pdf, свободный. Яз. рус. (дата обращения 5.12.2019).
4. Мирошник И.В. Теория автоматического управления. Линейные системы. — СПб.: Питер, 2005. — 336 с.
5. Майоров С.А., Новиков Г.И. Структура электронных вычислительных машин. – Л.: Машинострое-ние, 1979. – 384 с.
6. Минский М. Вычисления и автоматы. М.: Мир, 1971. – 364 с.
7. Карпов Ю.Г. Теория автоматов. – СПб.: Питер, 2003. – 208 с.
8. Поликарпова Н., А. Шалыто А. Автоматное программирование. 2-е изд., – СПб.: Питер, 2011. – 176 с.
9. Дж.Макконелл Анализ алгоритмов. Активный обучающий подход. 3-е дополненное издание. – М.: Техносфера, 2013. – 415 с.
10. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных сис-тем. М.: Наука, 1982, – 336с.
11. Шалыто А.А., Туккель Н.И. От тьюрингова программирования к автоматному // МирПК. №2. is.ifmo.ru/?i0=works&i1=turing
12. Любченко В.С. Эксперименты над абстрактными машинами. «Мир ПК», № 2,3/02. www.osp.ru/pcworld/2002/02/162923, www.osp.ru/pcworld/2002/03/163137
13. Любченко В.С. От машины Тьюринга к машине Мили. «Мир ПК», № 8/02. www.osp.ru/pcworld/2002/08/163856
14. Сайт SoftCraft. Использование теории автоматов в программировании. [Электронный ресурс], Режим доступа: www.softcraft.ru/auto, свободный. Яз. рус. (дата обращения 5.12.2019).

Комментарии (10)


  1. toyban
    26.12.2019 11:58

    Машины Тьюринга не эквивалентны классическим конечным автоматам. И более того, программирование не может быть представлено в виде классического конечного автомата. Чтоб убедиться в этом, попробуйте описать машину Тьюринга и конечный автомат, которые распознают слова из алфавита {0,1}, в которых количество нулей равно количеству единиц.


    1. lws0954 Автор
      26.12.2019 21:52

      Спору нет, безусловно, МТ не эквивалентны КА. Но, замечу, статья-то о том, что эквивалентны МТ и автоматные программы (подчеркиваю, что КА это только лишь часть АП — ее управление). Более того, МТ — это модель АП. Следовательно, все, что может МТ (а она может все!), может и АП.
      А «чтобы убедиться в этом», замените в примере рис.5, рис.6 символ «a» на «0», а символ «b» на 1 и Вы получите в точности тот язык, который предлагаете распознать. Получилось?


  1. Zenitchik
    26.12.2019 14:58

    Машина Тьюринга — сильно избыточна для автоматных программ.


    1. lws0954 Автор
      26.12.2019 22:04

      Мысль, конечно, интересная, но бездоказательная. Да и зачем умалять достоинства АП. Но пусть даже избыточна, как Вы утверждаете. Ну, и что? АП тогда тоже «избыточны» поскольку их моделью является как раз МТ? И в чем заключена эта самая «избыточность»? И что значит «сильно»? И что надо у МТ убрать, чтобы лишить ее «избыточности»?


      1. Zenitchik
        26.12.2019 22:41

        Простите, что значит «бездоказательная»?
        Под автоматными языками понимаются языки, трансляция которых возможна с помощью КА.
        Чем отличается КА от МТ, Вы и без меня знаете.


  1. lws0954 Автор
    26.12.2019 23:01

    Я не рассматриваю чистый КА. Я рассматриваю автоматные программы (АП), в которые КА входят составной частью. Т.е. чистый КА и АП — это качественно разные вещи. В АП, кроме КА, входит еще множество операторов и множество переменных. Роль КА, как управления автоматной программы, запускать операторы автоматной программы, которые уже делают с переменными автоматной программы все, что угодно.


    1. toyban
      27.12.2019 07:45

      А Вы не могли бы дать четкое и формальное определение, что такое автоматные программы?


  1. lws0954 Автор
    27.12.2019 09:54

    Могу только повторить (см. статью), что автоматная программа — это программа, имеющая управление в форме модели конечного автомата. Но это общее определение. Дальше нужно, конечно, конкретизировать модель автомата, т.к. подобных моделей достаточно много. Предлагается модель структурного конечного автомата с абстрактным состоянием, сокращенно — СКА.
    Текст программ дает представление уже о форме описания СКА. Это таблица переходов в текстовой форме. И уже она интерпретируется программным ядром, реализующим работу управления АП.
    Интерпретатор необходим, т.к. не существует аппаратной поддержки. Например, для обычных программ такой «поддержкой» являются операторы управления программ — do, while, go to, for, switch и т.д. и т.п.


  1. lolikandr
    27.12.2019 20:22
    +1

    Было бы неплохо посмотреть на примеры автоматных программ, а особенно с комментариями, что в них нельзя менять, чтобы они не перестали быть автоматными.


    1. lws0954 Автор
      28.12.2019 15:40

      Большое спасибо за интересный вопрос.
      Отвечая, можно сказать просто — не менять управление. Остальное к АП уже фактически не имеет отношения (см. определение АП).
      Как это будет выглядеть в нашем случае?
      Введем в автоматный класс «неавтоматную» функцию/метод increment:

      void FTIncrement::increment() {
          while (!x1()) {
              y15();
          }
          y16();
          while (x2()||(!x2()&&!x1()&&!x3())) {
              if (x2()) {
                  y2(); y16();
              }
          }
          if (x1()||x3()) {
              y1();
          }
      }
      

      Теперь класс может быть и неавтоматным. К нему можно будет обращаться, ну, например, уже так:

      FTIncrement *p = new FTIncrement(«inc», nullptr);
      p->increment();

      И, что интересно, будет даже работать.
      Но для проверки пришлось проделать следующее.
      Поскольку я работаю в рамках среды ВКПа и с автоматами, то пришлось немного извратиться.
      Так, я привел управление класса FTIncrement к совсем простому автомату (остальные строки таблицы переходов убрал):
      LArc(«Прямой проход», «Конец», "--", «y3»), // функция инкремента
      LArc(«Конец», «Прямой проход», «x16», «y17»), // Перезапуск машины

      Одновременно это значит, что для сигнала y3 нужно создать одноименное действие y3().

      void FTIncrement::y3() { increment(); }

      Ну и все. Не так уж сложно. Мне уж точно.
      Запускаем. Теперь функция increment за один так делает то, на что исходному автомату требовалось много больше [дискретного] времени. Я даже посчитал: для заданной строки 11011110011111, чтобы получить в результате 11011110100000 нужен 21 такт. Но для исследования «идеи» это нормально.
      Интереснее другое. Приглядимся к автомату. Что будет, если среди символов 0, 1 попадется другой, например, 2. Автомат, как и МТ, зависнет в состоянии «Обратный проход», т.к. не знает, что ему в такой ситуации делать. Эквивалентная ему функция зависнет на операторе while (x2()||(!x2()&&!x1()&&!x3())). При этом она, в отличие от автомата, подвесит и приложение. А это уже совсем плохо. Т.е. подобные ошибки в случае неавтоматных программ ведут фактически к краху приложения.
      Для автомата разрешить проблему просто. Достаточно в таблицу переходов добавить, например, такой переход:
      LArc(«Обратный проход», «Конец», "^x1^x2^x3","--"), // неопознанный символ
      Для функции increment нужно изменить ее код, который учитывал бы и эту ситуацию.
      Чем хороши в данной ситуации автоматы. Если бы мы делали формальный анализ автомата на рис. 4, то сразу бы подобную ошибку обнаружили, т.к. анализ на полноту и непротиворечивость переходов это выявляет сразу. Не надо даже вникать в работу автомата — все делает теория автоматов. Для функцией increment подобный анализ — это уже другая история. Т.е. то, что обычно для автоматов, для обычных программ необычно :).
      Ну вот как-то так…