التحليل القابل للحساب

آلة تورينج من النوع 2 هي آلة تورينج بثلاثة أشرطة: شريط إدخال، وهو للقراءة فقط؛ وشريط عمل، يمكن الكتابة عليه والقراءة منه؛ والأهم من ذلك، شريط إخراج، وهو "للإضافة فقط".

في هذا السياق، تُمثَّل الأعداد الحقيقية بسلاسل لا نهائية عشوائية من الرموز. يمكن لهذه السلاسل، على سبيل المثال، أن تُمثِّل أرقام عدد حقيقي. لا يشترط أن تكون هذه السلاسل قابلة للحساب - وهذه الحرية مهمة وغير إشكالية من الناحية الفلسفية. ^{[ 2 ]} تجدر الإشارة إلى أن البرامج التي تعمل على هذه السلاسل يجب أن تكون قابلة للحساب بشكل معقول.

في حالة الأعداد الحقيقية، لا تُعدّ التمثيلات العشرية أو الثنائية المعتادة مناسبة. بدلاً من ذلك، يُستخدم غالبًا تمثيل الأرقام المُوقّعة الذي اقترحه براور لأول مرة: نظام الأعداد أساسه 2، لكن الأرقام هي${\displaystyle {\overline {1}}}$(يمثل)${\displaystyle -1}$)، 0 و1. وهذا يعني على وجه الخصوص${\displaystyle 1/2}$يمكن تمثيل كليهما على النحو التالي${\displaystyle 0.1}$و${\displaystyle 1.{\overline {1}}}$.

لفهم سبب عدم ملاءمة الترميز العشري، انظر إلى مشكلة الحساب${\displaystyle z=x+y}$أين${\displaystyle x=0.(3)}$و${\displaystyle y=0.(6)}$وإعطاء النتيجة${\displaystyle z}$بالصيغة العشرية. قيمة${\displaystyle z}$إما${\displaystyle 0.(9)}$أو${\displaystyle 1.(0)}$إذا تم إعطاء النتيجة الأخيرة على سبيل المثال، فسيكون هناك عدد محدود${\displaystyle n}$من أرقام${\displaystyle x}$سيتم قراءتها قبل اختيار الرقم${\displaystyle 1}$قبل الفاصلة العشرية في${\displaystyle z}$— ولكن إذا كان${\displaystyle n+1}$الرقم رقم من${\displaystyle x}$تم تخفيضها إلى 2، ثم النتيجة لـ${\displaystyle z}$سيكون ذلك خطأً. وبالمثل، فإن الخيار الأول${\displaystyle 0.(9)}$ل${\displaystyle z}$قد يكون مخطئاً أحياناً. هذه هي معضلة صانع الطاولات في جوهرها .

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

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

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

إن قابلية الحساب من النوع 1 هي الشكل الساذج للتحليل القابل للحساب حيث يتم تقييد المدخلات إلى الآلة لتكون أرقامًا قابلة للحساب بدلاً من الأرقام الحقيقية العشوائية.

يكمن الفرق بين النموذجين في أن البرنامج الذي يتصرف بشكل جيد على الأعداد القابلة للحساب (بمعنى كونه كليًا) ليس بالضرورة أن يتصرف بشكل جيد على الأعداد الحقيقية العشوائية. على سبيل المثال، توجد دوال قابلة للحساب على الأعداد الحقيقية القابلة للحساب تربط بعض الفترات المغلقة المحدودة بفترات مفتوحة غير محدودة. ^{[ 3 ]} لا يمكن توسيع هذه الدوال لتشمل الأعداد الحقيقية العشوائية (دون جعلها جزئية)، كما هو الحال مع جميع الدوال القابلة للحساب.${\displaystyle \mathbb {R} \to \mathbb {R} }$إذا كانت متصلة، فإن هذا من شأنه أن يخالف نظرية القيمة القصوى . ولأن هذا النوع من السلوك قد يُعتبر شاذًا، فمن الطبيعي التأكيد على أن الدالة لا تُعتبر كلية إلا إذا كانت كلية على جميع الأعداد الحقيقية، وليس فقط على الأعداد القابلة للحساب.

في حال عدم الرضا عن استخدام آلات تورينج (لأنها منخفضة المستوى وعشوائية إلى حد ما)، يوجد مفهوم قابلية التحقق يُسمى مفهوم كلين -فيسلي، والذي يُمكن من خلاله اختزال التحليل الحسابي إلى تحليل بنائي . يشمل هذا التحليل البنائي كل ما هو صحيح في مدرسة براور، وليس فقط مدرسة بيشوب . ^{[ 4 ]} إضافةً إلى ذلك، تنص إحدى نظريات هذه المدرسة من التحليل البنائي على أن ليس كل الأعداد الحقيقية قابلة للحساب ، وهو ما يُناقض بنائيًا وجود أعداد غير قابلة للحساب . وبالتالي، تتعارض هذه المدرسة من التحليل البنائي تناقضًا مباشرًا مع مدارس التحليل البنائي الأخرى - مثل مدرسة ماركوف - التي تدّعي أن جميع الدوال قابلة للحساب. في النهاية، يُظهر هذا أن الوجود البنائي ، وإن كان يستلزم قابلية الحساب، إلا أنه في الواقع ليس من الإشكالي - بل من المفيد - التأكيد على أن ليس كل دالة قابلة للحساب.