(۰۸ خرداد ۱۳۹۵ ۰۱:۲۲ ق.ظ)pure liveliness نوشته شده توسط:  

(07 خرداد ۱۳۹۵ ۱۱:۱۵ ب.ظ)automata01 نوشته شده توسط:  با سلام
من در درس نظریه محاسبه خیلی ضعیفم و دلیلش هم این هست که استادم با اینکه خیلی با سواد هستند ولی قدرت تفهیم درس را به من و هم کلاسی هام ندارند.برای همین از شما کمک می خوام.لطفا اگر کسی این سوال را می دونه برام توضیح بده.
منبعی که به ما معرفی شده "مقدمه ای بر نظریه محاسبات" اثر سیپسر هست.
با تشکر

سلام. توی این مدت زمان کم تا امتحان ترم نمیشه کتاب مرجع خوند. شاید بشه یه تیکه هایی ازش رو خوند. جزوه ی دکتر کارگهی توی مانشت هست. اون رو بخونید خیلی خوبه. تورینگ هم خوب توضیح دادن وویسشون هم هست.
چند تا رشته امتحان میکنیم. هر رشته روی نوار قرار داره، اطراف رشته بی نهایت فضای خالی یا Blank هست که با B نشون میدن، وسط رشته امکان نداره این فضای خالی وجود داشته باشه. مثلا روی نوار رشته ی ۰۰۰۱۱۰۱۰۰ به صورت …. BBBBBBBB000110100BBBBBB…. هست. حالا، با رسیدن به هر حرف از رشته، یه حرف دیگه مثلا ۰ یا ۱ یا x یا هر چی جاش قرار داده میشه. معمولا رشته ای که انتخاب میشه اول به صورت یه تعدادی ۱ بعد ۰ بعد یه تعدادی ۱ انتخاب میشه. چون خیلی وقتا اون چیزی که ماشین تورینگ بر میگردونه یعنی عملی که روی این رشته انجام میده مثلا ضرب یک های قسمت اول یعنی قبل از صفر در ۱ ها ی قسمت دوم هست. نه لزوماََ البته. هر تابعی ممکنه پیاده سازی بشه توسط ماشین تورینگ.
توی این مسئله گام به گام عملیات رو توضیح میدیم. R حرکت به راست. L حرکت به چپ. B فضای خالی هست بعد و قبل از رشته.
مثلا حرکت ۱ , R <- یک یعنی اگر روی نوار حرف اول از رشته که خوندیم برابر با ۱ بود، به جاش ۱ بذاره، بره راست.
مسئله : توی اولین state هستیم. اگه اول رشته ۰ مشاهده کنیم، جاش X میذاریم میریم راست. حالا رسیدیم به q2 اگه ۰ ببینیم، جاش ۰ میذاریم میریم راست. و به همین صورت ادامه میدیم تا رسیدن به حالت نهایی. و بعد میبینیم چه رشته ای حاصل شده، بعد حدس میزنیم این ماشین تورینگ چه بلایی سر رشته آورده و چی رو محاسبه کرده... ادامه دارد :|

(۰۹ خرداد ۱۳۹۵ ۰۸:۵۶ ب.ظ)Jooybari نوشته شده توسط:  سلام.
با تشکر از توضیحات خانم pure liveliness، منم نتونستم زبان خوبی برای این ماشین تعریف کنم. بهترین تعریف، بنظرم زبان شامل رشته‌هاییه که حداقل ۲ تا حرف ۱ دارن. روش کار ماشین به این شکله:
اگه حرف اول ۰ بود بجاش x قرار بده و به راست برو. تا زمانی که به B نرسیدی به راست برو. بجای اولین B حرف ۰ رو قرار بده و به چپ برو تا به اولین حرف x در سمت چپ برسی. (یعنی اگه اولین حرف رشته ۰ بود بجاش بنویس x و به آخر رشته ۰ اضافه کن و برگرد به اولین حرف بعد از x.)
اگه ۱ دیدی به راست برو و تا زمانی که ۰ دیدی به راست برو. اگه ۱ دیدی به راست برو و پایان. (یعنی فقط ۲ تا ۱ داشته باشه. فقط رشته رو تغییر میده.)

(۱۰ خرداد ۱۳۹۵ ۰۳:۱۵ ب.ظ)automata01 نوشته شده توسط:  سلام
از ممنونم از همه
فقط یک سوال؟
مگه نباید جواب این سوال مثلا به سبک زیر باشه؟ چطور باید بهش برسیم.
۰+۱*(۱+۰)
اگه سوالم خیلی پیش پا افتادس مسخره ام نکنید
واقعا در نظریه افسیلنم.