الدولة والوقت الذي يتجاوز المنطق وتدفق البرنامج؟

Question

هل تتساءل عما إذا كان من المفيد فهرسة كل حالة محتملة للتطبيق باستخدام بعض المفاتيح المرجعية...

بمعنى، لنفترض أن لدينا برنامجًا يبدأ، وله عدد قليل جدًا من النتائج المحتملة، على سبيل المثال 8.

ولكن إذا تم تحقيق كل نتيجة من خلال المرور عبر العديد من الحالات المنطقية، وبين كل فرع يعتبر حالة ويتم تعيينه لمفتاح.

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

فكر في الأمر كشجرة حيث تكون العقد التي لا تحتوي على أطفال هي النتائج النهائية، وكل فرع بين العقدة ووالديها أو أطفالها هو "حالة"، كل منها مفتاحه مختلف.لذلك، في حين أن هناك 8 أوراق فقط، أو النتائج النهائية للعملية، فمن الممكن أن يكون هناك العديد من "الحالات" اعتمادًا على مدى عمق المنطق في الشجرة قبل نفاد الأطفال.

ربما من أجل المحاكاة، لكن الأمر سيستغرق الكثير من الذاكرة.

Answer 1

رايان، الجواب هو نعم بالتأكيد.

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

في النظام الرقمي الحتمي (أي.برنامج يعمل على أجهزة رقمية حقيقية)، فإن عدد الحالات المحتملة محدود، وبالتالي فإن جميع الحالات المحتملة قابلة للعد.

سيكون المقدار الدقيق للذاكرة المطلوبة للتجزئة هو:

(2)*(program state size)*(number of initial states)

ستكون الحالة الأولية هي مفتاح التجزئة الخاص بك، وستكون الحالة النهائية هي قيمة التجزئة، وبعد ذلك سيكون لديك زوج مفتاح/قيمة لكل حالة أولية.

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

توضيح:

يعد هذا مفيدًا للغاية، لأنه إذا قمت بفهرسة كل حالة أولية محتملة وربطتها بحالة النهاية، فسوف تجعل وقت تشغيل أي برنامج يصل إلى الصفر!أي بصفر أعني وقت تشغيل سريع جدًا O(1) - الوقت المستغرق للبحث عن حالة الإنهاء (إذا انتهت).

إن تشغيل البرنامج، بدءًا من كل حالة من الحالات الممكنة، سيوفر نوعًا من خريطة الحالة التي تعرض الدورات. وبالتالي تم حل مشكلة التوقف، لأنه لا يوجد سوى ثلاثة احتمالات (في الواقع أربعة تنهار إلى ثلاثة) في ضوء أي حالة أولية محتملة:

1. سيقوم البرنامج بإعادة إدخال الحالة التي واجهها سابقًا (منذ الحالة الأولية)، قبل استنفاد جميع الحالات المحتملة، وبالتالي يتكرر بشكل منطقي إلى الأبد.
2. يصل البرنامج إلى حالة تم تحديدها على أنها "منتهية" قبل أن تتاح له فرصة إعادة الدخول إلى حالة تمت مواجهتها مسبقًا أو استنفاد جميع الحالات الممكنة (منذ الحالة الأولية).

3. أو 4.سيبدأ أبسط برنامج من حالة أولية، وسيدخل جميع الحالات الممكنة مرة واحدة بالضبط، وبعد ذلك ليس لديه خيار سوى (3) التوقف أو (4) إعادة الدخول إلى حالة تمت مواجهتها مسبقًا والتكرار إلى الأبد.

   ل(int i = 0;حقيقي؛أنا ++)؛// سأصل إلى القيمة القصوى، ثم أعود إلى الصفر، وعند هذه النقطة ستعود إلى الحالة الأولية

لذلك، في الأساس، يمكن وصف الفهرس الخاص بك على النحو التالي:

• لكل حالة أولية، هناك حالة إنهاء واحدة بالضبط أو صفر.

بمعنى آخر ، لكل حالة أولية ، يصل البرنامج إما إلى حالة إنهاء أو إعادة إدخال دولة واجهتها بالفعل منذ الحالة الأولية والدورات إلى ما لا نهاية.

لذلك، لأي برنامج قيد التشغيل الأجهزة الرقمية الحتمية, ، إنها ممكن تماما (ولكن في كثير من الأحيان ليس عملي) لتحديد جميع حالاته وما إذا كان سيتوقف أو يتكرر إلى الأبد.

• يعتمد التطبيق العملي فقط على عدد الحالات الأولية الصالحة لديك (والتي يمكنك تقليلها بشكل جذري مع قيود الإدخال)، ومدى جدوى قضاء الوقت في تشغيل البرنامج لكل منها لإنهاء وتخزين الحالة الناتجة في جدول التجزئة.

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

ما يثبته هذا هو أنه يمكن تمثيل أي برنامج بواسطة جدول التجزئة.يمكن تمثيل أي برنامج بخريطة انتقال الحالة الأولية إلى النهائية.يمكن تبسيط جميع البرامج إلى وظيفة واحدة كبيرة ذات مساحة ذاكرة هائلة!

Answer 2

وهذا لن يكون من الممكن حل للبرنامج عام. مشكلة وقف يثبت أن من المستحيل تحديد ما إذا كان البرنامج سوف توقف. مشكلة تحديد ما إذا كانت دولة معينة هو ممكن هو اختزال لمشكلة وقف، وبالتالي لا يمكن حلها أيضا.

Answer 3

وأعتقد أن هذا النهج ستكون مستعصية تماما ل، حسنا، أي شيء.

وأما مشكلة البحث، انها كبيرة جدا. وإذا افترضنا أن كل دولة يمكن أن يؤدي إلى نتائج 10 (على الرغم من أنني أعتقد أن هذا الرقم منخفض حقا)، ثم لننظر فقط 20 خطوات إلى الأمام، لدينا الآن لتتبع 200 مليار الاحتمالات.

وتذكر أن كل خطوة في التهم حلقة كنقطة الفرع. حتى إذا كان لدينا الرمز الذي يبدو مثل هذا:

for (int i=0; i < 100; i++)
    some_function();

وبعد عدد من الحالات الممكنة هو (عدد الفروع داخل some_function) ^ 100

Answer 4

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

وعلى سبيل المثال، نقول لديك تطبيق سير العمل الموجهة التي تم تعريفها من قبل DFA (آلة الدولة). كنت في الواقع ثم يمكن ربط نقطة معينة في هذا DFA مع معرف من نوع ما.

وهكذا نعم انها لين العريكة ولكن ليس من دون قيود.

Answer 5

ويتم ذلك على مستوى وظيفة. انها تقنية تسمى التحفيظ .

Answer 6

والهياكل كريبك البحوث والمنطق مشروط. وهذا هو النهج المتبع في برامج النمذجة. أنسى ما نظم الكلاسيكية التي تستخدم هذا النهج.