تشير أطروحة Church-Turing إلى مفهوم طريقة فعالة أو منهجية أو ميكانيكية في المنطق والرياضيات وعلوم الكمبيوتر. تمت صياغته على أنه وصف للمفهوم الحدسي للقدرة الحسابية ، وفيما يتعلق بالوظائف العودية العامة ، غالبًا ما يطلق عليه أطروحة الكنيسة. كما يشير إلى نظرية الوظائف الحاسوبية. ظهرت الأطروحة في ثلاثينيات القرن الماضي ، عندما لم تكن أجهزة الكمبيوتر نفسها موجودة بعد. سُميت لاحقًا على اسم عالم الرياضيات الأمريكي ألونسو تشيرش وزميله البريطاني آلان تورينج.
كفاءة الأسلوب في تحقيق النتيجة
أول جهاز يشبه الكمبيوتر الحديث كان Bombie ، وهي آلة ابتكرها عالم الرياضيات الإنجليزي آلان تورينج. تم استخدامه لفك رموز الرسائل الألمانية خلال الحرب العالمية الثانية. ولكن من أجل أطروحته وإضفاء الطابع الرسمي على مفهوم الخوارزمية ، استخدم آلات مجردة ، سميت فيما بعد بآلات تورينج. تقدم الأطروحةاهتمام علماء الرياضيات والمبرمجين على حد سواء ، لأن هذه الفكرة ألهمت مبدعي أجهزة الكمبيوتر الأولى.
في نظرية الحوسبة ، تُعرف أطروحة Church-Turing أيضًا باسم التخمين حول طبيعة الوظائف الحسابية. تنص على أنه بالنسبة لأي وظيفة قابلة للحساب حسابيًا على الأعداد الطبيعية ، هناك آلة تورينج قادرة على حسابها. أو بعبارة أخرى ، هناك خوارزمية مناسبة لها. أحد الأمثلة المعروفة لفعالية هذه الطريقة هو اختبار جدول الحقيقة لاختبار الحشو.
طريقة لتحقيق أي نتيجة مرغوبة تسمى "فعالة" أو "منهجية" أو "ميكانيكية" إذا:
- يتم تحديد الطريقة من حيث عدد محدد من التعليمات الدقيقة ، ويتم التعبير عن كل تعليمات باستخدام عدد محدود من الأحرف.
- سيتم تشغيله بدون أخطاء ، وسوف ينتج النتيجة المرجوة في عدد معين من الخطوات.
- الطريقة يمكن أن يقوم بها الإنسان دون مساعدة بأي معدات أخرى غير الورق والقلم الرصاص
- لا يتطلب فهمًا أو حدسًا أو براعة من جانب الشخص الذي يقوم بالعمل
في وقت سابق في الرياضيات ، تم استخدام المصطلح غير الرسمي "قابل للحساب بشكل فعال" للإشارة إلى الوظائف التي يمكن حسابها بالقلم الرصاص والورق. لكن فكرة الحوسبة الحسابية كانت أكثر سهولة من أي شيء ملموس. الآن تتميز بوظيفة ذات وسيطة طبيعية ، والتي توجد لها خوارزمية حسابية. كان أحد إنجازات آلان تورينجتمثيل المسند الدقيق رسميًا ، والذي يمكن من خلاله استبدال المسند غير الرسمي ، إذا تم استخدام شرط كفاءة الطريقة. قامت الكنيسة بنفس الاكتشاف.
المفاهيم الأساسية للوظائف العودية
تغيير تورينغ للمسندات ، للوهلة الأولى ، بدا مختلفًا عن ذلك الذي اقترحه زميله. لكن نتيجة لذلك ، تبين أنها متكافئة ، بمعنى أن كل واحد منهم يختار نفس مجموعة الوظائف الرياضية. أطروحة Church-Turing هي التأكيد على أن هذه المجموعة تحتوي على كل وظيفة يمكن الحصول على قيمها بطريقة تفي بشروط الكفاءة. كان هناك اختلاف آخر بين الاكتشافين. كان أن تشرش اعتبر فقط أمثلة على الأعداد الصحيحة الإيجابية ، بينما وصف تورينج عمله بأنه يغطي الوظائف الحسابية مع متغير حقيقي أو متكامل.
الدوال العودية الشائعة
تنص الصيغة الأصلية للكنيسة على أنه يمكن إجراء الحساب باستخدام حساب التفاضل والتكامل. هذا يعادل استخدام الوظائف العودية العامة. تغطي أطروحة Church-Turing أنواعًا من الحسابات أكثر مما كان يُعتقد في الأصل. على سبيل المثال ، المتعلقة بالأجهزة الخلوية والمجمعات وآلات التسجيل وأنظمة الاستبدال. في عام 1933 ، أنشأ عالم الرياضيات كورت جودل وجاك هيربراند تعريفًا رسميًا لفئة تسمى الوظائف العودية العامة. يستخدم دوال حيث يمكن استخدام أكثر من وسيطة.
إنشاء طريقةλ-حساب التفاضل والتكامل
في عام 1936 ، أنشأ ألونسو تشيرش طريقة تحديد تسمى حساب التفاضل والتكامل λ. كان مرتبطا بالأعداد الطبيعية. في حساب التفاضل والتكامل λ ، حدد العالم ترميزهم. نتيجة لذلك ، يطلق عليهم أرقام الكنيسة. كانت الوظيفة التي تعتمد على الأعداد الطبيعية تسمى λ-computable. كان هناك تعريف آخر. تسمى الوظيفة من أطروحة الكنيسة λ-computable تحت حالتين. الأول بدا على هذا النحو: إذا تم حسابه على عناصر الكنيسة ، وكان الشرط الثاني هو إمكانية تمثيله بواسطة عضو حساب التفاضل والتكامل.
أيضًا في عام 1936 ، قبل دراسة عمل زميله ، ابتكر تورينج نموذجًا نظريًا للآلات المجردة التي سميت الآن باسمه. يمكنهم إجراء العمليات الحسابية عن طريق التلاعب بالأحرف الموجودة على الشريط. ينطبق هذا أيضًا على الأنشطة الرياضية الأخرى الموجودة في علوم الكمبيوتر النظرية ، مثل الحوسبة الاحتمالية الكمية. تم إثبات الوظيفة من أطروحة تشيرش في وقت لاحق فقط باستخدام آلة تورينج. في البداية ، اعتمدوا على حساب التفاضل والتكامل.
حساب الوظيفة
عندما يتم تشفير الأرقام الطبيعية بشكل مناسب كتسلسل أحرف ، يُقال أن دالة على الأرقام الطبيعية قابلة للحساب من Turing إذا عثرت الآلة المجردة على الخوارزمية المطلوبة وطبعت هذه الوظيفة على شريط. مثل هذا الجهاز ، الذي لم يكن موجودًا في ثلاثينيات القرن الماضي ، سيعتبر في المستقبل جهاز كمبيوتر. بشرت آلة تورينج المجردة وأطروحة الكنيسة بعصر من التطورأجهزة الحوسبة. ثبت أن فئات الوظائف المحددة رسميًا من قبل كلا العالمين تتطابق. لذلك ، نتيجة لذلك ، تم دمج كلا العبارتين في واحد. كما كان للوظائف الحسابية وأطروحة الكنيسة تأثير قوي على مفهوم الحوسبة. كما أصبحت أداة مهمة للمنطق الرياضي ونظرية الإثبات.
مبررات ومشاكل الطريقة
هناك آراء متضاربة حول الأطروحة. تم جمع العديد من الأدلة لـ "فرضية العمل" التي اقترحها تشيرش وتورنج في عام 1936. لكن جميع الطرق أو العمليات المعروفة لاكتشاف وظائف جديدة قابلة للحساب بشكل فعال من وظائف معينة كانت مرتبطة بأساليب آلات البناء ، والتي لم تكن موجودة في ذلك الوقت. لإثبات أطروحة Church-Turing ، يبدأ المرء من حقيقة أن كل نموذج واقعي للحساب مكافئ.
نظرًا لتنوع التحليلات المختلفة ، يُعتبر هذا عمومًا دليلًا قويًا بشكل خاص. تبين أن كل المحاولات لتعريف أكثر دقة للمفهوم الحدسي لوظيفة قابلة للحساب بشكل فعال كانت مكافئة. لقد أثبت كل تحليل تم اقتراحه أنه يميز نفس فئة الوظائف ، أي تلك التي يمكن حسابها بواسطة آلات Turing. لكن تبين أن بعض النماذج الحسابية كانت أكثر كفاءة من حيث استخدام الوقت والذاكرة لمهام مختلفة. لاحقًا لوحظ أن المفاهيم الأساسية للوظائف العودية وأطروحة الكنيسة هي إلى حد ما افتراضية.
أطروحة م
من المهم التمييز بين أطروحة تورينج والتأكيد على أن أي شيء يمكن حسابه بواسطة جهاز كمبيوتر يمكن حسابه بواسطة جهازه. الخيار الثاني له تعريفه الخاص. يسمي غاندي الجملة الثانية "أطروحة م". يبدو الأمر على هذا النحو: "كل ما يمكن حسابه بواسطة جهاز يمكن حسابه بواسطة آلة Turing." بالمعنى الضيق للأطروحة ، فهي اقتراح تجريبي قيمته الحقيقية غير معروفة. أحيانًا يتم الخلط بين أطروحة تورينج و "الرسالة م". النسخة الثانية غير صحيحة على نطاق واسع. تم وصف العديد من الآلات الشرطية التي يمكنها حساب الوظائف التي لا يمكن حسابها بواسطة Turing. من المهم ملاحظة أن الأطروحة الأولى لا تستلزم الثانية بل تتفق مع زيفها.
التضمين العكسي للأطروحة
في نظرية الحوسبة ، تُستخدم أطروحة تشرش كوصف لمفهوم الحوسبة بواسطة فئة من الوظائف العودية العامة. أعطى الأمريكي ستيفن كلاين صيغة أكثر عمومية. دعا إلى التكرار الجزئي لجميع الوظائف الجزئية القابلة للحساب بواسطة الخوارزميات.
يشار إلى الضمني العكسي عادة بأطروحة الكنيسة العكسية. يكمن في حقيقة أن كل دالة عودية للأعداد الصحيحة الموجبة يتم تقييمها بكفاءة. بالمعنى الضيق ، تشير الأطروحة ببساطة إلى مثل هذا الاحتمال. وبمعنى أوسع ، فهي تستخلص من السؤال عما إذا كانت هذه الآلة الشرطية يمكن أن توجد فيها.
أجهزة الكمبيوتر الكمومية
أصبحت مفاهيم الوظائف الحسابية وأطروحة تشرش اكتشافًا مهمًا للرياضيات ونظرية الآلة والعديد من العلوم الأخرى. لكن التكنولوجيا تغيرت كثيرًا وتستمر في التحسن. من المفترض أن أجهزة الكمبيوتر الكمومية يمكنها أداء العديد من المهام الشائعة في وقت أقل من الأجهزة الحديثة. لكن تبقى الأسئلة ، مثل مشكلة التوقف. لا يستطيع الكمبيوتر الكمومي الإجابة عليها. ووفقًا لأطروحة Church-Turing ، لا يوجد أي جهاز كمبيوتر آخر أيضًا.
