بفضل تقنية الذكاء الاصطناعي، يمكن لأجهزة الكمبيوتر الحالية إجراء محادثات مقنعة مع البشر، وتأليف الأغاني، ورسم الصور، ولعب الشطرنج، والمعاشات، وتشخيص الأمراض، على سبيل المثال لا الحصر من براعتهم التكنولوجية.
يمكن استخدام هذه النجاحات للإشارة إلى أن الحساب ليس له حدود. لمعرفة ما إذا كان هذا هو الحال، من المهم أن نفهم ما الذي يجعل أجهزة الكمبيوتر قوية للغاية.
قوة الكمبيوتر لها جانبان: عدد العمليات في الثانية التي يمكن أن تؤديها أجهزته وكفاءة الخوارزميات التي يتم تشغيلها. سرعة الجهاز محدودة بقوانين الفيزياء. الخوارزميات - في الأساس مجموعات من التعليمات - يكتبها البشر وتُترجم إلى سلسلة من العمليات التي يمكن أن يؤديها الكمبيوتر. حتى لو وصلت تصل سرعات الكمبيوتر إلى الحدود المادية، ولا تزال الحواجز الحسابية قائمة بسبب القيود الحسابية.
تتراوح هذه العقبات من المشكلات التي لا تستطيع أجهزة الكمبيوتر حلها إلى المشكلات التي يمكن حلها نظريًا ولكنها تتعدى عمليًا قدرات أقوى إصدارات أجهزة الكمبيوتر الحالية. يحاول علماء الرياضيات وعلماء الكمبيوتر تحديد ما إذا كان من الممكن حل المشكلة عن طريق تجربتها على آلة خيالية.
آلة حوسبة خيالية
اقترح عالم الرياضيات البريطاني آلان تورينج فكرة حديثة لخوارزمية، تُعرف باسم آلة تورينج، في عام 1936. إنه جهاز افتراضي يحاكي كيفية إجراء العمليات الحسابية بقلم رصاص على الورق. آلات تورينج هي القالب الذي تعتمد عليه جميع أجهزة الكمبيوتر اليوم.
لاستيعاب العمليات الحسابية التي تتطلب المزيد من الورق عند إجرائها يدويًا، يُفترض أن التوفير الافتراضي للورق لآلة تورينج لا نهائي. يرقى هذا إلى عدد لا حصر له من الأشرطة أو المربعات الشريطية التي يمكن تخيلها، وكل منها إما فارغ أو يحتوي على رمز.
ما هي آلة تورينج؟
الآلة محكومة بمجموعة محدودة من القواعد وتبدأ تسلسلًا أوليًا للرموز على الشريط. العمليات التي يمكن أن تؤديها الآلة هي الانتقال إلى المربعات المجاورة، ومسح الرموز، وكتابة الرموز على المربعات الفارغة. تقوم الآلة بالحساب عن طريق إجراء سلسلة من هذه العمليات. عندما تنتهي الآلة أو تتوقف، فإن الرموز المتبقية على الشريط هي الإخراج أو النتيجة.
غالبًا ما تتعلق الحوسبة بالقرارات مع أو بدون إجابات. عن طريق القياس، يتحقق الاختبار الطبي (نوع السؤال) مما إذا كانت عينة المريض (مثال على السؤال) لها مؤشر مرض معين (نعم أم لا). مثال يتم تمثيله عدديًا في آلة تورينج هو التسلسل الأولي للرموز.
يُقال إن المشكلة قابلة للحل إذا كان من الممكن تصميم آلة تورينج للتوقف عند كل حالة موجبة أو سلبية وتحديد الإجابة التي ينتجها مثيل بشكل صحيح.
لا يمكن حل كل مشكلة
يمكن حل العديد من المشكلات باستخدام آلة Turing، وبالتالي على الكمبيوتر، بينما لا يمكن حل العديد من المشكلات الأخرى. على سبيل المثال، مشكلة الدومينو، وهي شكل من أشكال مشكلة البلاط اقترحها عالم الرياضيات الأمريكي الصيني هاو وانج في عام 1961، غير قابلة للحل.
تتمثل المهمة في تغطية الشبكة بالكامل بمجموعة من الدومينو، باتباع قواعد معظم ألعاب الدومينو، ومطابقة عدد الدومينو على الأطراف المجاورة من قطع الدومينو. اتضح أنه لا توجد خوارزمية يمكن أن تبدأ بمجموعة من الدومينو وتحدد ما إذا كانت مجموعة الدومينو تغطي الشبكة بالكامل.
إبقائها معقولة
يمكن أن تخرج مشكلة البائع المتجول عن السيطرة بسرعة عندما تسافر عبر عدة وجهات.
يمكن حل العديد من المشكلات القابلة للحل عن طريق الخوارزميات التي تتوقف في وقت معقول. تعد الخوارزميات متعددة الحدود خوارزميات فعالة، مما يعني أنه من العملي استخدام الكمبيوتر لحلها.
لا يُعرف أن آلاف المشكلات الأخرى القابلة للحل لها خوارزميات متعددة الحدود، على الرغم من الجهود المبذولة للعثور على مثل هذه الخوارزميات. من بينها مشكلة البائع المتجول.
تسأل مشكلة البائع المتجول ما إذا كانت مجموعة من النقاط (تسمى الرسم البياني) المرتبطة مباشرة ببعض النقاط لها مسار يبدأ من أي نقطة ويمر عبر جميع النقاط الأخرى مرة واحدة بالضبط، ويعود إلى النقطة الأصلية. تخيل بائعًا يريد أن يجد طريقًا يمر عبر جميع المنازل المجاورة مرة واحدة بالضبط ويعود إلى نقطة معينة بداية.
هذه المشاكل، المعروفة باسم NP-complete، تمت صياغتها وعرضها بشكل مستقل في أوائل السبعينيات من قبل اثنين من علماء الكمبيوتر، الكندي الأمريكي ستيفن كوك والأوكراني الأمريكي ليونيد ليفين. فاز Work-First Cook بجائزة Turing لعام 1982، وهي أعلى جائزة في علوم الكمبيوتر، هذا العمل.
تكلفة المعرفة بالضبط
تجد أشهر الخوارزميات لمشكلات NP-Complete أساسًا حلاً من جميع الإجابات الممكنة. سوف تستغرق مشكلة البائع المتجول على رسم بياني لبضع مئات من النقاط سنوات لتشغيلها على كمبيوتر عملاق. هذه الخوارزميات تفاعلية، مما يعني عدم وجود اختصارات رياضية.
يمكن أن توفر الخوارزميات العملية للتعامل مع هذه المشكلات في العالم الحقيقي تقديرات تقريبية فقط، على الرغم من تحسن التقديرات التقريبية. ما إذا كانت هناك خوارزمية متعددة الحدود فعالة يمكنها حل مشاكل NP الكاملة هي واحدة من ألغاز الألفية السبعة التي لم يتم حلها والتي نشرها معهد كلاي للرياضيات في مطلع القرن st، جائزة كل منها 1 مليون دولار.
ما وراء تورينج
هل هناك شكل جديد من أشكال الحوسبة خارج إطار عمل تورينج؟ في عام 1982، اقترح ريتشارد فاينمان، الفيزيائي الأمريكي الحائز على جائزة نوبل، فكرة الحوسبة على أساس ميكانيكا الكم.
في عام 1995، اقترح عالم الرياضيات التطبيقي الأمريكي بيتر شور خوارزمية كمومية تحلل الأعداد الصحيحة إلى زمن متعدد الحدود. يعتقد علماء الرياضيات أن هذا لا يمكن حله عن طريق خوارزمية متعددة الحدود في ظل إطار تورينج. تحليل عدد صحيح يعني إيجاد عدد صحيح أقل من 1 يقسم العدد الصحيح بالتساوي. علي سبيل المثال على سبيل المثال، العدد الصحيح 688،826،081 قابل للقسمة على العدد الصحيح الأصغر 25،253 لأن 688،826،081 = 25،253 × 27،277.
الخوارزمية الرئيسية المستخدمة على نطاق واسع لتأمين اتصالات الشبكة، والتي تسمى خوارزمية RSA، تعتمد على الصعوبة الحسابية لتحليل الأعداد الصحيحة الكبيرة. تظهر نتائج شور أنه إذا أصبحت الحوسبة الكمومية حقيقة واقعة، فيمكنها تغيير مشهد الأمن السيبراني.
هل يمكن بناء كمبيوتر كمي كامل لتحليل الأعداد الصحيحة وحل المشكلات الأخرى؟ يعتقد بعض العلماء أن هذا ممكن. يعمل العديد من فرق العلماء حول العالم على بناء واحد، وقد قام البعض بالفعل ببناء حواسيب كمومية صغيرة.
ومع ذلك، مثل جميع التقنيات الجديدة التي تم اختراعها من قبل، فمن شبه المؤكد ظهور مشاكل مع الحوسبة الكمومية ستقود آفاقًا جديدة.