كتب turing machine picture
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
صورة آلة تورنغ (معلومة)
بشكل عام لوصف الفعالية لالات تورنغ نستخدم بشكل عام مصطلح "صورة"(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 ...
