رياضيات

آلة تورينج

A Turing machine is an abstract computational model that manipulates symbols on a tape.
4 مقالات ذات صلة · 1 من عمل هنا

الوصف

تتكون آلة تورينج رسمياً من شريط لا نهائي مقسم إلى خلايا، تحتوي كل منها على رمز من أبجدية محدودة؛ ووحدة تحكم بذاكرة حالات محدودة؛ ورأس قادر على القراءة والكتابة والانتقال خلية واحدة. تحدد دالة الانتقال (transition function) بناءً على الحالة الحالية والرمز المقروء رمزاً جديداً، واتجاه الحركة (يسار/يمين)، وحالة جديدة. تبدأ الآلة بكلمة مدخلة على الشريط ويمكنها أن تتوقف في حالة قبول أو رفض، أو أن تعلق في حلقة لا نهائية. ويمكن لآلة تورينج العامة (universal Turing machine) أن تحاكي أي آلة أخرى بناءً على وصفها — مما يُعد استباقاً لمفهوم الحاسوب المبرمج.

التاريخ

في عام 1936، أثناء حل آلان تورينج لمسألة القرار (Entscheidungsproblem) التي طرحها ديفيد هيلبرت، قدم مفهوم «الآلة-أ» (الآلة التلقائية) في ورقته «عن الأعداد القابلة للحساب». كان هدفه صياغة المفهوم الحدسي للخوارزمية بصورة شكلية. وبشكل مستقل، توصل ألونزو تشرش إلى مفهوم مكافئ هو حساب اللامدا (λ-calculus). تؤكد أطروحة تشرش-تورينج أن أي عملية يمكن حسابها حدسياً قابلة للتحقيق على آلة تورينج. في عام 1945، استخدم جون فون نيومان هذا النموذج في معمارية EDVAC — النموذج الأولي للحواسيب الحديثة. وفي عام 1985، اقترح ديفيد دويتش آلة تورينج الكمومية، ممهداً الطريق للحوسبة الكمومية.

كيف يعمل

تحسب آلة تورينج من خلال معالجة سلاسل الرموز. وهي من حيث الخوارزمية مكافئة للغة برمجة تحتوي على مصفوفة وحيدة ذات طول لا نهائي. من خصائصها الأساسية: وجود الآلة العامة (المفسّر interpreter)، وعدم قابلية مسألة التوقف للحل (halting problem) (لا يمكن تقرير ما إذا كانت آلة ما ستتوقف على مدخل معين خوارزمياً)، ومبرهنة العودية (recursion theorem) (يمكن للآلة الحصول على وصف لذاتها). وفي نظرية التعقيد، تُدرس الآلات العرَّافية (oracle machines) (التي تملك معلومات إضافية) والآلات الاحتمالية (probabilistic machines) (ذات مولّد بتات عشوائية). وتعمل آلات تورينج الكمومية على حالات في فضاء هيلبرت (Hilbert space) وتستخدم تحويلات واحدية (unitary transformations)؛ وهي لا تخالف أطروحة تشرش-تورينج، لكنها قد تحقق تسريعاً أسياً لبعض المسائل.

في التطبيق

أي برنامج حاسوبي — من الآلة الحاسبة إلى المساعد الذكي — يتحول إلى تعليمات يمكن لآلة تورينج تنفيذها. وتقوم عليها نظرية الحوسبة بأكملها.

حقيقة طريفة

أبسط آلة تورينج عامة، التي ابتكرها مارفن مينسكي، تستخدم 7 حالات فقط و4 رموز — ومع ذلك فهي قادرة على حساب كل ما يستطيعه حاسوب فائق القوة، ولو ببطء شديد.

Concept graph →

مقالات ذات صلة · 16

أربعة قادة لأوركسترا الخلايا: كيف يختار النسيج الطلائي طريق السيولة
يبطن النسيج الطلائي أعضاءنا كما تبطن البلاطات الأرضية. في حالة السكون، تتماسك الخلايا مع بعضها البعض، ويكون النسيج مرنًا. لكن أثناء تطور الجنين أو التئام الجروح أو نمو الأورام، تبدأ هذه الطبقة في التدفق مثل العسل الكثيف. ما الذي يطلق هذا التليين بالضبط؟ قد تدفع الخلايا بعضها عشوائيًا، أو تتحرك بشكل منسق في اتجاه واحد، أو تنقبض بشكل فوضوي، أو تستجيب لتمددها الذاتي فتُطلق موجات انقباض.
ترميم Z3: نقرات المرحّلات تُحيي حاسوبًا مفقودًا
برلين، ديسمبر 1943. وميض قنبلة — ويختفي Z3، أول حاسوب تلقائي كامل قابل للبرمجة في التاريخ، وسط ألسنة اللهب. صانعه، كونراد تسوزه، لا يحاول حتى ترميم العتاد: فبعد الحرب يبني آلات جديدة. لكن فكرة Z3 — كلوحة مفقودة لم يبق منها سوى رسوم أولية وذكريات — تنتظر دورها.
أوركسترا بدون قائد: المجموعة المرنة لاستدلال نماذج اللغة الكبيرة
سبعة أنوية تجمدت عند حاجز غير مرئي. الثامن تأخر في عملية أخرى — وتوقف استدلال LLM بالكامل. هكذا تبدو المشكلة الرئيسية في تعايش مهام التعلم الآلي مع العمليات العادية على معالج واحد. مجموعة الاستدلال (gang) تتطلب أن تعمل جميع الأنوية في تناغم تام في نفس اللحظة — وإلا ساد الصمت.
العتبة 2: كيف تصمد المسطرة المطاطية أمام التوسيط اللانهائي
الاثنان — هو الحد الذي بعده تتعرض المتتابعة المطيعة لخطر فقدان بنيتها. فبدلاً من المقياس المنتظم المألوف، لدينا مسطرة مطاطية بمرونة غير متجانسة. هذا هو بالضبط كيف تُبنى فضاءات أورليخ (Orlicz spaces): فضاءات باناخ (Banach spaces) للمتتابعات، حيث يرتبط كل مقياس بصلابته الخاصة، التي توصف بدالة يونغ المحدبة (Convex Young function) (وهي بمثابة نوع من النوابض).
حاسوب كيميائي في أنبوب اختبار
في أنبوب الاختبار تسبح الجزيئات. كميتها — لنقل تركيز بروتين معين — تصبح الإشارة الداخلة. وعلى المخرج لا نريد مجرد محلول عكر، بل إجابة واضحة مثل "نعم" أو "لا". يُقيم مؤلفو العمل سلسلة كيميائية تفعل ذلك بالضبط. تستقبل مادة واحدة بتركيز يتراوح بين الصفر والواحد، وتُخرج سلسلة من النبضات — مثل شيفرة مورس، لكن كيميائية. كل نبضة تعني "تشغيل"، وغيابها يعني "إيقاف".
كتابة بلا أبجدية: كيف يرسم الدماغ حروفًا لم يرها من قبل
ترسم اليد في الهواء كلمة «ماما» — أقواس وخطوط مألوفة. والدماغ في هذه الأثناء لا يستعرض صورة كل حرف، بل يشغّل سلسلة من الحركات البسيطة. اختبر مهندسو الأعصاب هذه الفكرة: الكتابة الذهنية ليست معرضًا للصور الجاهزة، بل مجموعة تركيب من «لبنات» حركية متكررة. في التجربة، زُرعت في أدمغة المتطوعين غرسات داخل القشرة الدماغية — أجهزة استشعار دقيقة داخل الدماغ مباشرة. كانوا يكتبون حروفًا لاتينية ذهنيًا.
كيف نجعل المحركات الجزيئية لا تنزلق
داخل كل خلية تعج الحياة: آلات بروتينية صغيرة تنقل الأحمال بلا كلل، وتقرأ الجينات، وتصحح الأخطاء. لكن عملها بعيد عن المثالية — فهي بين الحين والآخر "تنزلق"، أو تخطو خطوات إلى الوراء، أو تعلق في دورات غير مفيدة. هذا يشبه ازدحامًا مروريًا في مدينة، حيث تتحرك السيارات بلا فائدة، محرقة الوقود.
كيف تضبط محركًا جزيئيًا دون أن تعقد الأمور
مصنع تدار فيه مئات خطوط التجميع الصغيرة دون توقف. كل خط هو محرك جزيئي يحول الوقود الكيميائي إلى حركة. لجعل المحرك يتحرك أسرع أو في الاتجاه المطلوب، يعدّل المهندس الإعدادات — شكل الأجزاء، وقوة التفاعلات. ولكن كيف تعرف أي إعداد سينجح إذا كانت الاختبارات تستغرق وقتًا طويلاً؟ المشكلة أن أهم الأحداث — مثل قفزة نادرة للمحرك إلى وضع جديد — تحدث مرة كل قرن بمقاييس المحاكاة.
الذكاء الاصطناعي يمهد الطريق لرقاقات ضوئية
ينقسم شعاع الليزر إلى عشرات الخيوط الرفيعة، ويمر عبر زجاج بلوري، ثم يتجمع مرة أخرى في نقطة واحدة. هكذا تبدو الطاولة التي جلست أمامها البرنامج. لم تُعطَ أي تعليمات، بل هدف عام فقط: فهم كيف يتغير الضوء عند مروره عبر وسط مشتت، وإيجاد شيء جديد.
مصائد الذرات: كيف نملؤها حتى آخر ذرة
الملقط البصري هو شعاع ليزر يمسك بذرة في نقطة واحدة، كما تمسك الأصابع بحبة البازلاء. من هذه الملاقط تُبنى شبكات كاملة من الذرات، وهي أساس أجهزة الكمبيوتر الكمومية المستقبلية. لكن هناك مشكلة: لا تدخل الذرة إلى كل ملقط. عادةً، تمتلئ نصف المصائد فقط، وبالنسبة للجزيئات تكون النسبة أقل من ذلك. الأماكن الفارغة تكسر البنية بأكملها.
آلة لا تعيق نفسها بنفسها
أوركسترا يعزف كل عازف فيها دوره، لكنه لا يسمع إلا جاره. ما إن يخطئ أحدهم حتى تتدحرج موجة الأخطاء عبر القاعة كلها. هكذا تعمل آلات إيزينج — أجهزة خاصة لحل المسائل التي تتطلب إيجاد الخيار الأفضل من بين العديد. عناصرها، أو «السبينات»، مترابطة، وإذا حُدِّثت في آن واحد، تبدأ بالتداخل مع بعضها مثل موسيقيين دخلوا في غير موعدهم. عادةً تُحدَّث السبينات تباعًا، لكن هذا بطيء.
رقصة الأيونات: ولادة دوامات كمومية
في مصيدة كهرومغناطيسية، شكل الباحثون بلورة أيونية — بنية منتظمة من 150 أيونًا مبردًا إلى درجات حرارة منخفضة للغاية درجات الحرارة. كل أيون يتصرف كمغناطيس أولي، لفه المغزلي هو متجه يمكن توجيهه في الفضاء بحرية.
أفكار لم يبحث عنها أحد
العلم يشبه مدينة يسكنها سكان يمدّون شوارعها بأنفسهم. حيثما توجد ممرات معبّدة، تُبنى منازل جديدة، بينما تظل الأراضي البور غير ملحوظة — ليس لأن البناء فيها مستحيل، بل لأن لا أحد يلتفت إليها. في العلم، هذه الأراضي البور هي اتجاهات تنبع منطقيًا من المعروف سابقًا، لكنها لا تخطر ببال العلماء، لأن لكلٍّ منهم تخصصه الضيق وأساليبه المألوفة. النظام الجديد يعمل كرسّام خرائط لا يتبع الآثار، بل ينظر إلى الخريطة من الأعلى.
الدماغ يطبع بنفسه: كيف تسرّع أزواج الأقطاب قراءة الأفكار
ينظر الشخص إلى شاشة تظهر عليها حروف تومض. لا يحرك يده ولا عينه — فقط يحدد ذهنيًا الرمز المطلوب. تلتقط أجهزة الاستشعار على الرأس موجات كهربائية ضعيفة من الدماغ، ويفهم الحاسوب أي حرف اختاره الشخص. هكذا تعمل واجهة «الدماغ — الحاسوب»: إنها تعطي صوتًا لمن لا يستطيعون الكلام أو الحركة.
ذاكرة فائقة التوصيل: مفتاح لا ينسى
الذاكرة التقليدية في الحواسيب تستهلك طاقة باستمرار كي لا تنسى ما خُزّن فيها. أما المادة فائقة التوصيل فيمكنها تخزين البيانات دون فقدان، لكن من الصعب جعلها تتبدل بين حالتين. في العمل الجديد، حُصرت مادة فائقة التوصيل بين عازلين مغناطيسيين. تعمل الطبقات المغناطيسية كقطبين مغناطيسيين: إذا كان قطباها متوازيين، تكون خاصية التوصيل الفائق مفعّلة؛ وإذا كانا متعاكسين، تكون معطّلة.
رنين النفق: كيف تتعلم الثنائيات الرؤية
في عام 1974، وصف الفيزيائيون لأول مرة جهازًا تمر فيه الإلكترونات عبر حاجز طاقة بفضل النفق الكمومي. اليوم، هذا الجهاز، وهو الصمام الثنائي الرنان النفقي (resonant tunneling diode)، أصبح قلب بنية حوسبة غير تقليدية. فبدلًا من آلاف الأسطر من البرمجيات ومعالج قوي، نجد مصفوفة من 28 ثنائيًا تقرأ الصورة وتحولها إلى مجموعة من الميزات تكفي لتمييز الأرقام والفواكه.