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

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

1936
  • Alan Turing
Computer science lab showcasing Turing completeness in programming languages.

(صورة توضيحية فقط)

نظام من قواعد معالجة البيانات، مثل لغة البرمجة, is Turing complete if it can simulate any single-taped Turing machine. This means it is computationally universal and can be used to solve any computable problem, given enough time and memory. Most general-purpose programming languages are Turing complete, forming the theoretical foundation for their expressive power.

Turing completeness is a concept from computability theory that defines the power of a computational system. It originates from Alan Turing’s 1936 paper describing a theoretical device known as the Turing machine. This machine consists of an infinitely long tape, a head that can read, write, and move along the tape, and a set of states and transition rules. Despite its simplicity, a Turing machine can perform any computation that can be described algorithmically. A لغة البرمجة or any other formal system is deemed ‘Turing complete’ if it has the capability to simulate a universal Turing machine. This implies that the language can compute anything that is computable.

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

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

UNESCO Nomenclature: 1202
– Computer science

يكتب

نظام مجرد

خلل

Incremental

الاستخدام

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

مقدمات

  • كورت غودلعمل ® على نظريات عدم الاكتمال
  • Alonzo Church’s development of lambda calculus
  • برنامج ديفيد هيلبرت لإضفاء الطابع الرسمي على الرياضيات
  • يعود مفهوم الخوارزمية إلى العصور القديمة

التطبيقات

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

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

NA

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

  • لغة عقود ذكية قابلة للتحقق وغير تورينجية كاملة للمعاملات المالية الهامة لمنع الحلقات اللانهائية وهجمات إعادة الدخول.
  • لعبة تعليمية حيث يقوم اللاعبون ببناء آلات تورينج الكاملة من بوابات منطقية أساسية لتدريس علوم الكمبيوتر الأساسية.
  • نظام حوسبة يعتمد على الحمض النووي ويستفيد من اكتمال تورينج لإجراء عمليات محاكاة بيولوجية معقدة على المستوى الجزيئي.
  • نموذج برمجة كمية يمتد إلى اكتمال تورينج للتعامل مع التراكب والتشابك من أجل خوارزميات جديدة.
  • أ formal verification tool that can prove or disprove the turing completeness of any given formal system or esoteric language.
  • بروتوكول شبكة لامركزي حيث يتم تعريف سلوك العقدة من خلال نصوص صغيرة محمية ومكتملة تورينج لتوجيه قابل للتخصيص.
  • ذكاء اصطناعي فني يولد أنماط بصرية جديدة من خلال استكشاف مساحة الحالة للآلات تورينج البسيطة التي يتم إنشاؤها عشوائيًا.
  • إطار عمل لتحليل الأمان يعمل على تحديد نقاط الضعف المحتملة في رفض الخدمة الناجمة عن اكتمال تورينج غير المقصود في ملفات التكوين.
  • a neuro-symbolic ai architecture where a الشبكة العصبية learns to manipulate a turing-complete symbolic computation engine.
  • نظام أجهزة قابل للتعديل ذاتيًا يعتمد على FPGA حيث يكون منطق الأجهزة نفسه عبارة عن نظام تورينج كامل يمكن أن يتطور.
ذات صلة بـ: اكتمال تورينج، آلة تورينج، نظرية الحوسبة، آلان تورينج، أطروحة تشيرش-تورينج، الحوسبة الشاملة، الخوارزمية، اللغة الرسمية، قابلية الحسم، مشكلة التوقف.

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

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

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

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

أحدث الإضافات

أهم المنشورات والمقالات

أفضل الأدوات الأصلية

السنة العاشرة عيد

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