طريقة فعالة
في علم ما وراء المنطق ، والمنطق الرياضي ، ونظرية الحوسبة ، تُعرَّف الطريقة الفعالة [ 1 ] أو الإجراء الفعال بأنه إجراء حتمي ذو زمن محدود لحل مسألة من فئة محددة. [ 2 ] [ 3 ] ويُطلق على الطريقة الفعالة أحيانًا اسم الطريقة أو الإجراء الآلي . [ 4 ] وتُسمى الدوال التي توجد لها طريقة فعالة أحيانًا بالدوال القابلة للحساب الفعال .
تعريف
بشكل رسمي، تُعتبر الطريقة فعالة لفئة معينة من المشاكل عندما تستوفي المعايير التالية:
- يتكون من عدد محدود من التعليمات الدقيقة والمحدودة.
- عند تطبيقها على مشكلة من فئتها:
- ينتهي الأمر دائمًا بعد عدد محدود من الخطوات.
- إنها تُنتج دائمًا إجابة صحيحة.
- من حيث المبدأ، يمكن القيام بذلك بواسطة إنسان دون أي مساعدات باستثناء أدوات الكتابة.
- يكفي اتباع تعليماته بدقة لتحقيق النجاح. بعبارة أخرى، لا يتطلب الأمر أي براعة لتحقيق النجاح. [ 5 ]
اختيارياً، قد يُشترط أيضاً ألا تُعيد الدالة نتيجةً كما لو كانت إجابةً عند تطبيقها على مسألة من خارج فئتها. يُقلل هذا الشرط من عدد الفئات التي تتوفر لها دالة فعّالة.
الخوارزميات
تُسمى الطريقة الفعالة لحساب قيم الدالة " خوارزمية ".
الدوال القابلة للحساب
أدت عدة جهود مستقلة لوضع توصيف رسمي للحسابية الفعالة إلى ظهور مجموعة متنوعة من التعريفات المقترحة ( الدوال التكرارية العامة ، آلات تورينج ، حساب لامدا ) والتي ثبت لاحقًا أنها متكافئة. يُعرف المفهوم الذي تشمله هذه التعريفات بالحسابية التكرارية أو الحسابية الفعالة .
تنص أطروحة تشيرش -تورينغ على أن المفهومين متطابقان: أي دالة نظرية عددية قابلة للحساب بشكل فعال قابلة للحساب بشكل متكرر .
انظر أيضاً
مراجع
- ↑ هنتر، جيفري (1996) [1971]. " 1.7 : مفهوم المنهج الفعال في المنطق والرياضيات". ما وراء المنطق: مقدمة في نظرية ما وراء المنطق القياسي من الدرجة الأولى . مطبعة جامعة كاليفورنيا (نُشر عام 1973). ISBN 9780520023567. OCLC 36312727 . ( متاح للزبائن ذوي الإعاقات البصرية )
- ↑ إن مسألة ما إذا كانت العملية التي تتضمن عمليات داخلية عشوائية (باستثناء المدخلات) تُعتبر خوارزمية أم لا، أمرٌ قابل للنقاش. يرى روجرز أن: "الحساب يتم بطريقة منفصلة متدرجة، دون استخدام أساليب متصلة أو أجهزة تناظرية ... يتم تنفيذه بشكل حتمي، دون اللجوء إلى أساليب أو أجهزة عشوائية، مثل النرد" (روجرز 1987:2).
- ↑ غاندي، روبن (1980). "أطروحة تشيرش ومبادئ الآليات" . ندوة كلين . دراسات في المنطق وأسس الرياضيات. 101 : 123-148 . doi : 10.1016/S0049-237X(08)71257-6 . ISBN 978-0-444-85345-5تم الاطلاع عليه بتاريخ 19 أبريل 2024 .
- ↑ كوبلاند، بي جيه ؛ كوبلاند، جاك؛ براودفوت، ديان (يونيو 2000). "أطروحة تورينج-تشيرش" . AlanTuring.net . أرشيف تورينج لتاريخ الحوسبة . تم الاطلاع عليه بتاريخ 23 مارس 2013 .
- ↑ قاموس كامبريدج للفلسفة، الإجراء الفعال
- إس سي كلين (1967)، المنطق الرياضي . أعيد طبعه، دوفر، 2002، رقم ISBN 0-486-42533-9، الصفحات 233 وما بعدها، وخاصة الصفحة 231.
- ميتالوجيك
- نظرية الحوسبة
- نظرية الحوسبة