الحوسبة الفائقة

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

تنص أطروحة تشيرش -تورنج على أن أي دالة "قابلة للحساب" يمكن حسابها بواسطة عالم رياضيات بقلم وورقة باستخدام مجموعة محدودة من الخوارزميات البسيطة، يمكن حسابها بواسطة آلة تورنج. تحسب أجهزة الكمبيوتر الفائقة الوظائف التي لا تستطيع آلة تورنج القيام بها، وبالتالي فهي غير قابلة للحساب وفقًا لمفهوم تشيرش-تورنج.

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

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

بمعنى ما، فإن معظم الوظائف غير قابلة للحساب: هناك وظائف قابلة للحساب، ولكن هناك عدد لا يحصى ( ) من وظائف تورينج الفائقة المحتملة. ^[3]${\displaystyle \aleph _{0}}$${\displaystyle 2^{\aleph _{0}}}$

تتراوح نماذج الحاسوب الفائق من تلك المفيدة ولكن ربما لا يمكن تحقيقها (مثل آلات أوراكل الأصلية لتورنج)، إلى مولدات الوظائف العشوائية الأقل فائدة والتي يمكن "تحقيقها" بشكل أكثر منطقية (مثل آلة تورنج العشوائية ).

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

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

• آلات أوراكل الأصلية لتورنج، والتي حددها تورنج في عام 1939.
• يمكن لجهاز كمبيوتر حقيقي (نوع من الكمبيوتر التناظري المثالي ) إجراء عمليات حسابية فائقة ^[4] إذا كانت الفيزياء تقبل المتغيرات الحقيقية العامة (وليس فقط الأعداد الحقيقية القابلة للحساب )، وهذه المتغيرات يمكن "تسخيرها" بطريقة ما للحسابات المفيدة (وليس العشوائية). قد يتطلب هذا قوانين فيزيائية غريبة جدًا (على سبيل المثال، ثابت فيزيائي قابل للقياس بقيمة أوراكلية، مثل ثابت تشايتن )، وسيتطلب القدرة على قياس القيمة الفيزيائية ذات القيمة الحقيقية بدقة تعسفية، على الرغم من أن الفيزياء القياسية تجعل مثل هذه القياسات ذات الدقة التعسفية غير قابلة للتنفيذ نظريًا. ^[5]
  • على نحو مماثل، فإن الشبكة العصبية التي تحتوي بطريقة ما على ثابت تشايتن مضمنًا تمامًا في دالة الوزن الخاصة بها ستكون قادرة على حل مشكلة التوقف، ^[6] ولكنها تخضع لنفس الصعوبات الفيزيائية مثل النماذج الأخرى للحوسبة الفائقة القائمة على الحوسبة الحقيقية.
• يمكن لبعض "آلات تورينج الضبابية" القائمة على المنطق الضبابي ، بحكم التعريف، حل مشكلة التوقف عن طريق الخطأ، ولكن فقط لأن قدرتها على حل مشكلة التوقف مفترضة بشكل غير مباشر في مواصفات الآلة؛ ويميل هذا إلى النظر إليه باعتباره "خطأ" في المواصفات الأصلية للآلات. ^{[7] [8]}
  • على نحو مماثل، يمكن للنموذج المقترح المعروف باسم عدم التحديد العادل أن يسمح عن طريق الخطأ بالحساب الوهمي للوظائف غير القابلة للحساب، لأن بعض هذه الأنظمة، بحكم التعريف، لديها القدرة الوهمية على تحديد المدخلات المرفوضة التي من شأنها أن تتسبب "بشكل غير عادل" في تشغيل نظام فرعي إلى الأبد. ^{[9] [10]}
• اقترح دميتري تارانوفسكي نموذجًا محدودًا لفروع التحليل غير المحدودة تقليديًا، مبنيًا حول آلة تورينج المجهزة بدالة متزايدة بسرعة كعراف لها. من خلال هذا النموذج وغيره من النماذج الأكثر تعقيدًا، كان قادرًا على تقديم تفسير للحساب من الدرجة الثانية. تتطلب هذه النماذج مدخلات غير قابلة للحساب، مثل عملية توليد حدث فيزيائي حيث ينمو الفاصل الزمني بين الأحداث بمعدل كبير لا يمكن حسابه. ^[11]
  • على نحو مماثل، يفترض أحد التفسيرات غير التقليدية لنموذج عدم التحديد غير المحدود ، بحكم التعريف، أن طول الوقت المطلوب لـ "الفاعل" للاستقرار غير قابل للمعرفة بشكل أساسي، وبالتالي لا يمكن إثبات، داخل النموذج، أنه لا يستغرق فترة طويلة غير قابلة للحساب. ^[12]

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

آلة تورينج التي يمكنها إكمال عدد لا نهائي من الخطوات في وقت محدود، وهو إنجاز يُعرف باسم المهمة الفائقة . إن مجرد القدرة على الركض لعدد غير محدود من الخطوات لا يكفي. أحد النماذج الرياضية هو آلة زينو (مستوحاة من مفارقة زينو ). تقوم آلة زينو بتنفيذ أول خطوة حسابية لها في (على سبيل المثال) دقيقة واحدة، والخطوة الثانية في ½ دقيقة، والخطوة الثالثة في ¼ دقيقة، وهكذا. من خلال جمع 1 + ½ + ¼ + ... ( سلسلة هندسية ) نرى أن الآلة تقوم بعدد لا نهائي من الخطوات في إجمالي دقيقتين. وفقًا لأورون شاجرير ، فإن آلات زينو تقدم مفارقات فيزيائية وحالتها غير محددة منطقيًا خارج فترة مفتوحة من جانب واحد من [0، 2)، وبالتالي غير محددة بالضبط بعد دقيقتين من بداية الحساب. ^[13]

يبدو من الطبيعي أن إمكانية السفر عبر الزمن (وجود منحنيات زمنية مغلقة (CTCs)) تجعل الحوسبة الفائقة ممكنة في حد ذاتها. ومع ذلك، هذا ليس صحيحًا لأن CTC لا توفر (بحد ذاتها) كمية غير محدودة من التخزين التي تتطلبها الحوسبة اللانهائية. ومع ذلك، هناك أزمنة مكانية يمكن فيها استخدام منطقة CTC للحوسبة الفائقة النسبية. ^[14] وفقًا لورقة بحثية عام 1992، ^[15] يمكن لجهاز كمبيوتر يعمل في زمكان مالامينت-هوجارث أو في مدار حول ثقب أسود دوار ^[16] أن يقوم نظريًا بإجراء حسابات غير تورينج لمراقب داخل الثقب الأسود. ^{[17] [18]} قد يسمح الوصول إلى CTC بالحل السريع لمشاكل PSPACE-complete ، وهي فئة تعقيد، على الرغم من إمكانية حلها وفقًا لتورينج، إلا أنها تعتبر عمومًا مستعصية على الحل من الناحية الحسابية. ^{[19] [20]}

يفترض بعض العلماء أن النظام الميكانيكي الكمومي الذي يستخدم بطريقة ما تراكبًا لا نهائيًا للحالات يمكنه حساب دالة غير قابلة للحساب . ^[21] هذا غير ممكن باستخدام الكمبيوتر الكمومي القياسي ذي نموذج البت الكمومي ، لأنه ثبت أن الكمبيوتر الكمومي العادي قابل للاختزال بواسطة PSPACE (يمكن محاكاة الكمبيوتر الكمومي الذي يعمل في زمن متعدد الحدود بواسطة كمبيوتر كلاسيكي يعمل في فضاء متعدد الحدود ). ^[22]

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

في منتصف ستينيات القرن العشرين، اقترح إي مارك جولد وهيلاري بوتنام بشكل مستقل نماذج للاستدلال الاستقرائي ("الدوال التكرارية المحدودة" ^[23] و"تنبؤات التجربة والخطأ" ^[24] على التوالي). تمكن هذه النماذج من "تعلم" بعض المجموعات غير التكرارية من الأرقام أو اللغات (بما في ذلك جميع مجموعات اللغات القابلة للعد التكراري )؛ في حين أنه بحكم التعريف، لا يمكن التعرف إلا على مجموعات التكرار من الأرقام أو اللغات بواسطة آلة تورينج. وبينما ستستقر الآلة على الإجابة الصحيحة على أي مجموعة قابلة للتعلم في وقت محدود، إلا أنها لا تستطيع تحديدها على أنها صحيحة إلا إذا كانت متكررة؛ وإلا، فإن الصحة لا يتم إثباتها إلا من خلال تشغيل الآلة إلى الأبد وملاحظة أنها لا تعدل إجابتها أبدًا. حدد بوتنام هذا التفسير الجديد باعتباره فئة من المسندات "التجريبية"، قائلًا: "إذا "افترضنا" دائمًا أن الإجابة التي تم إنشاؤها مؤخرًا صحيحة، فسنرتكب عددًا محدودًا من الأخطاء، لكننا سنحصل في النهاية على الإجابة الصحيحة. (لاحظ، مع ذلك، أنه حتى إذا وصلنا إلى الإجابة الصحيحة (نهاية التسلسل المحدود) فلن نكون متأكدين أبدًا من أن لدينا الإجابة الصحيحة.)" ^[24] درست ورقة LK Schubert لعام 1974 "التكرار المحدود المتكرر ومشكلة تقليل البرنامج" ^[25] تأثيرات تكرار إجراء التحديد؛ وهذا يسمح بحساب أي مسند حسابي . كتب شوبرت، "بشكل حدسي، يمكن اعتبار تحديد التحديد المحدود المتكرر استدلالًا استقرائيًا من الدرجة الأعلى يتم إجراؤه بشكل جماعي من قبل مجتمع متزايد النمو من آلات الاستدلال الاستقرائي من الدرجة الأدنى."

يمكن حساب تسلسل الرموز في الحد إذا كان هناك برنامج محدود وربما غير متوقف على آلة تورينج عالمية تنتج بشكل تدريجي كل رمز من التسلسل. يتضمن هذا التوسع الثنائي لـ π وكل عدد حقيقي آخر قابل للحساب ، لكنه لا يزال يستبعد جميع الأعداد الحقيقية غير القابلة للحساب. لا يمكن لـ "آلات تورينج أحادية النغمة" المستخدمة تقليديًا في نظرية حجم الوصف تعديل مخرجاتها السابقة؛ يمكن لآلات تورينج المعممة، كما حددها يورجن شميدهوبر ، أن تفعل ذلك. وهو يعرف تسلسلات الرموز القابلة للوصف بشكل بناء على أنها تلك التي تحتوي على برنامج محدود وغير متوقف يعمل على آلة تورينج معممة، بحيث يتقارب أي رمز إخراج في النهاية؛ أي أنه لا يتغير بعد فترة زمنية أولية محدودة. نظرًا للقيود التي أظهرها كورت جودل لأول مرة (1931)، فقد يكون من المستحيل التنبؤ بوقت التقارب نفسه بواسطة برنامج متوقف، وإلا يمكن حل مشكلة التوقف . يستخدم شميدهوبر ( ^{[26] [27]} ) هذا النهج لتحديد مجموعة الأكوان التي يمكن وصفها رسميًا أو حسابها بشكل بناء أو النظريات البناءة لكل شيء . يمكن لآلات تورينج المعممة أن تتقارب في النهاية إلى حل صحيح لمشكلة التوقف من خلال تقييم تسلسل سبيكر .

إن العديد من مقترحات الحوسبة الفائقة ترقى إلى طرق بديلة لقراءة دالة أوراكل أو نصيحة مضمنة في آلة كلاسيكية بخلاف ذلك. تسمح مقترحات أخرى بالوصول إلى مستوى أعلى من التسلسل الهرمي الحسابي . على سبيل المثال، ستكون آلات تورينج فائقة المهام، وفقًا للافتراضات المعتادة، قادرة على حساب أي مسند في درجة جدول الحقيقة التي تحتوي على أو . على النقيض من ذلك، يمكن للتكرار المحدود حساب أي مسند أو دالة في درجة تورينج المقابلة ، والتي يُعرف أنها . أظهر جولد أيضًا أن التكرار الجزئي المحدود سيسمح بحساب المسندات بدقة. ${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle \Delta _{2}^{0}}$${\displaystyle \Sigma _{2}^{0}}$

نموذج	مسندات قابلة للحساب	ملحوظات	مراجع
المهام الفائقة	${\displaystyle \operatorname {tt} \left(\Sigma _{1}^{0},\Pi _{1}^{0}\right)}$	تعتمد على مراقب خارجي	[28]
الحد/المحاولة والخطأ	${\displaystyle \Delta _{2}^{0}}$		[23]
الحد المتكرر ( k مرة)	${\displaystyle \Delta _{k+1}^{0}}$		[25]
آلة بلوم-شوب-سمال		لا يمكن مقارنتها بالوظائف الحقيقية القابلة للحساب التقليدية	[29]
فضاء الزمان مالامينت-هوجارث	إتش واي بي	تعتمد على بنية الزمكان	[30]
الشبكة العصبية المتكررة التناظرية	${\displaystyle \Delta _{1}^{0}[f]}$	f هي دالة نصيحة تعطي أوزان الاتصال؛ الحجم محدود بوقت التشغيل	[31] [32]
آلة تورينج ذات الزمن اللانهائي	${\displaystyle مؤشر جودة الهواء}$	المجموعات شبه الاستقرائية الحسابية	[33]
آلة تورينج الضبابية الكلاسيكية	${\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}}$	لأي معيار t قابل للحساب	[8]
دالة متزايدة أوراكل	${\displaystyle \Delta _{1}^{1}}$	بالنسبة لنموذج التسلسل الواحد؛ يتم إعادة ${\displaystyle \Pi _{1}^{1}}$	[11]

في كتاباته عن الحوسبة الفائقة، ^{[34] [35] يشير} مارتن ديفيس إلى هذا الموضوع باعتباره "أسطورة" ويقدم حججًا مضادة لإمكانية تحقيق الحوسبة الفائقة ماديًا. أما بالنسبة لنظريتها، فهو يجادل ضد الادعاءات القائلة بأن هذا مجال جديد تأسس في تسعينيات القرن العشرين. وتعتمد وجهة النظر هذه على تاريخ نظرية قابلية الحساب (درجات عدم القدرة على الحل، وقابلية الحساب على الوظائف، والأعداد الحقيقية والترتيبية)، كما ذكر أعلاه أيضًا. في حجته، يدلي بملاحظة مفادها أن كل الحوسبة الفائقة ليست أكثر من: " إذا سُمح بالمدخلات غير القابلة للحساب، فيمكن تحقيق المخرجات غير القابلة للحساب " . ^[36]

• الفيزياء الرقمية
• حدود الحساب

• عون، ماريو أنطوان (2016). "التقدم في ثلاثة نماذج للحوسبة الفائقة" (PDF) . المجلة الإلكترونية للفيزياء النظرية . 13 (36): 169-182. مؤرشف من الأصل (PDF) في 2017-02-06 . تم الاسترجاع 2023-07-28 .
• بورجين، إم إس (1983). "آلات تورينج الاستقرائية". إشعارات أكاديمية العلوم في الاتحاد السوفييتي . 270 (6): 1289-1293.
• بورجين، مارك (2005). خوارزميات فائقة التكرار . دراسات في علوم الكمبيوتر. سبرينغر. رقم ISBN 0-387-95569-0.
• كوكشوت، ب.؛ مايكلسون، ج. (2007). "هل هناك نماذج جديدة للحوسبة؟ رد على ويجنر وإيبرباخ". مجلة الكمبيوتر . doi :10.1093/comjnl/bxl062.
• كوبر، إس بي؛ أوديفريدي، بي. (2003). "عدم قابلية الحساب في الطبيعة" (ملف PDF) . في كوبر، إس بي؛ جونشاروف، إس إس (المحرران). قابلية الحساب والنماذج: وجهات نظر الشرق والغرب . نيويورك، بوسطن، دوردرخت، لندن، موسكو: بلينوم للنشر. ص 137-160. مؤرشف من الأصل (ملف PDF) في 2011-07-24 . تم الاسترجاع في 2011-06-16 .
• كوبر، إس بي (2006). "قابلية التعريف كتأثير حسابي فائق". الرياضيات التطبيقية والحوسبة . 178 : 72-82. CiteSeerX  10.1.1.65.4088 . doi :10.1016/j.amc.2005.09.072. S2CID  1487739.
• كوبلاند، ج. (2002). "الحوسبة الفائقة" (PDF) . العقول والآلات . 12 (4): 461-502. doi :10.1023/A:1021105915386. S2CID  218585685. مؤرشف من الأصل (PDF) في 2016-03-14.
• هاجر، أ.؛ كوروليف، أ. (2007). "الحوسبة الكمومية الفائقة - مبالغة أم حسابية؟*" (PDF) . فلسفة العلوم . 74 (3): 347-363. doi :10.1086/521969. S2CID  9857468.
• أورد، توبي (2002). "الحوسبة الفائقة: الحوسبة أكثر مما تستطيع آلة تورينج حسابه: مقالة استطلاعية حول أشكال مختلفة من الحوسبة الفائقة". arXiv : math/0209332 .
• Piccinini, Gualtiero (16 يونيو 2021). "الحوسبة في الأنظمة الفيزيائية". موسوعة ستانفورد للفلسفة . تم استرجاعه في 2023-07-31 .
• شارما، آشيش (2022). "خوارزميات مستوحاة من الطبيعة بمنظور حسابي عشوائي فائق". علوم المعلومات . 608 : 670-695. doi :10.1016/j.ins.2022.05.020. S2CID  248881264.
• ستانيت، مايك (1990). "آلات إكس ومشكلة التوقف: بناء آلة تورينج فائقة". الجوانب الرسمية للحوسبة . 2 (1): 331-341. doi : 10.1007/BF01888233 . S2CID  7406983.
• Stannett, Mike (2006). "The case for hypercomputation" (PDF) . Applied Mathematics and Computation . 178 (1): 8–24. doi :10.1016/j.amc.2005.09.067. مؤرشف من الأصل (PDF) في 2016-03-04.
• سيروبولوس، أبوستولوس (2008). الحوسبة الفائقة: الحوسبة ما وراء حاجز الكنيسة-تورينج . سبرينغر. رقم ISBN 978-0-387-30886-9.