نکات تستی کنکور نظریه زبانها - ماشین تورینگ

تمامی توابع ریاضی توسط ماشین تورینگ قابل محاسبه اند.

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

تفاوت ماشین تورینگ ها معمولا  در تعریف دلتای آنهاست. به تعریف آنها دقت شود.

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

به ازای هر ماشین تورینگ یک ماشین تورینگ حداکثر سه حالته وجود دارد و اگر چند نواره شود با حداکثر دو حالت میشود پیاده سازی شود.

بطور کلی در نامعین ها(چه پشته ای چه تورینگ و چه اوتوماتا متناهی) برد دلتا بصورت توانی از دو است.

اتوماتای دو پشته ای هم ارز با ماشین تورینگ است.

مجموعه تمام ماشین های تورینگ شمارش پذیر است.

مجموعه های شمارش پذیر تحت ضرب دکارتی متناهی و اجتماع بسته اند.

معلوم نیست که اتوماتای کراندار خطی معین با نامعین هم ارز هستند یا نه!

اتوماتای کراندار خطی ضعیفتر از ماشین تورینگ است(تنها مثالی که پیدا کردم همینه و پیچوندنهای همین)

چیزهایی که باید از کتاب خوانده شود: ماشین تورینگ و ماشین تورینگ استاندارد. حرکت در ماشین تورینگ. محاسبه پذیری. تز تورینگ. الگوریتم.هم ارزی ماشین های تورینگ. ماشین تورینگ سکون دار. ماشین تورینگ آفلاین. ماشین تورینگ چند نواره. ماشین تورینگ چند بعدی. ماشین تورینگ عمومی. شمارش پذیری و شمارش ناپذیری و روال شمارش. ترتیب محض. اتوماتای کراندار خطی lba.