هل معالج تورينج C99 مكتمل؟

Question

بعد اكتشاف تعزيز قدرات المعالج المسبق وجدت نفسي أتساءل:هل معالج تورينج C99 مكتمل؟

إذا لم يكن الأمر كذلك، فما الذي ينقصه لعدم التأهل؟

Answer 1

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

من وصف المشروع المرتبط:

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

إن الإجابة التي أجراها بول فولتز الثاني مثيرة للإعجاب تمامًا وبالتأكيد أقرب مما اعتقدت أن المعالج المسبق يمكن أن يحصل عليه ، لكنه ليس آلة تورينج حقيقية. لدى المعالج المسبق C بعض الحدود التي تمنعها من تنفيذ برنامج تعسفي مثل آلة تورينج ، حتى لو كان لديك ذاكرة ووقت لا حصر لها. القسم 5.2.4.1 من ج المواصفات يعطي الحد الأدنى التالي لمجمول البرمجي C:

• 63 مستويات التعشيش من التعبيرات الأقواس ضمن تعبير كامل
• 63 حرفًا أوليًا مهمًا في معرف داخلي أو اسم ماكرو
• 4095 المعرفات الكلية المحددة في وقت واحد في وحدة ترجمة واحدة قبل المعالجة
• 4095 حرفًا في خط مصدر منطقي

تتطلب آلية العداد أدناه تعريفًا ماكرو لكل قيمة ، وبالتالي فإن حد تعريف الماكرو سيحد من عدد المرات التي يمكنك فيها حلقة (EVAL(REPEAT(4100, M, ~)) سوف تسفر عن سلوك غير محدد). هذا يضع الحد الأقصى بشكل أساسي على تعقيد البرنامج الذي يمكنك تنفيذه. قد يصل التعشيش وتعقيد التوسعات متعددة المستويات إلى أحد الحدود الأخرى أيضًا.

هذا يختلف اختلافًا أساسيًا عن قيود "الذاكرة اللانهائية". في هذه الحالة ، تشير المواصفات على وجه التحديد إلى أن برنامج التحويل البرمجي C الذي يشترك في المعايير مطلوب فقط ليتوافق مع هذه الحدود ، حتى لو كان لديه وقت غير محدود أو ذاكرة ، وما إلى ذلك. يمكن معالجة أي ملف إدخال يتجاوز هذه الحدود (أو رفض صريح). قد يكون لبعض التطبيقات حدود أعلى ، أو لا توجد حدود على الإطلاق ، ولكن هذا يعتبر "خاصًا بالتنفيذ" وليس جزءًا من المعيار. قد يكون من الممكن استخدام طريقة Paul Fultz II لتنفيذ شيء مثل آلة تورينج بعض تنفيذ برنامج التحويل البرمجي المحدد هذا ليس له حدود محدودة ، ولكن بمعنى عام "هل يمكن القيام بذلك على أي معالجات تعسفية تعسفية ، معالجات ما قبل المعالج" ، الجواب هو لا. نظرًا لأن الحد الأقصى هنا مدمج في اللغة نفسها وليس مجرد تأثير جانبي لعدم قدرتنا على بناء جهاز كمبيوتر لا حصر له ، أقول إن هذا يكسر اكتمال Turing.

Answer 2

حسنًا، لا تتوسع وحدات الماكرو بشكل مباشر بشكل متكرر، ولكن هناك طرق يمكننا التغلب عليها.

أسهل طريقة للقيام بالتكرار في المعالج المسبق هي استخدام تعبير مؤجل.التعبير المؤجل هو تعبير يتطلب المزيد من عمليات الفحص للتوسيع الكامل:

#define EMPTY()
#define DEFER(id) id EMPTY()
#define OBSTRUCT(...) __VA_ARGS__ DEFER(EMPTY)()
#define EXPAND(...) __VA_ARGS__

#define A() 123
A() // Expands to 123
DEFER(A)() // Expands to A () because it requires one more scan to fully expand
EXPAND(DEFER(A)()) // Expands to 123, because the EXPAND macro forces another scan

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

#define EVAL(...)  EVAL1(EVAL1(EVAL1(__VA_ARGS__)))
#define EVAL1(...) EVAL2(EVAL2(EVAL2(__VA_ARGS__)))
#define EVAL2(...) EVAL3(EVAL3(EVAL3(__VA_ARGS__)))
#define EVAL3(...) EVAL4(EVAL4(EVAL4(__VA_ARGS__)))
#define EVAL4(...) EVAL5(EVAL5(EVAL5(__VA_ARGS__)))
#define EVAL5(...) __VA_ARGS__

الآن إذا أردنا تنفيذ أ REPEAT الماكرو باستخدام العودية، نحتاج أولاً إلى بعض عوامل الزيادة والنقصان للتعامل مع الحالة:

#define CAT(a, ...) PRIMITIVE_CAT(a, __VA_ARGS__)
#define PRIMITIVE_CAT(a, ...) a ## __VA_ARGS__

#define INC(x) PRIMITIVE_CAT(INC_, x)
#define INC_0 1
#define INC_1 2
#define INC_2 3
#define INC_3 4
#define INC_4 5
#define INC_5 6
#define INC_6 7
#define INC_7 8
#define INC_8 9
#define INC_9 9

#define DEC(x) PRIMITIVE_CAT(DEC_, x)
#define DEC_0 0
#define DEC_1 0
#define DEC_2 1
#define DEC_3 2
#define DEC_4 3
#define DEC_5 4
#define DEC_6 5
#define DEC_7 6
#define DEC_8 7
#define DEC_9 8

نحتاج بعد ذلك إلى عدد قليل من وحدات الماكرو الإضافية للقيام بالمنطق:

#define CHECK_N(x, n, ...) n
#define CHECK(...) CHECK_N(__VA_ARGS__, 0,)

#define NOT(x) CHECK(PRIMITIVE_CAT(NOT_, x))
#define NOT_0 ~, 1,

#define COMPL(b) PRIMITIVE_CAT(COMPL_, b)
#define COMPL_0 1
#define COMPL_1 0

#define BOOL(x) COMPL(NOT(x))

#define IIF(c) PRIMITIVE_CAT(IIF_, c)
#define IIF_0(t, ...) __VA_ARGS__
#define IIF_1(t, ...) t

#define IF(c) IIF(BOOL(c))

#define EAT(...)
#define EXPAND(...) __VA_ARGS__
#define WHEN(c) IF(c)(EXPAND, EAT)

الآن مع كل وحدات الماكرو هذه يمكننا كتابة تكراري REPEAT دقيق.نحن نستخدم REPEAT_INDIRECT الماكرو للإشارة إلى نفسه بشكل متكرر.يؤدي هذا إلى منع طلاء الماكرو باللون الأزرق، لأنه سيتم توسيعه عند إجراء فحص مختلف (وباستخدام سياق تعطيل مختلف).نحن نستخدم OBSTRUCT هنا، الأمر الذي سيؤجل التوسع مرتين.وهذا ضروري لأن المشروطة WHEN يطبق مسح واحد بالفعل.

#define REPEAT(count, macro, ...) \
    WHEN(count) \
    ( \
        OBSTRUCT(REPEAT_INDIRECT) () \
        ( \
            DEC(count), macro, __VA_ARGS__ \
        ) \
        OBSTRUCT(macro) \
        ( \
            DEC(count), __VA_ARGS__ \
        ) \
    )
#define REPEAT_INDIRECT() REPEAT

//An example of using this macro
#define M(i, _) i
EVAL(REPEAT(8, M, ~)) // 0 1 2 3 4 5 6 7

الآن يقتصر هذا المثال على 10 تكرارات، بسبب قيود العداد.تمامًا مثل عداد التكرار في الكمبيوتر سيكون محدودًا بالذاكرة المحدودة.يمكن دمج عدادات التكرار المتعددة معًا للتغلب على هذا القيد، تمامًا كما هو الحال في الكمبيوتر.علاوة على ذلك، يمكننا تحديد أ FOREVER دقيق:

#define FOREVER() \
    ? \
    DEFER(FOREVER_INDIRECT) () ()
#define FOREVER_INDIRECT() FOREVER
// Outputs question marks forever
EVAL(FOREVER())

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

Answer 3

لكي يكون Turing كاملًا ، يحتاج المرء إلى تحديد العودية التي قد لا تنتهي أبدًا - يدعو المرء مشغل MU-Decursive.

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

لذا لا يمكن حساب هذه الفئة من الوظائف بواسطة المعالج المسبق C. لأنه في C Preprocessor ، يوجد عدد محدود من وحدات الماكرو المحددة ويتم توسيع كل منها مرة واحدة فقط.

يستخدم المعالج المسبق C خوارزمية ديف بروسر (كتبه ديف بروسر لفريق WG14 في عام 1984). في هذه الخوارزمية ، يتم رسم ماكرو باللون الأزرق في لحظة التوسع الأول ؛ لا توسع مكالمة متكررة (أو مكالمة متكررة متبادلة) ، حيث تم رسمها بالفعل باللون الأزرق في اللحظة التي يبدأ فيها التوسع الأول. لذلك مع وجود عدد محدود من خطوط المعالجة المسبقة ، من المستحيل إجراء مكالمات لا حصر لها للوظائف (وحدات الماكرو) ، والتي تميز مشغلي MU-Recursive.

يمكن للمعالج المسبق C حساب فقط مشغلات سيغما .

لمزيد من التفاصيل ، راجع مسار حساب Marvin L. Minsky (1967) - حساب: آلات محدودة وغير محدودة, ، Prentice-Hall ، Inc. Englewood Cliffs ، NJ وما إلى ذلك

Answer 4

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

تحرير ردًا على تعديلات الأسئلة:

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

الأمرين الوحيدان اللذان ضروريان حقًا لمكملات turing المحدودة (التوافق التوافق؟) هل التكرار/التكرار (بنيات مكافئة) والتفرعة الشرطية.