books turing machine picture
If you do not find what you're looking for, you can use more accurate words.
صورة آلة تورنغ (Info)
بشكل عام لوصف الفعالية لالات تورنغ نستخدم بشكل عام مصطلح "صورة"(Configuration) . وبشكل غير دقيق صورة آلة تورنغ في لحظة مُعينة تحوي كل الحسابات التي قامت بها الآلة في تلك اللحظة، أي انه صورة آلة تورنغ M هي ثلاثي : حيث أن هو الحال الحالي، و- هما سلسلتان اللتين تصفان ما على يمين المؤشر (الذي قد يكون فارغا) وما على يساره . نقول أن الصورة تنتج الصورة في خطوة واحدة نرمز لها ب- إذا خطوة الآلة بعد الصورة نرى الصورة أي انه : فلنفرض أنَّ هو الرمز الأخير في السلسلة ولنفرض أن حينها , اما بالنسبة ل-D فعندنا ثلاث حالات :
- إذا حينها "w هي w غير أن الرمز الأخير في w الذي كان بدلناه ليكون وأول رمز في u هو الرمز الحالي أي انَّ "u هو u غير أن الرمز الأول في u قد حذف .
- إذا حينها "w هي w غير أن الرمز الأخير في w حُذف، و "u هو u غير أننا اضفنا لبدايته .
- إذا حينها "w هي w غير أن الرمز الأخير في w الذي كان بدلناه ليكون ولكن .
بشكل مشابه يمكن القول أن الصورة تنتج الصورة خلال k خطوات نرمز لها ب- , ونقول أنَّ الصورة تنتج الصورة ونرمز لهذا ب- إذا يوجد بحيث يتحقق : .
مخطط الصور
فلتكن M آلة تورنغ، لكل مخطط الصور,GM,x , هو مخطط الذي فيه كل رأس هو صورة آلة تورنغ M أثناء حساب x , ويوجد ضلع بين رأسين c1 ,c2 فقط إذا يمكن الوصول من c1 إلى c2 بخطوة حسابية واحدة .
لهذا المخطط أهمية كبيرة في نظرية التعقيد حيث أن له استخدامات عديدة من بينها في مبرهنة سافيتش , L⊆ NL , NL⊆ P , PSPACE ⊆EXP ...
