(۲۱ اسفند ۱۳۹۲ ۰۸:۱۳ ب.ظ)negar.v نوشته شده توسط:  تراگذری که یک رشته دودویی را به معادل مبنای هشت تبدیل می کند،دارای چند حالت است؟(فرض شود تعداد بیت های رشته دودویی مضربی از سه باشد)
گزینه ها :سه حالت/هشت حالت/هفت حالت/پنج حالت
دوستان کسی میتونه جواب و راه حل رو برام توضیح بده؟لطفا
کتاب راهیان ارشد گفته جواب سه حالت میشه و یک راه حل طولانی داره براش
اما کتاب هفت سال کنکور ارشد آزاد،انتشارات ساد گفته هفت حالت میشه و اینطور توضیح داده:تمام حالت های صفر تا هفت باینری ولی برای هر کدام سه بیت
کدوم جواب درسته؟


Sent from my ME172V using Tapatalk

سلام دوست عزیز.
پاسخ صحیح به نظر من :
اگر منظورش از تراگذر همون ماشین باشد، به طور حتم ماشین یا lba است یا تورینگ است و نمی تواند dfa یا pda باشد زیرا این دو تنها yes/no پاسخ می دهند در حالی که ماشین مورد سوال دارد یک تابع را روی رشته ورودی اعمال می کند و یک رشته تحویل می دهد.
از طرفی چنانچه به تمرینات فصل ۱۰ - بخش ۲ از کتاب ویرایش چهارم پروفسور لینز مراجعه کنید، دو تمرین با شماره های ۶ و ۷ آورده شده است.
۶- نشان دهید به ازای هر ماشین تورینگ، یک ماشین تورینگ استاندارد هم ارز وجود دارد که حداکثر ۶ حالت دارد.
۷- تا حد امکان تعداد حالت های مورد نیاز در تمرین ۶ را کاهش دهید (راهنمایی : کمترین تعداد ممکن سه جالت است).

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

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