books computable function
If you do not find what you're looking for, you can use more accurate words.
دالة قابلة للحساب (Info)
الدوال الحسابية (بالإنجليزية: Computable function) هي المواد الأساسية في دراسة النظرية الحسابية. الدوال الحسابية هي التماثلية الرسمية للفكرة البديهية للخوارزمية. . وهي تستخدم لمناقشة الحسابية دون الإشارة إلى أي نموذج ملموس من الحساب مثل آلات تورنغ أو آلات التسجيل. ورغم ذلك فإن أي تعريف يجب أن يكون له مرجعية لبعض النماذج المحددة من الحساب ولكن كل التعريفات الصحيحة تحقق نفس الدرجة من الوظائف. نماذج معينة من الحاسوبية التي تؤدي إلى مجموعة من الوظائف الحسابية هي دوال تورنغ الحسابية ودوال المايكرو المتكررة. قبل التعريف الدقيق للدالة الحسابية، غالباً ما كان يستخدم علماء الرياضيات المصطلح غير الرسمي محسوب بشكل فعّال. لقد أصبح هذا المصطلح منذ ذلك الحين معرّف بالدوال الحسابية. لاحظ أن الحاسوبية الفعّآلة لهذه الدوال لا تدل على أنه يمكن حسابهم بطريقة فعّآلة (بمعنى: يتم حسابهم في قدر معقول من الوقت). في الحقيقة، بالنسبة لبعض الدوال المحسوبة بشكل فعّال فهي قد تظهر أن أي خوارزمية تقوم بحسابهم سوف لن تكون فعّآلة في إدراك أن الوقت المنصرم من الخوارزمية يزيد باطراد ( أو حتى باطراد مضاعف) مع مدة المدخلات. مجالات الحاسوبية العملية و التعقيد الحسابي تدرس الدوال التي قد تكون محسوبة بشكل فعّال.
طبقاً لفرضية تورنغ-الكنيسة، فإن الدوال الحسابية هم بالضبط الدوال التي من الممكن أن يتم حسابها باستخدام أداة حساب ميكانيكية بفرض وجود كمية غير محدودة من الوقت ومساحة التخزين. بالمقابل، وتنص هذه الفرضية على أن أي دالة التي لها خوارزمية يمكن حسابها. لاحظ أن الخوارزمية في هذا المعنى تُفهم على أنها سلسلة متعاقبه من الخطوات التي يمكن لشخص لديه وقت غير محدود وإمداد غير منتهي من الأقلام والأوراق أن يتبعها. يمكن استخدام بديهية بلام لتعريف النظرية المجردة للتعقيد الحاسوبي على مجموعة من الدوال حسابية. في نظرية التعقيد الحاسوبي، مشكلة تحديد تعقيد الدالة المحسوبة يعرف بمشكلة الدالة.
التعريف
يمكن تعريف طبقة الدوال الحسابية بكثير من النماذج المساوية، وتشمل:
تستخدم فرضية تشرتش-تورنغ أحياناً في إثبات استيفاء أن دالة معينة قابلة للحساب عن طريق منحها وصف ملموس لإجراءات الحسابية.
الدوال غير القابلة للحسب والمشاكل غير القابلة للحل
كل دالة حسابية لها إجراءات متناهيه لتعطي تعليمات واضحة وصريحة عن كيفية حسابها. علاوة على ذلك، هذه الأجراءات يجب أن ترمز في الأبجدية المتناهية المستخدمة في النموذج الحاسوبي، لذلك فهناك فقط دوال عديدة قابلة للحسب. على سبيل المثال، قد تكون الدوال مرمزة باستخدام سلسلة من الأجزاء (الأبجدية={1,0} ∑). الأرقام الحقيقية لا تعد لذلك فمعظم الأرقام الحقيقية ليست حسابية. انظر الأرقام الحسابية. مجموعة الدوال المنتهاة في الأعداد الطبيعية غير معدودة لذلك معظمها ليست حسابية. أمثلة ملموسة على هذه الدوال مثل بوزي بايفر، تعقيد كولموجوروف أو أي دالة تكون مخرجاتها أرقام غير حسابية مثل ثابت تشيتيني.
وبالمثل، معظم المجموعات الثانوية من الأرقام الطبيعية ليست حسابية. كانت مشكلة التوقف هي الأولى في إنشاءها. مشكلة إنستشيدانجز، المقترحة من دافيد هيلبرت، حيث سأل إذا ما كان هناك إجراء فعال لتحديد أي من البيانات الرياضية صحيحة (المرمزه كأرقام طبيعية). تورنغ والكنيسة أظهرت بشكل مستقل في الثلاثينات أن هذه المجموعة من الأعداد الطبيعية ليست حسابية. طبقاً لفرضية تورنغ-الكنيسة، لا توجد إجراءات فعالة (باستخدام الخوارزميه) يمكنها عمل هذه الحسابات.
امتدادات الحاسوبية
الحاسوبية النسبية
فكرة حاسوبية الدالة هذه يمكن أن تكون نسبية لمجموعة تعسفية من الأرقام الطبيعية "أ" الدالة د تعرف على أنها الحسابية في "أ" (ويساوي: أ" –الحسابي، أو نسبي بالنسبة إلى "أ") عندما ترضي التعريف الخاص بالدالة الحاسوبية مع المعدلات التي تسمح بالوصول إلى "أ" كأوراكل. طبقاً لمفهوم الدالة الحسابية يمكن إعطاء الدالة الحسابية النسبية تعريفات مساويه على العديد من النماذج المختلفة للحساب. وهذا عادةً ينفذ عن طريق إلحاق نموذج الحساب بعمليات أصلية إضافية والتي تسأل ما إذا كان عدد صحيح معين هو عنصر في "أ" . يمكننا أيضاً الحديث عن د وكونها حسابية في ت عن طريق تعريف ت برسمها البياني .
نظرية العودة الأعلى
نظرية العلم الفوق راضي تدرس هذه المجموعات التي يمكن حسابها من عدد حسابي ترتيبي من إعادات قفز تورنغ من المجموعة الخالية. هذا يكافئ المجموعات المعرفة عن طريق كلاً من المعادلات العامة و الوجودية في اللغة من الأمر الثاني الحسابي ولبعض النماذج من الفوق كومبيوتر. لجعلها أكثر شمولية فإن نظريات العودة يتم تدريسها، مثل نظرية التواتر الإلكتروني والتي أي مجموعة بها يمكن استخدامها كوسيط لدالة التواتر الإلكتروني.
الحوسبة الفائقة
على الرغم من أن فرضية الكنيسة- تورنغ ذكرت أن الدوال الحسابية تشمل كل الدوال مع الخوارزمي، فمن المحتمل أن نعتبر الطبقات الواسعة من الدوال والتي تريح المتطلبات التي يجب أن تحصلها الخوارزمية. إن مجال الفوق حاسوبية يدرس نماذج من الحساب والتي تتخطى حساب تورنغ الطبيعي. هذا لا يخرق فرضية الكنيسة –تورنغ حيث أنهم يسمحون بالعمليات التي، إذا حدث أو لم يحدث تطبيقهم بجهاز فيزيائي، لا يمكن آدائوها بعمل البشر عن طريق قلم و ورقة.
