تالار گفتمان مانشت

سلام
ماشین تورینگ {a^(n^2 ):n≥1} (ِیعنی a به توان n به توان 2 ) چیه؟؟؟

سلام. باید از رابطه [tex](n 1)^2=n^2 2n 1[/tex] استفاده کنید. در هر لحظه هم باید n و n^2 رو داشته باشید.

ممنونم

میشه یکم بیشتر برام توضیح بدید که دقیقا چه جوری نوشته میشه؟

(26 دى 1392 01:49 ب.ظ)venoos71 نوشته شده توسط: [ -> ]ممنونم

میشه یکم بیشتر برام توضیح بدید که دقیقا چه جوری نوشته میشه؟

یه رشته از a به ما میدن و قراره مشخص کنیم تعداد a ها برابر n^2 هست یا نه!
(برای n=1) اولین a رو بصورت b مینویسیم. اگه حرف سمت راست آخخر رشته بود به پذیرش میریم. در غیر این صورت از رابطه ای که گفتم استفاده میکنیم.
دو برابر b هامون بعلاوه 2، aهای بعد از a و c رو به c تبدیل میکنیم و اولین c سمت چپ رو به b تغییر میدیم. (این تغییرات برای همون رابطست.)
اگه رشته a ها تموم شد و همه cها رو روی a نوشتیم میریم به حالت پذیرش.

اگه ممکنه ماشین توریگشو بنویسید
من باید جوابشو تا امشب بدست بیارم

اینم جواب. توضیحاتش تو ارسال قبلیمه.