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

يمكن حساب العدد π إلى دقة إعتباطية.

في الرياضيات، الأعداد القابلة للحساب (بالإنجليزية : Computable Numbers) هي الأعداد الحقيقية التي يمكن حسابها إلى أي دقة مُرادة بواسطة خوارزمية منتهية و محدودة. تُعرف أيضًا باسم الأعداد العودية.

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

تعريف غير رسمي باستخدام آلة تورينغ كمثال

في ما يلي، يعرف مارفن مينسكي الأعداد التي يمكن حسابها بطريقة مشابهة لتلك التي عرفها بها آلان تورنغ في عام 1936 ؛ أي، كـ «تسلسل من الأعداد يتم التعامل معه على أنه كسور عشرية» بين 0 و 1:

العدد القابل للحساب [هو] العدد الذي توجد له آلة تورينج، بحيث يتم إعطاؤها

$n$

على شريطها الأولي، وتعطي الرقم النوني

$n$

من ذلك الرقم [مشفراً على شريطها].

تعريف رسمي

يقال عن عدد حقيقي $a$ أنه قابل للحساب، إذا كان يمكن حساب قيمة تقديرية له عن طريق الدوال القابلة للحساب $f:\mathbb{N}\to \mathbb{Z}$ بالطريقة التالية: بالنظر إلى أي عدد صحيح موجب $n$، تعطي الدالة $f(n)$ عددًا صحيحًا بحيث :

$\frac{f(n)-1}{n}\le a\le \frac{f(n)+1}{n}.$

هناك تعريفان متشابهان، بحيث أنه إذا كان العدد $a$ قابلاً للحساب، فإنه يستوفي أحد هذه الشرطين :

• توجد دالة قابلة للحساب بحيث، بالنظر إلى أي عدد كسري موجب $\epsilon$ (يطلق على هذا العدد خطأ التقريب)، تعطي هذه الدالة عددًا كسرياً $r$ بحيث $|r-a|\le \epsilon .$
• هناك متتالية قابلة للحساب من الأعداد الكسرية $q_i$ تتقارب ل $a$، بحيث$|q_i-q_{i+1}|<2^{-i}$ لكل $i$ .

هناك تعريف آخر مكافئ للتعريفين السابقين، للأعداد القابلة للحساب عبر حد ديدكايند القابل للحساب. حد ديدكايند القابل للحساب هي دالة قابلة للحساب، يرمز لها ب$D$ والتي عند إعطائها عدد كسري $r$ تقوم بإخراج تعبيرين (صحيح أو خاطئ) $D(r)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$ أو $D(r)=\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}$.