Turing Machines (TM)

الفصل الثامن: آلة تورنغ (أساس الحوسبة الحديثة)

الهدف: فهم النموذج الأقوى للحوسبة، الشريط اللانهائي، وكيفية حل المشاكل (أو عدم حلها!).
1

What is a Turing Machine؟

هي نموذج نظري لكمبيوتر يمتلك ذاكرة غير محدودة (Infinite Tape).

  • يمكنها قراءة الكتابة على الشريط (Read/Write).
  • يمكنها التحرك يميناً ويساراً (Move L/R).
  • تتوقف (Halt) عند القبول أو الرفض، أو تدخل في حلقة لا نهائية (Loop).
Infinite Tape
...
0
1
1
0
B
...
Read/Write Head
Move: Left (L) or Right (R)
2

Formal Definition (The 7-Tuple)

تُعرف آلة تورنغ بـ 7 عناصر $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$:

Q مجموعة الحالات (States).
$\Sigma$ أبجدية المدخلات (Input Alphabet).
$\Gamma$ أبجدية الشريط (Tape Alphabet). ( $\Sigma \subset \Gamma$ )
$\delta$ دالة الانتقال (Transition Function).
$q_0$ حالة البداية.
B الرمز الفارغ (Blank Symbol). ( $B \in \Gamma$ but $B \notin \Sigma$ )
F الحالات النهائية (Final States).

The Heart of TM: Transition Function $\delta$

$\delta(q, X) = (p, Y, D)$

(Current State, Read Symbol) $\to$ (Next State, Write Symbol, Direction L/R)

3

Extensions of Turing Machine

هل يمكننا جعل آلة تورنغ أقوى بإضافة ميزات جديدة؟

Multi-tape TM

لديها عدة أشرطة ورؤوس قراءة مستقلة.

النتيجة: تكافئ الـ TM العادية (Equivalent).
أي أنها لا تحل مشاكل جديدة، بل قد تكون أسرع فقط.

Nondeterministic TM (NTM)

يمكنها الاختيار بين عدة انتقالات لنفس المدخل.

النتيجة: تكافئ الـ TM الحتمية (Deterministic).
على عكس الـ PDA حيث NPDA $\neq$ DPDA.
4

Languages & Acceptance

نوع اللغة سلوك الآلة (TM)
Recursive Language (Decidable) الآلة تتوقف (Halts) دائماً.
- تقبل الكلمة إذا كانت في اللغة.
- ترفض وتتوقف إذا لم تكن في اللغة.
Recursively Enumerable (RE) الآلة قد لا تتوقف (Loop) إذا كانت الكلمة ليست في اللغة.
- تقبل وتتوقف إذا كانت الكلمة في اللغة.
- قد تعلق في حلقة لا نهائية (Infinite Loop) إذا لم تكن.
🛡️ EXAM VAULT (خزنة الاختبار)
COMPARISON / مقارنة القوة

Hierarchy of Automata

  • FA (Finite Automata): ذاكرة محدودة (States only).
  • PDA (Pushdown): ذاكرة LIFO لا نهائية (Stack).
  • TM (Turing Machine): ذاكرة عشوائية لا نهائية (Tape). وهي الأقوى.
TRAP / فخ

Power of Nondeterminism

هل الـ Non-deterministic TM أقوى من الـ Deterministic TM؟
لا! لهما نفس القدرة التعبيرية (Equivalence).
الاستثناء الوحيد كان في الـ PDA (حيث NPDA > DPDA).

→ السابق (Ch 7) الفصل التالي (Ch 9) ←