TM Extensions & Encoding

الفصل التاسع: تنويعات آلة تورنغ وتمثيل البيانات

الهدف: إثبات أن "التعقيد" لا يعني "زيادة القوة"، وفهم كيفية ترميز المشاكل.
1

Variations of Turing Machines

هل يمكننا تحسين آلة تورنغ لجعلها تحل مشاكل لا تستطيع الآلة العادية حلها؟

1. Multi-track TM

1
0
1
B
...
$
X
Y
B
...

شريط واحد مقسم لعدة "مسارات" (Tracks). رأس قراءة واحد يقرأ كل المسارات في نفس الوقت.
الفائدة: تخزين معلومات إضافية (مثل العلامات Markers) دون فقدان البيانات الأصلية.

2. Multi-tape TM

Tape 1:
[ Input ]
Tape 2:
[ Scratch ]

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

The Golden Rule (القاعدة الذهبية)

Multi-tape TM $\equiv$ Single-tape TM
أي مشكلة يمكن حلها بآلة متعددة الأشرطة، يمكن حلها بآلة بشريط واحد (وإن كانت أبطأ).

2

Nondeterministic TM (NTM)

ما هي NTM؟

في كل خطوة، الآلة يمكنها "الاختيار" بين عدة انتقالات ممكنة (Guessing).
تقبل الآلة الكلمة إذا كان هناك مسار واحد على الأقل يؤدي للقبول.

$\delta(q, X) = \{ (q_1, Y_1, R), (q_2, Y_2, L), \dots \}$

هل NTM أقوى من DTM؟

لا!
أي NTM يمكن محاكاتها بواسطة DTM (عن طريق تجربة كل الاحتمالات بالتسلسل - BFS).
النتيجة: NTM = DTM (في القدرة على الحل، وليس في السرعة).

3

Encoding (الترميز)

آلة تورنغ تقبل فقط "سلسلة من الرموز" على الشريط. كيف نعطيها برنامجاً أو صورة أو آلة أخرى؟

Step 1
أي شيء ← نص (String) الصور، الموسيقى، البرامج.. كلها يمكن تحويلها لسلسلة من البايتات (Binary String).
Step 2
نص ← عدد صحيح (Integer) كل سلسلة ثنائية يمكن اعتبارها رقماً. إذن، كل برنامج هو في الحقيقة "رقم"!
Step 3
آلة تورنغ كمدخل (TM as Input) بما أن آلة تورنغ يمكن وصفها بجدول انتقالات، يمكننا تحويل هذا الجدول لسلسلة، وإدخالها لآلة تورنغ أخرى!
4

Universal Turing Machine (UTM)

The "Computer" Concept

هي آلة تورنغ $U$ تأخذ كمدخل:
1. وصف لآلة تورنغ أخرى $M$ (مرمزة).
2. مدخل $w$.

Run $U( < M, w > )$ $\equiv$ Run $M(w)$

هذا هو مبدأ الكمبيوتر المخزن للبرامج (Stored-Program Computer). السوفتوير (M) هو مجرد بيانات مدخلة للهاردوير (U).

🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / فخ القوة

Do extensions increase power؟

هل إضافة أشرطة (Tapes) أو رؤوس (Heads) أو عدم حتمية (Nondeterminism) تجعل الآلة تحل مشاكل كانت "مستحيلة" سابقاً؟
لا!
تزيد الكفاءة (Efficiency) فقط، لكنها لا تزيد القدرة (Computability).

CONCEPT / مفهوم

Programs are Countable

بما أن كل برنامج يمكن تحويله لعدد صحيح (Integer)، فإن مجموعة البرامج معدودة (Countable).
لكن مجموعة "المشاكل/اللغات" غير معدودة (Uncountable - Real Numbers).
النتيجة المرعبة: هناك مشاكل لا يوجد لها برامج!

→ السابق (Ch 8) الفصل التالي (Ch 10) ←