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