سوال ۹۴ کنکور ارشد علوم کامپیوتر ۱۳۹۹
اهمیت
۰/۵
دو تغییر زیر را روی هد (head) ماشین‌های تورینگ استاندارد اعمال و دو نوع ماشین جدید تعریف می‌کنیم: نوع اول: در هر حرکت (هر انتقال) مکان هد بتواند ثابت باشد، یک خانه به راست یا یک خانه به چپ حرکت کند. نوع دوم: هد در حداکثر یک حرکت بتواند به سمت چپ حرکت کند (رو به ابتدای نوار) و به تعداد دلخواه به سمت راست حرکت کند. مجموعه زبان‌های دو نوع بالا به ترتیب عبارت است از مجموعه زبان‌های:
پاسخ صحیح: گزینهٔ A — تورینگ محاسبه‌پذیر ـ منظم
پاسخ تشریحی
The question compares the power of two head-movement variants against a standard Turing machine. …
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#turing-machine#head-movement#stay-option#regular-languages#one-way-head#crossing-sequence