د کمپیوټري فعالیت او د تورینګ ماشین شتون ترمنځ اړیکه تشریح کړئ چې کولی شي دا محاسبه کړي.
د کمپیوټري پیچلتیا تیوري په ساحه کې، د کمپیوټري فعالیت او د تورینګ ماشین شتون ترمنځ اړیکه چې کولی شي دا محاسبه کړي بنسټیز اهمیت لري. د دې اړیکې د پوهیدو لپاره، موږ باید لومړی تعریف کړو چې د کمپیوټري فعالیت څه شی دی او دا څنګه د تورینګ ماشینونو سره تړاو لري.
د محاسبې وړ فنکشن، چې د تکراري فنکشن په نوم هم پیژندل کیږي، یو ریاضياتي فنکشن دی چې د الګوریتم لخوا محاسبه کیدی شي. دا یو فنکشن دی چې د هغې لپاره د تورینګ ماشین شتون لري چې د هر ډول ان پټ سره به ودریږي او د دې ان پټ لپاره سم محصول تولید کړي. په بل عبارت، د محاسبې وړ فعالیت هغه دی چې د تورینګ ماشین لخوا په مؤثره توګه محاسبه کیدی شي.
د تورینګ ماشینونه، له بل پلوه، نظري کمپیوټري وسایل دي چې په 1936 کې د الان تورینګ لخوا معرفي شوي. دوی د لامحدود ټیپ څخه جوړ شوي چې په حجرو ویشل شوي، د لوستلو/لیکلو سر چې کولی شي د ټیپ سره حرکت وکړي، او د دولتونو یوه ټولګه چې اداره کوي. د ماشین چلند. ماشین په ټیپ کې سمبولونه لولي، د خپل اوسني حالت او سمبول پر بنسټ ځینې کړنې ترسره کوي، او نوي حالت ته لیږدوي. دا پروسه تر هغه وخته دوام کوي تر څو چې ماشین ودریږي حالت ته ورسیږي.
د کمپیوټري فعالیت او د تورینګ ماشین شتون ترمنځ اړیکه چې کولی شي دا محاسبه کړي د تورینګ بشپړتیا مفهوم پراساس دی. د تورینګ ماشین ته ویل کیږي چې د تورینګ بشپړ دی که چیرې دا د کوم بل تورینګ ماشین انډول کولی شي. په بل عبارت، د تورینګ بشپړ ماشین کولی شي هر هغه فعالیت محاسبه کړي چې د کوم بل تورینګ ماشین لخوا محاسبه کیدی شي.
د دې تعریف په پام کې نیولو سره، موږ کولی شو ووایو چې که یو فنکشن د محاسبې وړ وي، نو د تورینګ ماشین شتون لري چې کولی شي دا محاسبه کړي. برعکس، که د تورینګ ماشین کولی شي یو فنکشن محاسبه کړي، نو دا فنکشن د حساب وړ دی. دا اړیکه د دې حقیقت پراساس ده چې د تورینګ ماشینونه نړیوال کمپیوټري وسیلې دي چې د کوم بل تورینګ ماشین سمولو وړتیا لري.
د دې اړیکو د روښانه کولو لپاره، راځئ چې یو مثال په پام کې ونیسو. فرض کړئ چې موږ د محاسبې وړ فعالیت لرو چې دوه شمیرې اضافه کوي. موږ کولی شو د تورینګ ماشین تعریف کړو چې دوه انپټونه اخلي، د لوستلو/لیکلو سر په ټیپ کې لومړي نمبر ته حرکت کوي، دویمه شمیره ورته اضافه کوي، او پایله یې تولیدوي. دا تورینګ ماشین کولی شي اضافي فعالیت محاسبه کړي ، د کمپیوټري فنکشن او د تورینګ ماشین شتون ترمینځ اړیکه څرګندوي چې کولی شي دا محاسبه کړي.
د کمپیوټري فعالیت او د تورینګ ماشین شتون ترمنځ اړیکه چې کولی شي دا محاسبه کړي د تورینګ بشپړتیا مفهوم پراساس دی. د کمپیوټیبل فنکشن هغه دی چې د تورینګ ماشین لخوا په مؤثره توګه محاسبه کیدی شي ، او د تورینګ ماشین د تورینګ بشپړ دی که چیرې دا د کوم بل تورینګ ماشین سره سمولیټ شي. نو ځکه، که یو فنکشن د حساب وړ وي، د تورینګ ماشین شتون لري چې کولی شي دا محاسبه کړي، او برعکس.
په اړه نورې وروستۍ پوښتنې او ځوابونه د پام وړ دندې:
- د تورینګ ماشینونو مختلف توپیرونو لپاره دا څه معنی لري چې د کمپیوټري وړتیا سره مساوي وي؟
- د ټورینګ ماشین اهمیت څه دی چې د کمپیوټري فعالیت کمپیوټري کولو پرمهال تل ودریږي؟
- ایا د تورینګ ماشین بدلیدلی شي ترڅو تل یو فعالیت ومني؟ تشریح کړئ چې ولې یا ولې نه.
- د تورینګ ماشین څنګه فعالیت محاسبه کوي او د ان پټ او آوټ پوټ ټیپونو رول څه دی؟
- د کمپیوټري پیچلتیا تیوري په شرایطو کې د کمپیوټري فعالیت څه شی دی او دا څنګه تعریف شوی؟