الأعداد القابلة للحوسبة اصغر بشكل لانهائي من الاعداد الرياضية R
(ماخوذ من ورقة تورنغ Turing (1936), On Computable Numbers)
بحسب تورنغ
العدد القابل للتعريف هو اي عدد يمكننا وصفه وصفا لغوي او رياضي بشكل يميزه عن غيره
مثلا عندما اقول أصغر عدد صحيح موجب
(هذا تعريف لغوي لعدد 1)
او يقول قائل العدد الذي يمثل النسبه بين محيط الدائره وقطرها(هذا تعريف للعدد باي )
اما العدد القابل للحساب/للحوسبة
هو عدد توجد خوارزمية تستطيع إنتاج أرقامه
وكل عدد قابل للحساب يمكن تعريفه على الاقل من خلال وصف الآلة التي تحسبه
العدد الذي تنتجه الالة رقم كذا
لكن مفهوم العدد القابل للتعريف اعم من العدد القابل للحوسبة و قبل ان اتطرق للبرهان الذي أورده تورنغ فقط لنتذكر ان المجموعة تكون قابلة للعد countable اذا كان بامكان بناء دالة onto تقابل مجموعة N ¹ ( او بشكل مبسط اذا قدرت ترسم سهم بين عناصرها و بين عناصر مجموعة N )
الان نعرف ان مجموعة R تعتبر غير قابلة للعد( بسبب برهان كانتور ) ²
لكي نثبت ان الاعداد القابلة للحساب هي أصغر لنفرض انها Mn حيث تكون
Mn={m1, m2,....}
الان بحسب تعريف القابل للحساب اذن يوجد الة نرمز لها a تقابل كل عدد
فتكون
a1--m1
a2---m2
و هكذا( الصيغة هذه مختصرة و برهان المفصل في المصدر ³)
بالتالي مجموعة M قابلة للعد بالتالي هي اصغر من R وهذا يعني بشكل مبسط ان هنالك اعداد شبه لا نهائية لايمكن لاي خوارزمية ان تحسبهم
¹للتفصيل راجع understand anylsis فصل Cantor set
²نفس المصدر السابق
³ فيON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM , 241
