د الګوریتم تشریح کړئ چې د تورینګ ماشینونو لپاره د منلو ستونزه پریکړه کوي، او دا څنګه د خالي ژبې ستونزې لپاره د پریکړه کونکي جوړولو لپاره کارول کیږي.
د تورینګ ماشینونو لپاره د منلو ستونزه د کمپیوټري پیچلتیا تیوري کې یو بنسټیز مفهوم دی، کوم چې د الګوریتم لخوا اړین سرچینو مطالعې سره معامله کوي ترڅو د کمپیوټري ستونزو حل کړي. د تورینګ ماشینونو په شرایطو کې، د منلو ستونزه د دې معلومولو ته اشاره کوي چې ایا ورکړل شوی تورینګ ماشین یو ځانګړی ان پټ تار مني.
د الګوریتم تشریح کولو لپاره چې د تورینګ ماشینونو لپاره د منلو ستونزه پریکړه کوي ، موږ اړتیا لرو د تورینګ ماشین په کارونو پوه شو. د تورینګ ماشین یو ټیپ لري چې په حجرو ویشل شوي ، د لوستلو لیکلو سر چې کولی شي د ټیپ سره حرکت وکړي ، او د کنټرول واحد چې د ماشین چلند ټاکي. د کنټرول واحد عموما د محدود دولتي ماشین لخوا نمایش کیږي.
الګوریتم چې د ټورینګ ماشینونو لپاره د منلو ستونزې پریکړه کوي د ان پټ سټینګ کې د ورکړل شوي ټورینګ ماشین چلند سمول شامل دي. دا سمول په ګام په ګام پرمخ ځي، د تورینګ ماشین د کنټرول واحد لخوا مشخص شوي لیږدونه تعقیبوي.
الګوریتم د ان پټ تار سره د ټیپ په پیل کولو سره پیل کیږي او د ټیپ په پیل کې د لوستلو لیکلو سر ځای په ځای کوي. بیا، دا یو لوپ ته ننوځي چیرې چې دا په مکرر ډول لاندې مرحلې ترسره کوي:
1. د لوستلو لیکلو سر لاندې سمبول ولولئ.
2. د تورینګ ماشین اوسنی حالت معلوم کړئ.
3. د تورینګ ماشین د لیږد فعالیت وګورئ ترڅو راتلونکی حالت ومومئ او هغه عمل چې د اوسني حالت او سمبول لوستلو پراساس ترسره کیږي.
4. د لیږد فعالیت لخوا مشخص شوي عمل پراساس د ټیپ او د لوستلو لیکلو سر موقعیت تازه کړئ.
5. که راتلونکی حالت د منلو وړ حالت وي، د ننوتلو تار ودروئ او ومنئ. که راتلونکی حالت د رد کولو حالت وي، د ننوتلو تار ودروئ او رد کړئ.
دا الګوریتم تر هغه وخته دوام کوي چې د تورینګ ماشین په منلو یا ردولو حالت کې ودریږي. که د تورینګ ماشین هیڅکله ودریږي، الګوریتم نه ختمیږي.
د منلو ستونزې لپاره د الګوریتم په کارولو سره د خالي ژبې ستونزې لپاره پریکړه کونکی رامینځته کولو لپاره ، موږ اړتیا لرو دا معلومه کړو چې ایا ورکړل شوی تورینګ ماشین کوم تار مني. د خالي ژبې ستونزه پوښتنه کوي چې ایا د تورینګ ماشین لخوا پیژندل شوې ژبه خالي ده ، یعنی دا هیڅ تار نه مني.
د خالي ژبې ستونزې حل کولو لپاره، موږ کولی شو د منلو ستونزې لپاره الګوریتم په لاندې ډول وکاروو:
1. د تورینګ ماشین په نظر کې نیولو سره، یو نوی تورینګ ماشین جوړ کړئ چې د اصلي تورینګ ماشین چلند په ټولو ممکنه ان پټ تارونو کې انډول کوي.
2. په نوي جوړ شوي تورینګ ماشین کې د منلو ستونزې لپاره الګوریتم چل کړئ.
3. که د منلو ستونزې لپاره الګوریتم ودروي او کوم ان پټ تار ومني، نو اصلي تورینګ ماشین لږترلږه یو تار مني، او د خالي ژبې ستونزه غلطه ده.
4. که د منلو ستونزې لپاره الګوریتم ټول داخل شوي تارونه ودروي او رد کړي، نو اصلي تورینګ ماشین هیڅ تار نه مني، او د خالي ژبې ستونزه سمه ده.
د منلو ستونزې لپاره د الګوریتم په کارولو سره، موږ کولی شو د خالي ژبې ستونزې لپاره پریکړه کونکی جوړ کړو، کوم چې دا معلومه کوي چې ایا ورکړل شوی تورینګ ماشین کوم تار مني.
الګوریتم چې د تورینګ ماشینونو لپاره د منلو ستونزه پریکړه کوي د ان پټ سټینګ کې د ټورینګ ماشین چلند سمول شامل دي. د دې الګوریتم په کارولو سره، موږ کولی شو د خالي ژبې ستونزې لپاره پریکړه کونکی جوړ کړو، کوم چې دا معلومه کوي چې ایا ورکړل شوی تورینګ ماشین کوم تار مني.
په اړه نورې وروستۍ پوښتنې او ځوابونه د پریکړې وړتیا:
- ایا یو ټیپ د ان پټ اندازې پورې محدود کیدی شي (کوم چې د ټرینګ ماشین سر سره مساوي دی چې د TM ټیپ ان پټ څخه بهر حرکت کولو لپاره محدود وي)؟
- د تورینګ ماشینونو مختلف توپیرونو لپاره دا څه معنی لري چې د کمپیوټري وړتیا سره مساوي وي؟
- ایا د پیژندلو وړ ژبه کولی شي د پریکړې وړ ژبې فرعي سیټ جوړ کړي؟
- ایا د تورینګ ماشین د بندیدو ستونزه د پریکړې وړ ده؟
- که موږ دوه TMs ولرو چې د پریکړې وړ ژبه بیانوي ایا د مساوي پوښتنه لاهم د نه منلو وړ ده؟
- د لینیر باونډډ آټوماټا لپاره د منلو ستونزه څنګه د تورینګ ماشینونو څخه توپیر لري؟
- د یوې ستونزې مثال ورکړئ چې د خطي محدود اتوماتیک لخوا پریکړه کیدی شي.
- د لینر باونډډ آټوماټا په شرایطو کې د پریکړه کولو مفهوم تشریح کړئ.
- په لینیر باونډډ آټوماټا کې د ټیپ اندازه څنګه د جلا ترتیبونو شمیر اغیزه کوي؟
- د لینیر بانډ شوي اتومات او ټورینګ ماشینونو ترمینځ اصلي توپیر څه دی؟
نورې پوښتنې او ځوابونه په پریکړه کولو کې وګورئ