Product Design, Manufacturing & Innovation Resources
بيت » اكتمال تورينج

اكتمال تورينج

1936
  • Alan Turing
مختبر علوم الكمبيوتر الذي يعرض اكتمال تورينج في لغات البرمجة.

(صورة تم إنشاؤها للتوضيح فقط)

نظام من قواعد معالجة البيانات، مثل لغة البرمجةتُعتبر لغة تورينج كاملة إذا استطاعت محاكاة أي آلة تورينج أحادية الشريط. وهذا يعني أنها لغة شاملة حسابيًا، ويمكن استخدامها لحل أي مسألة قابلة للحساب، إذا توفر لها الوقت والذاكرة الكافيان. معظم لغات البرمجة العامة كاملة تورينج، مما يشكل الأساس النظري لقدرتها التعبيرية.

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

تتمثل المتطلبات الأساسية لكي يكون النظام كاملاً تورينجياً في التفرع الشرطي (مثل عبارات if-then-else) والقدرة على التكرار اللانهائي أو التكراري (مثل حلقات while وfor). تسمح هذه البنى للنظام باتخاذ القرارات وتكرار العمليات، وهو ما يكفي لنمذجة سلوك انتقالات الحالة ومعالجة الشريط في آلة تورينج. تنص فرضية تشيرش-تورينج، وهي مبدأ أساسي في علوم الحاسوب، على أن أي دالة تُعتبر بطبيعتها "قابلة للحساب" يمكن حسابها بواسطة آلة تورينج. لذلك، فإن اللغة الكاملة تورينجياً، نظرياً، قادرة على التعبير عن أي خوارزمية.

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

UNESCO Nomenclature: 1202
- علوم الحاسب الآلي

يكتب

النظام التجريدي

الاضطراب

تزايدي

الاستخدام

الاستخدام الواسع النطاق

السلائف

  • Kurt Gödel’s work on incompleteness theorems
  • تطوير ألونزو تشيرش لحساب التفاضل والتكامل لامدا
  • برنامج ديفيد هيلبرت لإضفاء الطابع الرسمي على الرياضيات
  • يعود مفهوم الخوارزمية إلى العصور القديمة

التطبيقات

  • لغات البرمجة العامة (بايثون، سي++، جافا)
  • أنظمة جداول البيانات ذات إمكانيات الماكرو (على سبيل المثال، Excel مع VBA)
  • دوائر ريدستون في ماينكرافت
  • cellular automata like conway’s game of life
  • بعض ملحقات SQL المتقدمة مع تعبيرات الجدول المشتركة المتكررة
  • نظام البرمجة الفوقية لقالب c++
  • css3 مع مجموعات HTML معينة

براءات الاختراع:

NA

أفكار ابتكارات محتملة

بسبب عمليات جمع البيانات من خلال برامج الروبوت، والتي تتجاوز حاليًا 40 ألفًا يوميًا، فإن هذا المحتوى مخصص لأعضاء المجتمع فقط.
> تسجيل الدخول < أو > سجل < (مجاني 100٪) للوصول إلى هذا، وكذلك جميع المحتويات والأدوات الأخرى المقيدة.

ذات صلة بـ: اكتمال تورينج، آلة تورينج، نظرية الحوسبة، آلان تورينج، أطروحة تشيرش-تورينج، الحوسبة الشاملة، الخوارزمية، اللغة الرسمية، قابلية الحسم، مشكلة التوقف.

السياق التاريخي

اكتمال تورينج

1925
1928
1930
1936
1940
1943
1950
1924
1925
1930
1931
1939
1940
1950
1950

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

الاختراع والابتكار والمبادئ التقنية ذات الصلة

الصور بالحجم الكامل والتنزيلات متاحة فقط 100% مجاناً للأعضاء المسجلين.