إيقاف نظرية المشكلة مقابل الممارسة

Question

غالبا ما يكون مؤكد أن مشكلة وقف غير قابلة للكشف.وإثبات أنها تافهة بالفعل.

ولكن هذا ينطبق فقط على برنامج تعسفي.

قد حدثت أي دراسة بشأن فئات البرامج التي يصنعها البشر عادة؟

قد يكون من السهل في بعض الأحيان تحليل برنامج وتعداد جميع درجاتها من الحرية واستنتج أنه سيتوقف.

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

Answer 1

اللغات التي تضمن لوقف استخدام انتشار واسع النطاق. اللغات مثل COQ / AGDA / IDRIS كلها في هذه الفئة. تكفل العديد من أنظمة النوع العديد من الأنظمة لوقف مثل النظام F أو أي من متغيراته على سبيل المثال. من الشائع أن يغلي سلامة نظام النوع لإثبات أن جميع البرامج تطبيعها في ذلك. تطبيع قوي هو خاصية مرغوبة للغاية بشكل عام في أبحاث لغات البرمجة.

لم أر الكثير من النجاح في التقاط الحلقات اللانهائية في الممارسة المعنية بالممارسة "حيث يضمن التأكد من إنهاء ESFP" بواسطة Telford و Turner مدققا أكثر قوة إنهاء تمكنت من إثبات أن خوارزمية Euclid تم إنهاؤها دائما وتؤدي إلى مقبض الحالات الجزئية. خوارزمية Euclid هي مثال صعب للغاية على وظيفة متكررة بدائية لا تثبت بشكل مباشر أن تكون متكررة بدائية. يفشل الداما التي تبحث ببساطة عن معلمة تقليل (أو بعض النمط البسيط من المعلمات المتناقصة مثل مدقق إنهاء الجنين). لتنفيذ هذا باستخدام محكومات متكرر البدائية، عليك أن ترميز إثبات إنهاء الخوارزمية كمعلمة في الوظيفة بشكل أساسي.

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

Answer 2

هناك البحوث السابقة والحالية على هذا. تسمى هذه المشكلة تحليل الإنهاء ، وإلقاء نظرة سريعة على Google (Scholar) توفر العديد من العمر كذلك منشورات جديدة حول هذا:

1. 2005، 2005، تحليل الإنهاء البرامج الوظيفية المرتفعة ؛
2. 2006، 2006، تحليل الإنهاء الآلي ل Haskell < / A>؛
3. 2008، 2008، تحليل إنهاء برامج المنطق بناء على التبعية الرسوم البيانية ؛
4. li> 2010، حلقة تلخيص تحليل الإنهاء ؛
5. li> 2014، تحليل الإنهاء من خلال البرامج الإنهائية في التعلم ؛
6. 2015، 2015، تحليل الإنهاء مع الرسوم البيانية المتداعية العودية ؛
7. 2019، تحليل الإنهاء الثابت للخوارزميات الموزعة بحفلات الأحداث < / A>؛
8. 2019، re="nofollow noreferrer"> تنفيذ تحليل الإنهاء على البرمجة الكمومية ؛

بما في ذلك اللغات الحالية مع الآليات المباشرة لذلك مثل:

• li> href="https://www.mercurylang.org/information/doc-latest/mercury_user_guide/termination-analysis-options.html" rel="noftnofollow noreferrer"> الزئبق
• idris، coq، agda؛

Answer 3

Microsoft has developed a practical code checker (whose name escapes me at the moment) which performs halt-testing. It exploits the fact that the code it checks is human-written and not arbitrary, just as you suggest. More importantly, it bypasses the impossibility proof by being allowed to return the answer 'Cannot decide' if it runs into code too difficult to check.

Answer 4

There are only 2 types of infinite programs:

1. Those that repeat their own state after a point (cyclical)
2. Those that grow indefinitely in used memory

Those in 1st type, follow this pattern:

Where there is a pair of distinct indices i and j such that xi = xj, and after which the cycle repeats itself again (thanks to the deterministic nature of programs). In this case the inputs x, contain the whole memory and variables used by the algorithm, plus the current instruction pointer.

Cycle detection algorithms work very well in practice for this type and can prove that a given cyclical program will never finish, usually after a small number of steps, for most random programs.

Proving those in the 2nd type is where the challenge is. One could argue that type 2 can never exist in reality (as all computers have finite memory) but that is not very useful in practice because the memory used may grow very slowly for a regular computer to ever be full. A simple example of that is a binary counter that never stops and never repeats its full state completely.

Answer 5

There is a huge class of functions that are trivially guaranteed to halt: Everything with a finite number of loops, with an upper limit for the number of iterations for each loop determined before the loop is started.

If you have a random program, it can be difficult to prove whether or not it halts. Programs that are written for a purpose are usually much easier.

Answer 6

The smart contracts functions in the Ethereum blockchain are an example of a system that needs the guarantee of halting, not to stall the whole chain.

Every function has a gas cost, and the gas cost translates into real Ethereum coins. A transaction fee must be paid to call the contract. If the gas used in the contract exceed the gas paid with the transaction fee, the computation terminates immediately.