نماذج الحوسبة
تحدد العديد من الأطر الرسمية معنى الحوسبة، بدءًا من إعادة كتابة الدوال في حساب التفاضل والتكامل اللامدا (lambda calculus) وصولًا إلى الدوائر البوليانية والأنظمة الكمومية، وتكشف مقارنة قوتها عن النماذج المتكافئة وتلك التي تختلف اختلافًا جوهريًا.
Definition
نموذج الحوسبة هو إطار تجريدي دقيق يحدد العمليات المسموح بها وكيفية سير الحوسبة؛ قد تحسب النماذج المختلفة نفس الفئة من الدوال ولكنها تختلف في الإيجاز أو التوازي أو الموارد التي توضحها.
Scope
تغطي هذه المنطقة حساب التفاضل والتكامل اللامدا والنماذج الوظيفية، والدوال التكرارية وآلات السجل، والدوائر البوليانية وتعقيد الدوائر، والحوسبة الكمومية، مع دراسة كيفية تعبير كل نموذج عن الخوارزميات، وكيف ترتبط قوة قابليتها للحوسبة من خلال أطروحة تشرش-تورينج، وكيف يمكن أن تختلف كفاءتها.
Sub-topics
Core questions
- ما هي الطرق المختلفة لإضفاء الطابع الرسمي على مفهوم الحوسبة؟
- ما هي النماذج المتكافئة في الدوال التي يمكنها حسابها، ولماذا؟
- كيف تختلف النماذج عندما تصبح الكفاءة أو التوازي أو القابلية للتحقق المادي مهمة؟
- هل يمكن لنموذج ذي دوافع فيزيائية مثل الحوسبة الكمومية أن يتجاوز الكفاءة الكلاسيكية؟
Key theories
- التكافؤ بموجب أطروحة تشرش-تورينج
- يحسب حساب التفاضل والتكامل اللامدا، والدوال التكرارية، وآلات السجل، وآلات تورينج جميعها نفس الفئة من الدوال بالضبط، وهو التقارب الذي يؤسس لتحديد الحوسبة بقابلية تورينج للحوسبة.
- الاختلاف في الكفاءة
- يمكن أن تختلف النماذج المتفقة على قابلية الحوسبة بشكل حاد في الموارد: فالدوائر تكشف عن الحوسبة المتوازية وغير المنتظمة، ويبدو أن النماذج الكمومية توفر تسريعًا، لذا فإن اختيار النموذج مهم جدًا للتعقيد حتى لو لم يكن كذلك لقابلية الحوسبة.
Clinical relevance
توضح النماذج المختلفة جوانب متباينة من الحوسبة الحقيقية: فحساب التفاضل والتكامل اللامدا هو الأساس النظري للغات البرمجة الوظيفية، وتمثل الدوائر الأجهزة والحوسبة المتوازية، وتعكس آلات السجل المعالجات التقليدية، وتوجه النماذج الكمومية تصميم الأجهزة والخوارزميات الكمومية الناشئة.
History
في ثلاثينيات القرن الماضي، اقتُرح حساب التفاضل والتكامل اللامدا لتشرش، والدوال التكرارية لغودل وكليني، وآلات تورينج، ثم أُثبت تكافؤها. أضافت النماذج اللاحقة أبعادًا جديدة: فقد أضفى تعقيد الدوائر طابعًا رسميًا على الحوسبة المتوازية والأجهزة، وأدت مقترحات فاينمان عام 1982 لمحاكاة الكم إلى بزوغ نموذج الحوسبة الكمومية.
Key figures
- Alonzo Church
- Alan Turing
- Stephen Kleene
- Richard Feynman
Related topics
Seminal works
- church1936
- sipser2013
- aroraBarak2009
Frequently asked questions
- لماذا ندرس العديد من النماذج إذا كانت تحسب نفس الدوال؟
- التكافؤ ينطبق فقط على ما يمكن حسابه من حيث المبدأ. تجعل النماذج المختلفة أشياء مختلفة سهلة التعبير أو التحليل: يوضح حساب التفاضل والتكامل اللامدا البرمجة الوظيفية، وتكشف الدوائر عن التوازي وتكاليف الأجهزة، وتلتقط النماذج الكمومية الظواهر الفيزيائية، لذا فإن كل منها هو العدسة الصحيحة لأسئلة مختلفة.
- هل جميع نماذج الحوسبة متكافئة؟
- تحسب جميع النماذج الكلاسيكية المعقولة نفس الفئة من الدوال، مما يدعم أطروحة تشرش-تورينج. لكنها يمكن أن تختلف اختلافًا كبيرًا في الكفاءة، وقد تحل النماذج التي تستغل موارد مختلفة، مثل التراكب الكمومي، بعض المشكلات بشكل أسرع حتى أثناء حساب نفس الدوال.