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

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

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

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

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

يمكن استخدام بديهيات بلوم لتعريف نظرية التعقيد الحسابي المجردة على مجموعة الدوال القابلة للحساب. في نظرية التعقيد الحسابي، تُعرف مشكلة حساب قيمة دالة ما بمشكلة دالة ، وذلك على عكس مشاكل القرار التي تكون نتائجها إما "نعم" أو "لا".

قابلية حساب الدالة مفهوم غير رسمي. إحدى طرق وصفه هي القول بأن الدالة قابلة للحساب إذا أمكن الحصول على قيمتها من خلال إجراء فعال . وبدقة أكبر، فإن الدالة${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ تكون قابلة للحساب إذا كان هناك إجراء فعال يقوم، بالنظر إلى أي مجموعة من k عنصر${\displaystyle \mathbf {x} }$من الأعداد الطبيعية، سينتج القيمة${\displaystyle f(\mathbf {x} )}$[ ^{1 ]} بالاتفاق مع هذا التعريف، يفترض الجزء المتبقي من هذه المقالة أن الدوال القابلة للحساب تأخذ عددًا محدودًا من ^{الأعداد} الطبيعية كوسائط وتنتج قيمة هي عدد طبيعي واحد.

إلى جانب هذا الوصف غير الرسمي، توجد تعريفات رياضية رسمية متعددة. يمكن تعريف فئة الدوال القابلة للحساب في العديد من نماذج الحساب المكافئة ، بما في ذلك

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

على الرغم من أن هذه النماذج تستخدم تمثيلات مختلفة للدوال ومدخلاتها ومخرجاتها، إلا أن هناك ترجمات بين أي نموذجين، وبالتالي فإن كل نموذج يصف أساسًا نفس فئة الدوال، مما يُرسخ الرأي القائل بأن قابلية الحساب الرسمية أمر طبيعي وغير ضيق للغاية. ^{[ 2 ]} يُشار إلى هذه الدوال أحيانًا باسم "الدوال التكرارية"، تمييزًا لها عن المصطلح غير الرسمي "قابلة للحساب"، ^{[ 3 ]} وهو تمييز نابع من نقاش دار عام 1934 بين كلين وغودل . ^{[ 4 ] : ​​6}

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

بصورة مكافئة، يمكن صياغة الدوال القابلة للحساب على أنها دوال يمكن حسابها بواسطة عامل حاسوبي مثالي مثل آلة تورينج أو آلة تسجيل . وبعبارة أخرى، الدالة الجزئية${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$يمكن حساب ذلك إذا كان هناك برنامج حاسوبي بالخصائص التالية:

1. لو${\displaystyle f(\mathbf {x} )}$إذا تم تعريفها، فسيتوقف البرنامج عند المدخلات${\displaystyle \mathbf {x} }$بقيمة${\displaystyle f(\mathbf {x} )}$مخزنة في ذاكرة الحاسوب.
2. لو${\displaystyle f(\mathbf {x} )}$إذا كانت القيمة غير مُعرَّفة، فلن يتوقف البرنامج أبدًا عند المدخلات.${\displaystyle \mathbf {x} }$.

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

يقدم إندرتون [1977] الخصائص التالية لإجراء حساب دالة قابلة للحساب؛ وقد قدم تورينج [1936] وروجر [1967] وغيرهم توصيفات مماثلة.

• يجب أن تتضمن العملية تعليمات دقيقة (أي برنامجًا) محددة الطول. لذا، يجب أن يكون لكل دالة قابلة للحساب برنامج محدد يصف بدقة كيفية حسابها. ويمكن حساب الدالة باتباع التعليمات فقط، دون الحاجة إلى تخمين أو فهم خاص.
• إذا أُعطيت العملية مجموعة من k عناصر x في مجال الدالة f ، فبعد عدد محدود من الخطوات المنفصلة، ​​يجب أن تنتهي العملية وتُنتج f ( x ). وبشكل بديهي، تسير العملية خطوة بخطوة، مع قاعدة محددة تُغطي ما يجب فعله في كل خطوة من خطوات الحساب. ولا يمكن تنفيذ سوى عدد محدود من الخطوات قبل إرجاع قيمة الدالة.
• إذا أُعطيت العملية مجموعةً من k عناصر x لا تنتمي إلى مجال الدالة f ، فقد تستمر العملية إلى ما لا نهاية دون توقف. أو قد تتعثر عند نقطة ما (أي لا يمكن تنفيذ إحدى تعليماتها)، ولكن لا يجوز لها أن تدّعي إنتاج قيمة لـ f عند x . وبالتالي، إذا تم العثور على قيمة لـ f ( x )، فلا بد أنها القيمة الصحيحة. ليس من الضروري أن يُميّز العامل الحسابي بين النتائج الصحيحة والخاطئة، لأن العملية تُعرَّف بأنها صحيحة إذا وفقط إذا أنتجت نتيجة.

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

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

باختصار، بناءً على هذا الرأي، تكون الدالة قابلة للحساب إذا:

يعمل مجال دراسات التعقيد الحسابي ضمن حدود محددة للوقت و/أو المساحة المسموح بها في عملية حسابية ناجحة.

تُسمى مجموعة A من الأعداد الطبيعية قابلة للحساب (مرادفات: قابلة للتكرار ، قابلة للتقرير ) إذا كانت هناك دالة كلية قابلة للحساب f بحيث يكون لأي عدد طبيعي n ، f ( n ) = 1 إذا كان n في A و f ( n ) = 0 إذا لم يكن n في A.

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

• B هو مجال دالة قابلة للحساب.
• B هو مدى دالة قابلة للحساب كليًا. إذا كانت B لانهائية، فيمكن افتراض أن الدالة أحادية .

إذا كانت المجموعة B هي مدى الدالة f، فيمكن اعتبار الدالة بمثابة تعداد لـ B ، لأن القائمة f (0)، f (1)، ... ستتضمن كل عنصر من عناصر B.

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

في نظرية الحوسبة في علوم الحاسوب ، من الشائع دراسة اللغات الرسمية . الأبجدية هي مجموعة اختيارية. الكلمة في الأبجدية هي سلسلة منتهية من الرموز من تلك الأبجدية؛ ويمكن استخدام الرمز نفسه أكثر من مرة. على سبيل المثال، السلاسل الثنائية هي الكلمات الموجودة في الأبجدية {0، 1 }. اللغة هي مجموعة جزئية من مجموعة جميع الكلمات في أبجدية ثابتة. على سبيل المثال، مجموعة جميع السلاسل الثنائية التي تحتوي على 3 آحاد بالضبط هي لغة على الأبجدية الثنائية.

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

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

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

• كل دالة ذات مجال محدود ؛ على سبيل المثال، أي سلسلة محدودة من الأعداد الطبيعية.
• كل دالة ثابتة f  : N ^k → N ، f ( n ₁ ،... n _k )  := n .
• الجمع f  : N ² → N ، f ( n ₁ ، n ₂ )  := n ₁ + n ₂
• القاسم المشترك الأكبر لعددين
• معامل بيزو لعددين
• أصغر عامل أولي لعدد

إذا كانت الدالتان f و g قابلتين للحساب، فإن الدالتين f + g و f * g قابلتان للحساب أيضاً .${\displaystyle \color {Blue}f\circ g}$إذا كانت f أحادية ، فإن max( f , g ), min( f , g ), arg max { y ≤ f ( x )} والعديد من التركيبات الأخرى.

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

• الدالة f التي تحقق الشرط f ( n ) = 1 إذا وُجدت متتالية من n على الأقل من الخمسات المتتالية في التمثيل العشري للعدد π ، و f ( n ) = 0 فيما عدا ذلك، قابلة للحساب. (الدالة f إما أن تكون دالة ثابتة قيمتها 1، وهي قابلة للحساب، أو أن هناك قيمة k تحقق الشرط f ( n ) = 1 إذا كان n < k و f ( n ) = 0 إذا كان n ≥ k . كل دالة من هذا النوع قابلة للحساب. من غير المعروف ما إذا كانت هناك سلاسل طويلة من الخمسات في التمثيل العشري للعدد π، لذا لا نعرف أيًّا من هاتين الدالتين هي f . مع ذلك، نعلم أن الدالة f يجب أن تكون قابلة للحساب.)
• كل جزء محدود من متتالية غير قابلة للحساب من الأعداد الطبيعية (مثل دالة بيزي بيفر Σ) قابل للحساب. على سبيل المثال، لكل عدد طبيعي n ، توجد خوارزمية لحساب المتتالية المحدودة Σ(0)، Σ(1)، Σ(2)، ...، Σ( n ) - على عكس عدم وجود خوارزمية لحساب متتالية Σ كاملة ، أي Σ( n ) لجميع قيم n . بالتالي، فإن "اطبع 0، 1، 4، 6، 13" هي خوارزمية بسيطة لحساب Σ(0)، Σ(1)، Σ(2)، Σ(3)، Σ(4)؛ وبالمثل، لأي قيمة معطاة لـ n ، توجد خوارزمية بسيطة كهذه (حتى وإن لم تُعرف أو تُنتج من قِبل أحد) لحساب Σ(0)، Σ(1)، Σ(2)، ...، Σ( n ).

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

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

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

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

مجموعة الدوال الكلية القابلة للإثبات قابلة للتعداد التكراري : يمكن تعداد جميع الدوال الكلية القابلة للإثبات بتعداد جميع البراهين المقابلة لها، والتي تثبت قابليتها للحساب. ويمكن القيام بذلك بتعداد جميع براهين نظام البرهان وتجاهل البراهين غير ذات الصلة.

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

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

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

• عدد قابل للحساب
• طريقة فعالة
• نظرية الحوسبة
• نظرية التكرار
• درجة تورينج
• التسلسل الهرمي الحسابي
• الحوسبة الفائقة
• خوارزمية فائقة التكرار
• دالة شبه قابلة للحساب

• كاتلاند، نايجل. قابلية الحوسبة . مطبعة جامعة كامبريدج، 1980.
• إندرتون، إتش بي. عناصر نظرية الاستدعاء الذاتي. دليل المنطق الرياضي (نورث هولاند 1977) ص  527-566.
• روغرز، هـ. نظرية الدوال المتكررة والحساب الفعال (مكجرو هيل 1967).
• تورينج، أ. (1937)، حول الأعداد القابلة للحساب، مع تطبيق على مسألة القرار . وقائع الجمعية الرياضية بلندن ، السلسلة 2، المجلد 42 (1937)، ص 230-265. أعيد طبعه في م. ديفيس (محرر)، غير القابل للتقرير ، دار رافين للنشر، هيوليت، نيويورك، 1965.