آلة تورينج ، كنموذج لبرامج التشغيل الآلي

آلة تورينج ، كنموذج لبرامج التشغيل الآلي

1. مقدمة

تحتاج البرمجة إلى نماذج خوارزمية عالمية جديدة ، ويقوم الجهاز بتنفيذ الخوارزميات ليس فقط في شكل مختلف ، ولكن أيضًا على أساس نموذج خوارزمي آخر - تلقائي. يعد اعتماد التكنولوجيا من مجال تطوير الأجهزة فكرة أساسية للبرمجة الآلية. ومع ذلك ، فإن تركيب الأجهزة الرقمية يختلف عن البرمجة. لكن ، من خلال استعارة نموذج ، من ناحية ، لا يُنصح بتغييره إلى حد كبير ، لكن من ناحية أخرى ، لا يمكن للمرء أن يتجاهل النظرية والممارسة الحالية للبرمجة.

بعد ذلك ، سننظر في تقنية SWITCH لتصميم البرامج الآلية ، والتي تواجه فيها هذه العمليات طوال الوقت. فمن ناحية ، غيّرت نموذج آلة الدولة إلى درجة جعلتها في الواقع تتجاوز نطاق نظرية الأوتوماتا. ومن ناحية أخرى ، فإنه يدخل في مفاهيم البرمجة التي يصعب على المبرمجين إدراكها ، وفي بعض الأحيان ، لا لزوم لها ، هناك نظراء أكثر دراية من نظرية البرنامج وممارسة البرمجة.

كأساس لمناقشة مشاكل البرمجة التلقائية ، نأخذ المحاضرة الأخيرة التي ألقاها أ. Shalyto [1] ومقالاته "البرنامجية" حول تعريف نموذج البرمجة التلقائية [2 ، 3].

1. الكائنات الآلية ، مخططات البرنامج

في المحاضرة ، يتمثل تحقيق البرمجة التلقائية في تقديم مفهوم كائنات التحكم الآلي ، المستعارة من نظرية التحكم الآلي (TAU). ولكن ، تذكر أنه في TAU لا يفكرون في أشياء كثيرة ، ولكن في الأنظمة ، ومن بينها ما يلي [4]:



بناءً على ذلك ، سيكون من الأصح الحديث عن أنظمة التحكم الآلي (ACS). الآن دعونا نلقي نظرة على الشكل الوظيفي النموذجي للأسلحة ذاتية الدفع الموضحة في الشكل. 1. إذا كان شريط آلة تورينج هو كائن التحكم ، فإن الأجهزة المشغلة (IS) ستكون عناصر MT التي تنفذ التغيير في محتويات الشريط وتحرك الرأس ، وستكون أجهزة القياس (IS) هي العناصر التي تقرأ المعلومات من الشريط.


الشكل 1. مخطط وظيفي للبنادق ذاتية الدفع

ولكن لماذا أنتقل إلى TAU ، إذا كانت هناك ممارسة أقرب إلى برمجة تصميم أنظمة الكمبيوتر ، حيث تعتبر أجهزة التشغيل (OS) ، والتي تتضمن MT بالطبع ، مزيجًا من آلات التشغيل (OA) والتحكم (UA). وهذا أقرب إلى ما نسعى إليه في النهاية - تبرير قوة البرمجة التلقائية. في التين. 2 يعرض شاشة النص من دراسة من قبل Mayorov S.A. ، Novikov G.I. هيكل الحواسيب الإلكترونية [5] ، حيث يتم النظر في قضايا التصميم من أمبير المرجع بتفصيل كبير.


الشكل 2. مفهوم مدير وآلات التشغيل

لكن إذا قارنا نظرية تصميم الكمبيوتر ونظرية البرامج ، فيمكن تتبع تشابه هيكلي واضح بينهما. في نظرية البرمجة ، يمكن تمثيل نموذج أي برنامج على المستوى الهيكلي كمخطط برنامجي S = (M ، A ، C) ، حيث M هي مجموعة عناصر الذاكرة ، A هي مجموعة العوامل ، C هو التحكم [10]. باتباع هذا النهج ، يمكن أيضًا تعريف أي برنامج لآلة Turing على أنه مخطط برنامج يتم فيه تمثيل المجموعة M بخلايا الأشرطة ومجموعة المشغلين بإجراءات MT المرتبطة بتحليل الخلية و 2) تغيير الأحرف في خلايا الشريط و 3) تحريك الرأس.

وبالتالي ، فإن مفهوم مخطط البرنامج مماثل تمامًا للمفهوم المدروس لأتمتة التشغيل والتحكم ، حيث يكون نموذج UA هو نموذج آلة الحالة الهيكلية المحدودة (SKA) المذكورة أدناه ، و OA "هو هيكل لتنفيذ الإجراءات على المعلومات." في هذه الحالة ، تتضمن الزراعة العضوية عناصر تخزين البيانات (أعلاه هي الذاكرة) وكتل لمعالجة المعلومات التي تنفذ حساب الشروط المنطقية وتنفيذ إجراءات معينة (أعلاه - العديد من العوامل).

مما سبق ، يمكن فهم أن الشريط لا يمكن اعتباره سوى كائن التحكم لـ MT. إذا لم يكن لجهاز التحكم في آلة تورينج الوصول المباشر إليه ، لأنه يتم تحقيق جميع العمليات مع الخلايا بشكل غير مباشر من خلال كتل الزراعة العضوية. بالإضافة إلى ذلك ، يبدو أنه ليس مألوفًا جدًا أو ، إن لم يكن القول ، من الغريب اعتبار هدف إدارة البرنامج ، كنظام تحكم ، كائنًا يمثل ذاكرة (شريط).
وبالتالي ، من أجل تعريف رسمي لآلة تورينج ، وفي سياقها مكان لنموذج آلة الحالة المحدودة ، تكون مفاهيم نظرية البرنامج كافية. الآن ، على عكس التعريف الغامض للغاية لبرامج التشغيل الآلي المقدمة في إطار تقنية SWITCH ، يمكننا أن نقول أن برنامج التشغيل الآلي هو برنامج يتمتع بالتحكم في شكل نموذج لآلة الحالة المحدودة.

ماذا سيكون البرنامج نفسه - بسلوك بسيط أو معقد ، ما هو "تنوعه" - مع التحكم المنطقي ، "مع تخصيص حالة صريح" ، إلخ. إلخ لا يهم على الاطلاق. الشيء الرئيسي هو نوع الإدارة. يمكن تحديد العناصر المتبقية من البرنامج على نطاق واسع - من أبسط ، على سبيل المثال ، مع آلة تورينج ، إلى الأكثر تعقيدًا - أي شكل من أشكال المشغلين والوظائف وهياكل البيانات الخاصة بلغات البرمجة - المجمّع ، واللغة عالية المستوى ، إلخ.

يمكنك أيضًا أن تتذكر أن آلة تورينج تعتبر منذ فترة طويلة حصيرة أوتوماتيكية [6] أو ، في الحالات القصوى ، امتدادها البسيط [7]. لكن عليك أن تفهم ما هو نوع الأوتوماتون ، ونوع الامتداد ، وما إذا كانت مكافئة لنماذج آلات الحالة المحدودة الكلاسيكية. دعنا نحاول توضيح ذلك.

2. تورينج البرمجة في بيئة البرمجة الآلية

في التين. يوضح الشكل 3 الأوتوماتون لوظيفة زيادة MT من الدراسة [8]. في الشكل ، من الواضح أن هذا ليس برنامج MT ، ولكنه ليس بالفعل جهازًا كلاسيكيًا للحالة المحدودة. في التين. يوضح الشكل 4 الرسم البياني لآلة الحالة المحدودة الهيكلية الكلاسيكية (SKA) وتنفيذها في بيئة VKPa (بيئة البرمجة الآلية للمكوّن المرئي في C ++ في إطار مكتبة Qt وبيئة Qt Creator) ، التي تنفذ نفس خوارزمية وحدة التحكم MT.


الشكل 3. زيادة الرقم لكل وحدة باستخدام آلة تورينج


الشكل 4: نموذج لبرنامج الزيادة ل MT في شكل SKA

يمكنك أن ترى أن الجهاز الهيكلي يحتوي على أربع قنوات إدخال وخمس قنوات إخراج. ترتبط كل من هذه القنوات بوظيفة البرنامج الذي يحمل نفس الاسم - تقييم أو إجراء. هنا ، المسند عبارة عن وظائف بدون معلمات تُرجع قيمة Boolean استنادًا إلى قيمة خلية الشريط التي تعرضها ، والإجراءات عبارة عن وظائف بدون معلمات تؤدي إجراءً واحدًا أو آخر لتغيير خلية الشريط وتحريك رأس آلة Turing.

تحتوي SKA على نفس مجموعة الحالات التي يتمتع بها المحرك الآلي في الشكل 3. علاوة على ذلك ، بالإضافة إلى تعيين الأوتوماتون نفسه ، الذي قدمته SKA ، فإنه يطبق تعيينين إضافيين: تعيين مجموعة من المسندات (x1 ، ... ، xM) إلى مجموعة قنوات الإدخال لنفس الجهاز ، ومجموعة قنوات الإخراج الخاصة بالجهاز إلى مجموعة الإجراءات نفسها - y1 ، ... ، yN. على سبيل المثال ، ستعود القيمة الأصلية x3 إلى القيمة الحقيقية (القيمة 1 لإشارة الدخل التي تحمل نفس الاسم) ، إذا كان هناك 1 في الخلية الحالية ، والإجراء y4 ، الذي سيتم تشغيله عندما تأخذ نفس إشارة الخرج الخاصة بالجهاز ، القيمة 1 ، فسوف تتوافق مع تحريك الرأس إلى اليسار (L) و إلخ إلخ

لاحظ أن SKA لا تتحكم بشكل مباشر في الشريط ، ولكنها تنفذ [تعيينات إضافية] ، وربط إشارات الأوتوماتون بالوظائف التي تحدد العديد من عمليات آلة تورينج. هذا يقنعنا مرة أخرى بأنه ليست هناك حاجة لإدخال مفهوم كائن التحكم الآلي في الحالة التي يكون فيها "التعيين القديم" ، ولكن المفهوم الدقيق للرياضيات ، كافياً.

مقارنة الأوتوماتة في الشكل. 3 والتين. 4 ، يمكن ملاحظة أن SKA لا تستخدم الأمر "*" (انظر الشكل 1). في مثل هذه الحالة ، يكفي أن لا يعطي إشارة مرتبطة بهذا الأمر. بالإضافة إلى ذلك ، هناك إشارتان أو أكثر (المدخلات والمخرجات) في نفس المرحلة الانتقالية متوازية. لذلك ، عندما يكون هناك تعارض في الوصول إلى الكائنات المشتركة (على سبيل المثال ، تحتاج إلى تغيير الخلية وتحريك الرأس) ، يتم استخدام اتفاقية: يتم تنفيذ الإجراءات المتعلقة بمرحلة انتقال واحدة بالتسلسل بترتيب أرقامها ، أي يتم تنفيذ إجراء ذي رقم أعلى بعد إجراء ذي رقم أقل. هذا الاتفاق لا ينطبق على المسندات ، كما انهم لا يغيرون الشريط. لذلك نحن نجعل الجهاز أكثر إحكاما وبديهية (لا حاجة لتقديم حالات وسيطة).

في عملية اختبار برنامج الزيادة ، تم تحديد المواقف التي قد تنشأ فيها مشاكل أثناء تشغيل جهاز MT. أولاً ، الشريط الحقيقي ليس لانهائي ويمكن أن يؤدي تجاوزه إلى تعطل البرنامج. ثانيا ، من الضروري الإشارة إلى الوضع الأولي للرأس. بدون ذلك ، على سبيل المثال ، إذا كان الرقم في مكان تعسفي من الشريط ، وكانت الحالة الأولية للرأس على يسار الرقم ومقابل المساحة ، فسيبدأ الرأس على الفور في الانتقال إلى اليسار. بعد ذلك ، يمكن أن يتجاوز حدود الشريط ، مما يتسبب في "تعطل" البرنامج ، أو بعد نقله خطوة واحدة إلى اليسار ، سيكتب إلى الخلية 1 ، وسيكمل ، معلقًا ، العملية "الناجحة". أو ، إذا كان الرقم يحتوي على رقم واحد في جميع الأرقام وتم كتابته من بداية الشريط ، فإن المحاولة الأخيرة لنقل الرقم 1 إلى الرقم الأقدم ستتسبب في نفس "التعطل".

2.1. كائن تنفيذ MT في C ++

ضع في اعتبارك تطبيق برنامج الكائن لجهاز Turing في C ++ في بيئة VKPa ، التي تنفذ أي برنامج لـ MT ، بما في ذلك برنامج حساب الزيادة.

لهذا الغرض ، تم إنشاء فئة أساسية تمثل أي جهاز تورينج ، والذي يتم توارثه بواسطة كائنات البرامج التي تنفذ برنامج MT أو آخر. يظهر هذا العنصر الأساسي في القائمة 1 ، ويتم عرض البرنامج الذي ينفذ مهمة الزيادة في القائمة 2.

القائمة 1. تنفيذ البرنامج للفئة الأساسية MT

#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. أمثلة لبرامج MT مع التنفيذ في C ++

فكر في مثال لبرنامج MT الذي "يعمل كمتقبل للغة ، أي يمكنه التعرف على اللغة "من [9]. تظهر وظيفة الانتقال في الشكل. 5 ، والأوتوماتون المكافئ في شكل SKA في الشكل. 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}


التين. 6. رسم بياني SKA لجهاز تورينج يتعرف على اللغة {anbn: n≥1}

تحتوي وحدة التحكم MT في شكل SKA على 6 قنوات إدخال و 7 قنوات إخراج. يشتمل برنامج المستلم أيضًا على العدد المقابل من المسندات والإجراءات ، والتي يتم عرضها في الشكل على يمين الرسم البياني التلقائي. يظهر تنفيذ برنامج C ++ في بيئة VKPA في القائمة 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 متغيرًا من برنامج MT وفقًا لنهج تقنية SWITCH. كجزء من تنفيذ البرمجة التلقائية لبيئة VKPA ، في هذه الحالة ، بدلاً من التشغيل التلقائي في الشكل. 6 ، سيكون من الضروري تطبيق آلية مع حالة واحدة ، والتي تصدر إشارة y18 في الدورة. يتوافق مع سطر التعليق الذي تم تعليقه من جدول التحويل في القائمة 3. لكي يعمل الجهاز التلقائي كـ SWICH ، تحتاج إلى إزالة التعليق من هذا السطر والتعليق على الأسطر المتبقية.

النظر في مثال آخر لبرنامج لآلة تورينج من [7] ، حيث يتم تعريف MT بأنه "امتداد بسيط للغاية لنموذج آلة الحالة المحدودة". في هذه الحالة ، يعد برنامج جهاز تورينج عبارة عن قائمة محدودة من الخمسات للدالة المحددة جزئيًا للتحولات والنواتج δ: S × XS × X × G.

يظهر برنامج MT ، الذي يعثر على أكبر مقسوم مشترك (GCD) من رقمين ، في الشكل. 7. يتم عرض الرسم البياني SKA المكافئ له في الشكل. 8. لاحظ أن أمر إعادة الكتابة لا يستخدم هنا أيضًا. يظهر تطبيق C ++ في القائمة 4.


التين. 7. الرسم البياني للانتقال لآلة تورينج التي تحسب GCD من رقمين ، والعديد من تكويناتها عند معالجة زوج من الأرقام <4 ، 6>


التين. 8. الرسم البياني SKA ، أي ما يعادل الرسم البياني في الشكل. 7

قائمة 4. برنامج لآلة تورينج للعثور على GCD من رقمين

 #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; } 

في الختام ، هناك برنامج MT آخر من مطوري تقنية SWITH ، تم بحثه في المقال [11] ، والذي يقدم مهمة التعرف على الأقواس في نسختين. إحداها في شكل آلة مايلي ، والثانية هي آلة مختلطة (على التوالي في الشكل 9 والشكل 11). وتظهر الأوتوماتيكية الهيكلية المقابلة لها في الشكل. 10 والتين. 12. يظهر تنفيذ برنامج C ++ في القائمة 5.


التين. 9. الاعتراف بين قوسين من عمق التعسفي. ميل تحويل الرسم البياني


التين. 10. الاعتراف بين قوسين من عمق التعسفي. مايلز إيرل سكاي


التين. 11. الاعتراف بين قوسين من عمق التعسفي. رسم بياني انتقالي لآلية مختلطة


التين. 12. الاعتراف بين قوسين من عمق التعسفي. الرسم البياني SCA من التحولات من automaton مختلطة

قائمة 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. يتم عرض آلة أوتوماتيكية مكافئة لها في شكل SKA في الشكل. 10. صحيحًا ، هذا أيضًا شكل تلقائي مختلط ، حيث تم ترك الإشارة عند الحالة "0" والإشارة y15 في الحالة "1" من التنفيذ الأول (الشكل 12). الأول ضروري أثناء التثبيت الأولي ، وتنفذ إشارة y15 نوبة رأس إلى اليمين لقراءة حرف الشريط التالي. ما تبقى من SKA يتوافق مع آلة مايلز في الشكل. 9.

بعد التشغيل الآلي في التين. تم اختبار 10 بنجاح ، وعاد إلى الجهاز في الشكل. 11. وأصبح من الواضح أن الإشارة z1_1 بالحالة "1" لا لزوم لها (بالنسبة للإوتوماتون في الشكل 12 فهي الإشارة y2). المشكلة هي أنه عندما يجد "القوس الأيسر" ، فإنه يزيد العداد بوحدتين ، وعندما يجد "القوس الأيسر" لا يغيره على الإطلاق. لذلك ، عندما يتم الكشف عن "القوس الأيسر" ، يتم استدعاؤه مرتين - مرة واحدة على الحلقة التي تحمل علامة x2 / y2 ، والمرة الثانية عند دخول الحالة. وعندما يتم الكشف عن "القوس الأيمن" ، فإن العداد يتناقص أولاً في الحلقة ، ثم يزداد عند دخول الحالة.

السبب في هذا العمل لعنصر التحكم MT هو في تفسير غير صحيح من قبل مؤلفي أداء آلة نوع مور. على ما يبدو ، يعتقدون أن الإشارة التي تحتوي على حالة في Moore automaton يتم تنفيذها فقط عندما تدخل هذه الحالة (انظر الانتقال من الحالة "0" إلى "1") ، ولكن في الواقع يتم إصدارها في كل مرة تدخل فيها هذه الحالة. بما في ذلك عندما يمر حلقة. وبالتالي ، نحن لا نتعامل مع خطأ (من لم يكن مخطئًا؟) ، ولكن مع مشكلة أكثر خطورة - تفسير غير صحيح في إطار SWITH-technology لأداء نوع مور التلقائي. اختبار نموذج مكافئ أظهر هذا.

3. الخاتمة

لتلخيص ، يمكننا القول أنه لا توجد اختلافات رسمية بين تورينج والبرمجة التلقائية ، كما آلة تورينج هي نموذج مجردة لبرامج التشغيل الآلي. فقط في الحالة الأخيرة ، يتم استخدام مجموعة واسعة من العوامل وهياكل البيانات (الذاكرة). الآن يمكننا الإجابة بثقة على السؤال عن كيفية اختلاف Post Post ، كنموذج للبرامج العادية ، عن Turing machine ، نموذج البرامج التلقائية. نموذج الإدارة وفقط ، ل الباقي - الذاكرة والمشغلين يمكن أن تكون هي نفسها.
وبالتالي ، تختلف البرمجة العادية عن البرمجة التلقائية في شيء واحد فقط - نموذج التحكم. وبالتالي ، في حين يتم استخدام مشغلي التحكم العادي من نوع المحول لتنفيذ الأتمتة ، ولا يمكن استخدام ما شابه ، بالمعنى الدقيق للكلمة ، تعتبر هذه البرمجة تلقائية. يمكن أن يكون هذا تقليدًا للأتمتة مع فقد خصائصها المحددة ولا شيء أكثر من ذلك.

لذلك ، عند إعطاء تعريف لمفاهيم برنامج التشغيل الآلي وبرمجة التشغيل التلقائي ، لا نحتاج إلى التحدث عن "عناصر التحكم الآلي" ، ولكن عن البرامج والبرامج الوحيدة التي لها تحكم في شكل آلة حالة كلاسيكية محدودة.
وحقيقة أخرى مثيرة للاهتمام أود أن ألفت الانتباه إليها. في أوائل العقد الأول من القرن العشرين ، عبر المؤلفون عن فهمهم للبرمجة التلقائية لجمهور واسع. تم نشر مقالاتهم حول الآلات المجردة في مجلة PC World رقم 2 لعام 2002 [11 ، 12 ، 13]. يمكن القول أنه على مر السنين ، لم تتأثر قناعات الأطراف. على الرغم من أن هذا ربما يعكس فقط درجة ثقتهم في القرارات المختارة.

على سبيل المثال ، في "محاضرة جديدة عن البرمجة التلقائية" أ. شاليتو مقارنة بـ "المحاضرة ذات الشرائح" السابقة (قبل عشر سنوات) ، لم تتم إضافة سوى مقطع فيديو للمثال استنادًا إلى "الحزمة الحديثة" Stateflow. يبدو أن هذا يؤكد صحة أفكار أ. شاليتو ، لأنه ما لا يمكن تنفيذه داخل UniMod (يبدو أن المشروع "تم تجميده") ، يتجسد مطورو Stateflow. وربما ، ليس من المهم من فعل ذلك ...

ومع ذلك ، في وقت نشر المقالات المذكورة ، كان مؤلفو تقنية SWITCH يعرفون بالفعل نقدها. هذا لم يكن سرا منذ ذلك الحين كانت متاحة على موقع SoftCraft [14]. كما أنشأت أقسامًا مخصصة للبرمجة التلقائية بشكل عام وتكنولوجيا SWITH وتكنولوجيا KA على وجه الخصوص. نوقشت مواقف المؤلفين في منتدى الموقع (كان مفتوحًا في ذلك الوقت). لكن كلهم ​​ظلوا غير مقتنعين.

النتائج في الوقت الحالي هي كما يلي. النقد المعبر عنه فيما يتعلق بتكنولوجيا SWITH ذات مرة هو ذو صلة وحديثة. ينطبق أيضًا على حزمة Stateflow. في تقنية SWITH ، لم يكن هناك ، وليس هناك تعريف واضح للبرمجة التلقائية ، لم يتغير أسلوب تنفيذ الأوتوماتة ، النموذج نفسه ليس كلاسيكيًا ، لا يوجد نموذج حوسبة متوازي ، إلخ. إلخ دون القضاء على هذه المشكلات ، تدعي هذه البرمجة الآلية في أفضل الأحوال دورًا محدودًا إلى حد ما.

أسباب المشكلات المذكورة أعلاه واضحة تمامًا: يتم تجاهل نظرية البرامج ، ونسيان نظرية الأتمتة ، على الرغم من قول الكثير من الكلمات الجيدة والصحيحة حول الأتمتة نفسها وخصائصها الرائعة. ولكن في الواقع هذه هي الآلات الأخرى. المؤلف مقتنع بالشك في المحاولات السيئة لإنشاء نماذج أصلية. إنها عن نماذج متزامن ، رد الفعل وغيرها. يمكن أن تكون مريحة عند حل فئة ضيقة من المشاكل وليس أكثر. لكن الأخطر من ذلك هو أنها تقع خارج نظرية الأتمتة دون أن تمتلك نظرية خاصة بها. لكن النموذج الخارجي للنظرية لا حول له ولا قوة ، وبالتالي لا معنى له تقريبًا.