ماشین تورینگ محاسباتی

1396/5/2 محمدرضا احمدآبادی 335

Turing machine

سلام . حالتون خوبه ؟ محمدرضا احمدآبادی هستم با جلسه 24 آموزش نظریه زبان ها . نظریه زبان ها هم دیگه داره به ایستگاه آخر خودش میرسه . جلسه بعدی جلسه پایانی دوره آموزشی نظریه زبان ها خواهد  بود. 
در جلسه پیش در مورد ماشین تورینگ صحبت کردیم. امروز میخوام براتون درمورد ماشین تورینگ محاسباتی صحبت کنم . پس بیش از این دیگه وقت را تلف نمیکنیم و میریم سراغ آموزش امروز.

تورینگ محاسباتی

منظور از طراحی ماشین تورینگ محاسباتی ، طراحی تورینگی است که توابع ریاضی را پیاده سازی میکند . یعنی پس از طراحی ماشین تورینگ محاسباتی، اگر ماشین عددی را به عنوان ورودی دریافت کند باید عدد صحیحی را به عنوان عدد خروجی تولید کند. در ماشین های تورینگ هر عدد با تعداد یک هایی که روی نوار قرار میگیرد مشخص میشود. 
مثلا برای اینکه یک ماشین تورینگ عدد 3 را دریافت کند ، دنباله 111 را روی نوار قرار میدهیم ، اشتباها این اعداد را باینری نخوانید که میشود 7.
اگر توابع ریاضی دو پارامتری باشند (f(x,y) ) برای ارسال دو عدد به ماشین تورینگ ، این دو عدد با یک سمبل صفر از هم جدا میشوند. برای مثال دنباله  111110111 به معنی ورود عدد 5 و 3  خواهد بود. 
نکته: درپایان طراحی ماشین تورینگ محاسباتی ، هد در هر حالت پایانی حتما باید به اولین 1 از دنباله جواب اشاره کند . 
مثال)

F(x,y)=x+1

برای اینکه ماشین تورینگ محاسباتی این تابع را بکشیم باید یه سری مقدماتی را رعایت کنیم. اولا داخل توابع فقط باید عدد صحیح قرار بگیرد . ثانیا طبق اصول ماشین تورینگ انتهای رشته  با بلانک مشخص شده . 
اگر بخواهیم ماشین تورینگ محاسباتی این تابع را رسم کنیم فرض کنیم کاربر یک عدد را به ماشین داده است مثلا 5 . خروجی ماشین باید به او داده شود 6. برای اینکار چه فکری به نظرتون میرسه ؟ یک فکر راحت و آسون که به نظر من میرسه این هست که بلانک انتهای رشته را تبدیل به یک کنیم و بلانک را یک واحد به عقب ببریم اینطوری تابع x+1 ساخته میشود. خب برای این کار من باید تمام 1 های روی رشته را پیمایش کنم و از روی آنها گذر کنم تا به بلانک برسم . زمانی که به بلانک رسیدم آن را تبدیل به یک میکنم و حالا برمیگردم به اول رشته که اینبار این اول رشته خواهد بود اول رشته جواب.  گفتیم که در ابتدا باید من تمام یک های رشته ورودی را پویش کنم . پس تا به اینجا ماشین ما خواهد شد:

 

Turing Machine


حالا تا اینجا ماشین همه 1 های رشته ورودی را پیمایش کرده و به بلانک رسیدیم باید بلانک را تبدیل به 1 کنیم . وبعد دوباره باید 1 هارا پیمایش کنیم وبرگردیم به ابتدای رشته ورودی که رشته جواب خواهد بود.
 

Turing Machine


خب یه فرض اینجا باید داشته باشیم اینکه علاوه بر انتهای رشته ، ابتدای رشته هم بلانک وجود دارد که از انتهای رشته قبلی بوده است خب وقتی ماشین به بلانک ابتدایی میرسد کافیست یک خانه به سمت راست برود تا به اولین یک رشته ورودی برسد . پس ماشین نهایی ما خواهد شد:
 

Turing Machine

F(x,y)=x-1

برای رسم ماشین تورینگ محاسباتی این زبان کافیست خلاف مثال قبل عمل کنیم .
پس یک های رشته ورودی را پویش میکنیم به اخرین یک رشته ورودی که رسیدیم اون را تبدیل به بلانک میکنیم و برمیگردیم به ابتدای رشته ورودی. 
پس ماشین تورینگ محاسباتی ما خواهد شد:

 

Turing Machine

F(x,y)=x+y

برای رسم ماشین تورینگ این تابع همانطور که میدانید دو عدد به این ماشین داده میشود خب بین دوعدد ورودی صفر قرار دارد. حالا کافیه که ما این صفر را تبدیل به یک کنیم این طوری عملا جواب را ساخته ایم. اما یه اشکال اینجا هست وقتی ما صفر مابین دو عدد را تبدیل به یک کنیم باید یک انتهای رشته را تبدیل به بلانک کنیم تا جواب درست بگیریم. بیش ازاین دیگه توضیح جایز نیست و بهتره ماشین این تابع را ببینیم. 
 

Turing Machine


در اینجا به انتهای این جلسه میرسیم. امیدوارم مطالب این جلسه برایتان مفید بوده باشد و بهره کافی را برده باشید.
 

کلمات کلیدی

محمدرضا احندآبادی
مهندس نرم افزار
کارشناسی مهندسی نرم افزار
مدرس دوره نظریه زبان ها و ماشین ها