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

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

العدد القابل للحساب [هو] العدد الذي توجد له آلة تورينج، بحيث يتم إعطاؤها ${\displaystyle n}$ على شريطها الأولي، وتعطي الرقم النوني ${\displaystyle n}$ من ذلك الرقم [مشفراً على شريطها].

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

${\displaystyle {f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}.}$

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

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

هناك تعريف آخر مكافئ للتعريفين السابقين، للأعداد القابلة للحساب عبر حد ديدكايند القابل للحساب. حد ديدكايند القابل للحساب هي دالة قابلة للحساب، يرمز لها ب${\displaystyle D\;}$ والتي عند إعطائها عدد كسري ${\displaystyle r}$ تقوم بإخراج تعبيرين (صحيح أو خاطئ) ${\displaystyle D(r)=\mathrm {true} \;}$ أو ${\displaystyle D(r)=\mathrm {false} \;}$.

• بوابة رياضيات