دالة حسوبة

تعتبر ب هي مجال الدالة الحسوبة

ومن جهة أخرى، لأن كل علاقة منتهاه في الأرقام الطبيعية يمكن تعريفها بمجموعة مطابقة من السلاسل المتعاقبة من الأرقام الطبيعية، مفاهيم العلاقة الحسابية والعلاقة المتعددة حسابياً يمكن تعريفهم من المجموعات المتناظرة معها.

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

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

الحوسبة الفائقة

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

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

انظر كذلك

حسابات لامدا

آلات المشاركة (الآت تورنغ للمشاركة وآلات وضع العلامات)

نظرية العودة الأعلى

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

آلات التسجيل

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

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

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

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

التعريف

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

أمثلة

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

فرضية تورنغ – تشرتش

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

الدوال غير القابلة للحسب والمشاكل غير القابلة للحل

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

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

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

في هذا الإطار، لا يوجد نوذج أقوى للحساب والذي يعتبر بشكل عام جهاز حساب فعّال تم اقتراحه.

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

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

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

هوية بيزوت، معادلة ديوفانتين الخطية

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

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

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

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

وعلى صعيد آخر، الأمثلة التالية توضح أن الدالة قد تكون حسوبة من خلال أنها قد تكون غير معروفة أي خوارزمي هو المناسب لها.

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

اللغات الرسمية

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

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

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

المجموعات والعلاقات الحسابية

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

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

الحاسوبية النسبية

في هذا الإطار، فكرة حاسوبية الدالة هذه يمكن أن تكون نسبية لمجموعة تعسفية من الأرقام الطبيعية «أ»

كذلك، الدالة د تعرف على أنها حسوبة في «أ» (ويساوي: أ" –الحسابي، أو نسبي بالنسبة إلى «أ») عندما ترضي التعريف الخاص بالدالة الحاسوبية مع المعدلات التي تسمح بالوصول إلى «أ» كأوراكل. طبقاً لمفهوم الدالة الحسوبة يمكن إعطاء الدالة الحسوبة النسبية تعريفات مساويه على الكثير من النماذج المختلفة للحساب. وهذا عادةً ينفذ عن طريق إلحاق نموذج الحساب بعمليات أصلية إضافية والتي تسأل ما إذا كان عدد صحيح معين هو عنصر في «أ». يمكننا كذلك الحديث عن د وكونها حسوبة في ت عن طريق تعريف ت برسمها البياني.

صفات الدوال الحسوبة

من جهة ثانية، يستمر إندرتون بسرد توضيحات مختلفة لهذه المتطلبات للإجراء لدالة قابلة للحساب:

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

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

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

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

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

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

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

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

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

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