الكمبيوتر مفهوم مألوف يفهمه معظمنا بشكل حدسي. ضع في اعتبارك الدالة (f (x) = x + 3) ، حيث عندما تكون قيمة x تساوي ثلاثة (f (3) = 3 + 3) ، يصبح حل الدالة ستة.
من الواضح أن الوظيفة الموصوفة قابلة للحساب. لكن بعض الوظائف ليست بهذه البساطة وليس من السهل تحديد ما إذا كان من الممكن حسابها ، مما يعني أنها قد لا تعطينا الإجابة النهائية أبدًا.
في عام 1928 ، اقترح عالما الرياضيات الألمانيان ديفيد هيلبرت وويلهلم أكرمان مشكلة تسمى Entscheidungsproblem. بمرور الوقت ، أدت مشكلتهم إلى التعريف الرسمي للحوسبة ، مما سمح لعلماء الرياضيات بالإجابة على العديد من المشكلات الجديدة ووضع الأساس لعلوم الكمبيوتر النظرية.
وفقًا لمجلة Quanta Magazine ، كان التعريف المذكور أعلاه من بنات أفكار طالب يبلغ من العمر 23 عامًا يُدعى آلان تورينج ، والذي كتب ورقة بحثية أساسية في عام 1936 لم تضفي الطابع الرسمي على مفهوم الحساب فحسب ، بل أثبت أيضًا أنه سؤال أساسي في الرياضيات وأسس الأساس الفكري لاختراع الكمبيوتر الإلكتروني.
أراد تورينج إعطاء إجابة محددة للمشكلة الحسابية في شكل آلة مجردة. سميت هذه الآلة فيما بعد بآلة تورينج من قبل طالب الدكتوراه ألونزو تشيرش.
تعتبر آلة تورينج مفهومًا مجردًا لأنها غير موجودة (ولا يمكن) وجودها كجهاز ملموس ، وهي في الواقع نموذج مفاهيمي للحساب: إذا كان بإمكان الآلة حساب وظيفة ، فإن هذه الوظيفة قابلة للحساب أو قابلة للحساب. يتم شرح عمل آلة Turing أدناه.
يمكن لآلة تورينج قراءة الرموز ومعالجتها على شريط طويل بلا حدود وفقًا لجدول القواعد. يتكون الشريط من منازل ، يمكن لكل منها تخزين شخصية ، وتقرأ الآلة وتكتب فوق محتويات كل منزل برأس الشريط.
تحدد كل قاعدة في الجدول ما يجب أن يفعله الجهاز بناءً على حالته الحالية والشخصية التي يقرأها. قد تدخل الآلة في حالة طرفية (حالة القبول أو حالة الرفض) ثم تتوقف أو تقبل الإدخال أو ترفضه ، أو قد تدخل في حلقة لا نهائية وتستمر في قراءة الشريط إلى الأبد.
أفضل طريقة لفهم آلة تورينج هي إلقاء نظرة على مثال بسيط. تخيل آلة مصممة لتخبرنا ما إذا كان أحد المدخلات صفرًا أم لا.
لتوضيح ذلك ، نستخدم رقم الإدخال 0001 جنبًا إلى جنب مع الرمز (#) (# 0001 #) ، لذلك # 0001 # هو الحقل المطلوب على الشريط.
يبدأ الجهاز في الحالة الأولية ، والتي نسميها q0. تبدأ الآلة من أقصى اليسار على الشريط وتنتقل إلى الرمز # (مع وجود الأرقام بالداخل). تنص القواعد على أنه عندما تكون في الحالة q0 ، إذا كان هناك حرف # ، فتجاهله ، وانقل خلية واحدة إلى اليمين ، وقم بتغيير حالة الجهاز إلى q1. بعد هذه الخطوة ، تكون الآلة في حالة q1 ويقرأ رأسها الحرف الثاني ، أي 0.
الآن نبحث عن قاعدة تنطبق على هذا الشرط ونجد قاعدة تنص على: البقاء في q1 وتحريك الرأس إلى الخلية اليمنى. هذا يجعلنا نبقى في نفس الموقف (في الوضع q1 ، قراءة 0). لذلك نستمر في التحرك إلى اليمين حتى يقرأ الرأس أخيرًا رقمًا مختلفًا ، 1. عندما نتحقق من الجدول مرة أخرى ، نكتشف قاعدة جديدة: إذا واجهت 1 ، فانتقل إلى الحالة q2 ، وهي حالة رفض. تتوقف الآلة وتجيب بـ “لا” على السؤال الأولي “هو 0001 صفر”.
ولكن إذا كان الإدخال # 0000 # ، فسيواجه الجهاز # بعد كل هذه الأصفار. عندما نفحص الجدول ، نجد قاعدة تقول إن هذا يعني أن الآلة تدخل الحالة q3 ، حالة القبول. يجيب الجهاز الآن بنعم على السؤال عما إذا كان 0000 هو صفر.
ساعد آلان تورينج في تعريف الحساب والخوارزميات وما أصبح يعرف باسم آلة تورينج.
باستخدام آليته المجردة ، ابتكر تورينج نموذجًا حسابيًا للإجابة على مشكلة القرار ، والتي تطرح السؤال التالي: بالنظر إلى مجموعة من المبادئ الرياضية ، هل هناك عملية ميكانيكية (مجموعة من التعليمات نسميها الآن خوارزمية) تحدد دائمًا حقيقة اقتراح محدد؟
لنفترض أننا نريد إيجاد خوارزمية يمكنها أن تخبرنا ما إذا كان وضع شطرنج معين ممكنًا أم لا. هنا قواعد الشطرنج تحكم التحركات المسموح بها. هل يمكننا اتباع تسلسل محدود خطوة بخطوة من الطرق للوصول إلى الموضع المطلوب؟
على الرغم من أن بعض المواقف قد تستغرق أكثر من عمرنا لتحليلها (يمكن لخوارزمية أن تولد جميع المواقف الممكنة ومقارنة كل منها بالمدخلات) ، فإن مثل هذه الخوارزمية موجودة في لعبة الشطرنج. لذلك نقول إن الشطرنج “قابل للحل”.
ومع ذلك ، في عام 1936 ، أثبتت تشيرش وتورنج بشكل مستقل (باستخدام طرق مختلفة) أنه لا يوجد حل عام لجميع الحالات المحتملة لمشكلة القرار. على سبيل المثال ، لا يمكن حل بعض الألعاب مثل لعبة الحياة التي صممها جون هورتون كونواي. لا يمكن لأي خوارزمية تحديد ما إذا كان نمط معين سينبثق من النمط الأولي أم لا.
أظهر تورينج أن الوظيفة قابلة للحساب إذا كانت هناك خوارزمية يمكنها أداء المهمة المطلوبة. وفي الوقت نفسه ، أوضح أن الخوارزمية هي عملية يمكن تحديدها بواسطة آلة تورينج. لذلك ، فإن الوظيفة القابلة للحساب هي وظيفة توجد بها آلة تورينج. قد يبدو هذا التعريف وكأنه طريقة معقدة لتعريف الحوسبة ، لكنه أفضل تعريف لدينا. يقول مايكل سيبسر ، عالم الكمبيوتر النظري في معهد ماساتشوستس للتكنولوجيا: “لا توجد طريقة أخرى لتعريفه”. أعتقد أنه من المقبول عمومًا أن أطروحة تشيرش تورينج تقول أن المفهوم غير الرسمي للخوارزمية يتوافق مع ما يمكن أن يفعله أي نموذج حسابي معقول. »
توصل علماء رياضيات آخرون إلى نماذج مختلفة من الحسابات تبدو مختلفة تمامًا على السطح ، ولكنها في الواقع متكافئة: يمكنهم إجراء أي حساب يمكن لآلات تورينج إجراؤه ، والعكس صحيح.
بعد سنوات قليلة فقط من إثبات كيرت جودل أن الرياضيات غير كاملة ، أظهر تشرش وتورنج أن بعض المشكلات في الرياضيات غير قابلة للحل وأنه لا توجد خوارزمية ، مهما كانت معقدة ، يمكنها أن تخبرنا ما إذا كانت الإجابة بنعم أم لا.
اعتبرت كلتا الحالتين بمثابة ضربة قاتلة لهيلبرت ، الذي كان يأمل أن يكون للرياضيات إجابات واضحة وخالية من العيوب. إذا كان هناك حل عام لمشكلة الحل ، فهذا يعني أنه يمكن اختزال المشكلات الرياضية بأكملها إلى حسابات ميكانيكية بسيطة.
بالإضافة إلى الإجابة على هذه الأسئلة الأساسية ، فإن آلة تورينج تؤدي أيضًا بشكل مباشر إلى بناء أجهزة كمبيوتر حديثة من خلال إصدار يسمى “آلة تورينج العامة”.
آلة Turing العامة هي نوع خاص من آلات Turing التي يمكنها محاكاة أي آلة Turing أخرى بناءً على أي إدخال. يمكن لهذا الإصدار من آلة Turing قراءة أوصاف آلات Turing الأخرى (قواعدها وشرائط الإدخال) ومحاكاة سلوكها على شريط الإدخال الخاص بها وإنتاج نفس المخرجات التي تنتجها الآلة المحاكاة ؛ تمامًا مثل أجهزة الكمبيوتر الحالية ، يمكنها قراءة أي برنامج وتنفيذه.
في عام 1945 ، اقترح جون فون نيومان نوعًا من هندسة الكمبيوتر يسمى هندسة فون نيومان ، والتي طبقت مفهوم آلة تورينج العالمية في آلة حقيقية.
عندما يقوم سانجيف أرورا ، عالم الكمبيوتر النظري بجامعة برينستون ، بتدريس هذا المفهوم ، فإنه يؤكد على صورة فلسفية أكبر. يشرح قائلاً: “هناك معنيان لكلمة” العالمية “. أحد المفاهيم العالمية هو أنه يمكن تنفيذ أي آلة تورينج أخرى. “لكن المعنى الأوسع لـ” عالمي “هو أنه يمكنه إجراء أي عملية حسابية يمكنك التفكير فيها.”
في عالم الفيزياء الكلاسيكية ، يمكن نمذجة أي عملية فيزيائية أو محاكاتها باستخدام الخوارزميات ، والتي بدورها يمكن محاكاتها بواسطة آلة تورينج.
نوع آخر ملحوظ وأكثر فائدة لآلة تورينج هو “آلة تورينج الاحتمالية”. على عكس آلة تورينج العادية ، التي لها استجابة محددة لكل إدخال ، يمكن أن يكون لآلة تورينج الاحتمالية عدة استجابات بناءً على الاحتمالات. هذا يعني أن الآلة يمكن أن تنتج مخرجات مختلفة لنفس المدخلات في أوقات مختلفة. ومن المثير للاهتمام ، أن هذا النوع من الاستراتيجية الاحتمالية يمكن أن يكون أكثر كفاءة من النهج الحتمي الكامل لبعض المشاكل.
أصبحت فكرة آلات تورنج الاحتمالية مفيدة في مجالات مثل التشفير والتحسين والتعلم الآلي. ربما تكون هذه الآلات المجردة أفضل دليل حتى الآن على أن طرح الأسئلة الأساسية يمكن أن يكون أحد أكثر الأشياء المفيدة التي يمكن للعالم القيام بها.
5858
.