دالة قابلة للحساب

يمكن تعريف طبقة الدوال الحسابية بكثير من النماذج المساوية، وتشمل:

• آلات تورنغ
• دوال ماكرو المتكررة
• حسابات لامدا
• آلات المشاركة (الآت تورنغ للمشاركة وآلات وضع العلامات)
• آلات التسجيل

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

الدالة التي تعرف بالنسبة لكل الوسائط المتاحة تدعى مجموع. إذا كانت دالة حسابية هي مجموع، فهي تدعى دالة مجموع حسابية أو دالة مجموع متكررة. الملحوظة د(س1,.......سط) ↓تدل على أن الدالة الجزئية د معرّفة في الوسائط س1,.......سط والملحوظة د(س1,.......سط) = ص تدل على أن د معرّفه في الوسائط س1,.......سط وأن القيمة العائدة هي ص. في حالة أن الدالة د غير معرفه للوسائط س1,.......سط يرمز لها بأن( س1,.......سط) ↑

الصفة الأساسية للدالة الحسابية هي أنه يجب أن يوجد إجراء متناهي (خواريزم) ليخبرنا كيف يمكننا حساب الدالة. نماذج الحساب المذكورة أعلاه تعطي تفسيرات مختلفة لما يكونه الإجراء وكيف يستخدم، ولكن هذه التفسيرات تشترك في الكثير من الخصائص. حقيقة أن هذه النماذج تعطي طبقات متساوية لمنبع الدوال الحسابية من حقيقة أن كل نموذج قادر على قراءة ومحاكاة إجراء ما لأي من النماذج الأخرى، مثل المحوّل البرمجي فهو قادر على قراءة التعليمات بلغة كومبيوتر واحدة ويقذف بالتعليمات في لغة أخرى. إندرتون [1977] يعطي الخصائص التالية للإجراء لحساب دالة حسابية، وقد منحت صفات مشابهة عن طريق تورنغ [1936] روجرز [1967] وغيرهم.

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

• إذا كان الإجراء معطى ط-توبل س في المجال د ثم بعد عدد معين من الخطوات المنفصلة فيجب على الإجراء أن ينتهي وينتج د(س).

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

• إذا كان الإجراء معطى ط-توبل س وهو ليس في المجال د، ثم قد تستمر الإجراءات إلى الأبد، ولا تتوقف. أو قد تلتصق ببعض النقاط، ولكنها لا يجب أن تتظاهر إنتاج قيمة من د عند س.

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

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

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

• تعتبر ب هي مجال الدالة الحسابية
• تعتبر ب هي مدى الدالة الحسابية الكلية. إذا كانت ب غير منتهية فتكون الدالة يمكن افتراض أنها دخيلة.

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

طبقاً للنظرية الحاسوبية في علوم الكومبيوتر، من الشائع أن تراعي اللغات الرسمية. يعتبر الحرف مجموعة تعسفية. تعتبر كلمة في حرف سلسلة متناهيه من الرموز من الحروف، وقد يستخدم نفس الرمز أكثر من مرة. على سبيل المثال، الحروف الثنائية هي تماماً الكلملت بالحروف {0,1}. اللغة هي مجموعة ثانوية من مجموع كل الكلمات في حرف ثابت. على سبيل المثال، مجموع كل الحروف الثنائية والذي يحتوي بالضبط على ثلاثة حروف هي لغة فوق الحروف الثنائية. أهم خصائص اللغة الرسمية هي مستوى الصعوبة المطلوب لنقرر ما إذا كانت كلمة معينة موجودة في اللغة. يجب تطوير بعض أنظمة التكويد أو الترميز لتسمح لدالة حسابية بأن تأخذ كلمة تعسفية في اللغة كمدخل، وهذا في الغالب يعتبر روتيناً. تسمى اللغة حسابية (مرادف: متكررة، حاسمه) إذا كان هناك دالة حسابية د والتي تكون لكل كلمة ت فوق الحرف، د(ت)=1إذا كانت الكلمة موجودة في اللغة ود(ت)=0 إذا لم تكن الكلمة موجودة في اللغة. وهكذا، تحسب اللغة فقط في حالة أنه يوجد إجراء قادر على إخبارنا بشكل صحيح عن ما إذا كانت الكلمات التعسفية موجودة في اللغة. تكون اللغة متعددة حسابياً (مرادف: متعددة بشكل متكرر، شبه حاسمة) إذا كانت توجد دالة حسابية د مثل هذه د(ت) تكون معرفة عندما وفقط عندما تكون الكلمة ت موجودة في اللغة. المصطلح متعددة له نفس علم الكلمة كما في مجموعة متعددة حسابياً من الأعداد الطبيعية.

الدوال التالية حسابية:

• كل دالة لها مجال متناهي، مثل: أي ترتيب متناهي للأعداد الطبيعية.
• كل دالة ثابتة د: رط← ر، د(ر1......رط) = ر
• بالإضافة إلى د: ر2← ر، د(ر1 +ر2) = ر1 +ر2
• الدالة التي تعطي قائمة بالعناصر الأولية للرقم
• أعظم تقسيم شائع لرقمين هو الدالة الحسابية
• هوية بيزوت، معادلة ديوفانتين الخطية

لو كانت د وق حسابيتين، إذاً فهم: د + ق، د * ق، إذا كانت د هي الأعداد الأحادية، أقصاها (د، ق) أدناها (د، ق) ووسيط أعظم {ع>= د(س)} والمزيد من الاتحادات. الأمثلة التالية توضح أن الدالة قد تكون حسابية من خلال أنها قد تكون غير معروفة أي خوارزمي هو المناسب لها.

• الدالة د حيث د(ر) = 1 إذا كان هناك تتابع لخمسات ر المتتالية في الدالة العشرية المتوسعة في ط، ود(ر) = 0 وغير ذلك فهو حسابي. ( الدالة د إما أن تكون ثابتة على دالة 1، وهو حسابي، ومن المعروف، أو غير ذلك هو ط مثل د(ر) = 1 إذا كانت ر<ط ود(ر) = 0 إذا كانت ر<= ط. كل دالة كهذه تعتبر حسابية. من غير المعروف ما إذا كان هناك أمد طويل متعسف من الخمسات في التوسع العشري من باي، حيث أننا لا نعلم أي من هذه الدوال هي د.

ومع ذلك، نعلم أن الدالة د يجب أن تكون حسابية)

• كل قطاع متناهي من التسلسل الغير حسابي للأعداد الطبيعية (مثل دالة البوزي بيفور∑) يكون حسابياً. مثال: لكل رقم طبيعي ر، توجد خوارزمية والتي تحسب الترتيب المنتهي 0∑، 1∑، 3∑،...، (ر) ∑

فيما يتناقض مع الحقيقة التي تقول أنه لا يوجد خوارزمية لحساب الترتيب الكامل، ترتيب∑، بمعنى: (ر) ∑ لجمع قيم (ر). وبالتالي، فإن طباعة 0، 1، 4، 6، 13 هي خوارزمية عادية لحساب 0∑، 1∑، 3∑،4∑، وبالمثل لأي قيمة معطاة من ر، توجد خوارزمية عادية مثل هذه (رغم ذلك قد لا يعرف بوجودها أحد ولا يستخدمها أحد ) لحساب 0∑، 1∑، 3∑،...، (ر) ∑

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

• العديد من النماذج المكآفأه للحساب معروفة، وجميعهم يقدمون نفس التعريف للدالة الحسابية (أو نسخة أضعف في بعض الحالات).
• لا يوجد نوذج أقوى للحساب والذي يعتبر بشكل عام جهاز حساب فعّال تم اقتراحه.

تستخدم فرضية تشرتش-تورنغ أحياناً في إثبات استيفاء أن دالة معينة قابلة للحساب عن طريق منحها وصف ملموس لإجراءات الحسابية.

كل دالة حسابية لها إجراءات متناهيه لتعطي تعليمات واضحة وصريحة عن كيفية حسابها. علاوة على ذلك، هذه الأجراءات يجب أن ترمز في الأبجدية المتناهية المستخدمة في النموذج الحاسوبي، لذلك فهناك فقط دوال عديدة قابلة للحسب. على سبيل المثال، قد تكون الدوال مرمزة باستخدام سلسلة من الأجزاء (الأبجدية={1,0} ∑). الأرقام الحقيقية لا تعد لذلك فمعظم الأرقام الحقيقية ليست حسابية. انظر الأرقام الحسابية. مجموعة الدوال المنتهاة في الأعداد الطبيعية غير معدودة لذلك معظمها ليست حسابية. أمثلة ملموسة على هذه الدوال مثل بوزي بايفر، تعقيد كولموجوروف أو أي دالة تكون مخرجاتها أرقام غير حسابية مثل ثابت تشيتيني.

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

• النظرية الحسابية

• Enderton, H.B. Elements of recursion theory. Handbook of Mathematical Logic (North-Holland 1977) pp. 527–566.
• Rogers, H. Theory of recursive functions and effective computation (McGraw-Hill 1967).
• آلان تورنغ (1936), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936). Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.

• بوابة علم الحاسوب
• بوابة رياضيات
• بوابة تقنية المعلومات
• بوابة منطق