ماشین تورینگ کیست؟ توضیح بده.
ماشین تورینگ(به انگلیسی: Turing machine) یک مدل ریاضی محاسبات است که یک ماشین انتزاعی را توصیف می‌کند که نمادها را روی یک نوار طبق جدول قوانین دستکاری می‌کند. با وجود سادگی مدل، قادر به اجرای هر الگوریتم کامپیوتری است.این ماشین روی یک نوار حافظه بی‌نهایت که به سلول‌های گسسته تقسیم شده است، کار می‌کند. هر سلول می‌تواند یک نماد از یک مجموعه متناهی از نمادها که الفبای رسمی ماشین نامیده می‌شود را نگه دارد. این ماشین دارای "سر"ی است که در هر لحظه از عملکرد ماشین روی یکی از این سلول‌ها قرار دارد و دارای "حالتی" است که از مجموعه‌ای متناهی از حالت‌ها انتخاب می‌شود. در هر گام از عملکرد، سر نماد موجود در سلول را می‌خواند. سپس، بر اساس نماد و حالت کنونی ماشین، نمادی در همان سلول می‌نویسد، سر را یک گام به چپ یا راست حرکت می‌دهد، یا محاسبه را متوقف می‌کند. انتخاب نماد جایگزینی که باید نوشته شود، جهت حرکت سر و توقف یا عدم توقف، بر اساس یک جدول متناهی است که مشخص می‌کند برای هر ترکیب از حالت کنونی و نماد خوانده‌شده چه کاری باید انجام شود. مانند یک برنامه کامپیوتری واقعی، ممکن است ماشین تورینگ وارد یک حلقه بی‌نهایت شود که هرگز متوقف نمی‌شود.ماشین تورینگ در سال ۱۹۳۶ توسط آلن تورینگ اختراع شد، که آن را "ماشین خودکار" (automatic machine) نامید. این آلونزو چرچ، مشاور دکترای تورینگ بود که بعداً واژه "ماشین تورینگ" را در یک نقد ابداع کرد. با این مدل، تورینگ توانست به دو پرسش پاسخ منفی دهد:بنابراین با ارائه توضیح ریاضی یک دستگاه بسیار ساده قادر به محاسبات دلخواه، او توانست ویژگی‌های محاسبات به‌طور کلی و به‌طور خاص غیرقابل محاسبه بودن مسئله تصمیم‌گیری "Entscheidungsproblem" را اثبات کند.ماشین‌های تورینگ وجود محدودیت‌های اساسی در قدرت محاسبات مکانیکی را اثبات کردند. در حالی که آن‌ها می‌توانند محاسبات دلخواه را بیان کنند، طراحی مینیمالیستی آن‌ها باعث می‌شود که برای محاسبات در عمل بسیار کند باشند: کامپیوترهای واقعی بر اساس طراحی‌های متفاوتی ساخته می‌شوند که برخلاف ماشین‌های تورینگ، از حافظه با دسترسی تصادفی استفاده می‌کنند.کامل بودن تورینگ توانایی یک مدل محاسباتی یا یک سیستم دستورها برای شبیه‌سازی یک ماشین تورینگ است. یک زبان برنامه‌نویسی که کامل تورینگ باشد، از نظر تئوری قادر به بیان تمامی وظایفی است که توسط کامپیوترها قابل انجام است؛ تقریباً همه زبان‌های برنامه‌نویسی کامل تورینگ هستند اگر محدودیت‌های حافظه متناهی نادیده گرفته شوند.نمای کلی.ماشین تورینگ یک مدل ایدئال از یک واحد پردازش مرکزی (CPU) است که تمام دستکاری داده‌های انجام شده توسط کامپیوتر را کنترل می‌کند. ماشین کلاسیک از حافظه ترتیبی برای ذخیره داده‌ها استفاده می‌کند. معمولاً این حافظه ترتیبی به صورت نواری با طول بی‌نهایت نمایش داده می‌شود که ماشین می‌تواند بر روی آن عملیات خواندن و نوشتن انجام دهد.در زمینه نظریه زبان‌های صوری، ماشین تورینگ (ماشین متناهی) قادر است برخی زیرمجموعه‌های دلخواه از رشته‌های معتبر یک الفبا را شمارش کند. مجموعه‌ای از رشته‌ها که می‌توانند به این روش شمارش شوند، زبان بازگشتی شمارا نامیده می‌شوند. ماشین تورینگ می‌تواند معادل به عنوان مدلی تعریف شود که رشته‌های ورودی معتبر را تشخیص می‌دهد، به جای اینکه رشته‌های خروجی را شمارش کند.با در نظر گرفتن یک ماشین تورینگ "M" و یک رشته دلخواه "s"، معمولاً نمی‌توان تصمیم گرفت که آیا "M" در نهایت "s" را تولید می‌کند یا خیر. این موضوع به دلیل غیرقابل حل بودن مسئله توقف است، که تأثیرات عمده‌ای بر محدودیت‌های نظری محاسبات دارد.ماشین تورینگ قادر به پردازش یک دستور زبان بدون محدودیت است، که به نوبه خود نشان می‌دهد که می‌تواند منطق مرتبه اول را به صورت قوی و به روش‌های بی‌نهایت ارزیابی کند. این امر به طور معروف از طریق حساب لامبدا نشان داده شده است.یک ماشین تورینگ که قادر به شبیه‌سازی هر ماشین تورینگ دیگری است، ماشین تورینگ جهانی (UTM، یا به سادگی ماشین جهانی) نامیده می‌شود. فرم رسمی ریاضی دیگر، حساب لامبدا، با ماهیت "جهانی" مشابه توسط آلونزو چرچ معرفی شد. کار چرچ با کار تورینگ در هم تنیده شد تا مبنای تز چرچ–تورینگ را تشکیل دهد. این تز بیان می‌کند که ماشین‌های تورینگ، حساب لامبدا، و دیگر فرم‌های مشابه محاسبه واقعاً مفهوم غیررسمی روش مؤثر در منطق و ریاضیات را در بر می‌گیرند و بنابراین مدلی ارائه می‌دهند که از طریق آن می‌توان درباره یک الگوریتم یا "روش مکانیکی" به صورت ریاضی دقیق و بدون وابستگی به هر فرم خاص استدلال کرد. مطالعه ویژگی‌های انتزاعی ماشین‌های تورینگ بسیاری از بینش‌ها را در علوم کامپیوتر، نظریه محاسبات و نظریه پیچیدگی محاسباتی به ارمغان آورده است.توصیف فیزیکی.در مقاله سال ۱۹۴۸ خود، "ماشین‌های هوشمند"، تورینگ نوشت که ماشین او شامل موارد زیر است:توصیف.ماشین تورینگ به طور ریاضی یک ماشینی را مدل‌سازی می‌کند که به طور مکانیکی روی یک نوار عمل می‌کند. بر روی این نوار نمادهایی وجود دارد که ماشین می‌تواند آنها را خوانده و یکی یکی بنویسد، با استفاده از یک سر نوار. عملیات به طور کامل توسط یک مجموعه محدود از دستورات ابتدایی تعیین می‌شود، مانند "در حالت 42، اگر نمادی که دیده می‌شود 0 است، 1 بنویس؛ اگر نمادی که دیده می‌شود 1 است، به حالت 17 تغییر کن؛ در حالت 17، اگر نمادی که دیده می‌شود 0 است، 1 بنویس و به حالت 6 تغییر کن؛" و غیره. در مقاله اصلی ("در مورد اعداد قابل محاسبه، با کاربردی در مسئله تصمیم‌گیری"، همچنین به ارجاعات زیر مراجعه کنید)، تورینگ نه یک مکانیزم، بلکه شخصی به نام "کامپیوتر" را تصور می‌کند که این قوانین مکانیکی قطعی را به طور غلامانه اجرا می‌کند (یا به گفته تورینگ، "به شکلی بی‌هدف").بیشتر به طور صریح، یک ماشین تورینگ شامل موارد زیر است:در مدل‌های 4-تایی، پاک کردن یا نوشتن یک نماد (aj1) و حرکت دادن سر به چپ یا راست (dk) به عنوان دستورات جداگانه مشخص شده‌اند. جدول به ماشین می‌گوید که (ia) یک نماد را پاک کند یا بنویسد "یا" (ib) سر را به چپ یا راست حرکت دهد، "و سپس" (ii) همان وضعیت یا وضعیت جدید تجویز شده را بپذیرد، اما نه هر دو عمل (ia) و (ib) را در یک دستور. در برخی مدل‌ها، اگر ورودی برای ترکیب فعلی نماد و وضعیت در جدول وجود نداشته باشد، آنگاه ماشین متوقف می‌شود؛ مدل‌های دیگر نیاز دارند که تمام ورودی‌ها پر شوند.هر بخش از ماشین (یعنی وضعیت آن، مجموعه نمادها و نوار استفاده‌شده در هر لحظه) و اعمال آن (مانند چاپ، پاک‌کردن و حرکت نوار) "محدود"، "گسسته" و "قابل تمایز" است؛ این نوار نامحدود و زمان اجرا است که به آن فضای ذخیره‌سازی نامحدود می‌دهد.تعریف منطقی (انتزاع ذهنی مفاهیم کلی).ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت formula_1، که در اینجا:به‌طور کلی formula_8 یک تابع جزئی روی formula_13 است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند.مقایسه با ماشین‌های واقعی.اغلب گفته می‌شود که ماشین تورینگ، برخلاف ماشین‌های اتومات، به اندازه ماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی که ماشین واقعی می‌تواند بکند هستند. چیزی که در این مطلب جا ماند این است که یک ماشین واقعی تنها می‌تواند در بسیاری از تنظیمات متناهی باشد؛ در واقع ماشین واقعی چیزی نیست جز یک ماشین اتوماتیک محدود خطی. از طرف دیگر ماشین تورینگ با ماشین‌هایی که دارای ظرفیت حافظه‌های نامحدود محاسباتی هستند، معادل است. از نظر تاریخی رایانه‌هایی که محاسبات را در حافظه داخلی شان انجام می‌دادند، بعدها توسعه داده شده‌اند.چرا ماشین‌های تورینگ مدل‌های مناسبی برای رایانه‌های واقعی هستند؟.۱. هرچیزی که ماشین واقعی می‌تواند محاسبه کند، ماشین تورینگ هم می‌تواند. برای مثال ماشین تورینگ، می‌تواند هرچیز طبق روالی که در زبان‌های برنامه‌نویسی پیدا می‌شود شبیه‌سازی کند. همچنین می‌تواند فرایندهای بازگشتی و هریک از پارامترهای مکانیسم شناخته شده را شبیه‌سازی کند.۲. تفاوت، تنها در قابلیت ماشین تورینگ برای دخالت در مقدار محدودی اطلاعات نهفته است؛ بنابراین، ماشین تورینگ می‌تواند در مدت زمان محدودی، در اطلاعات دخالت داشته باشد هر چند که ماشین تورینگ فاقد حافظه به عنوان انچه امروز شناخته می شود بود.۳. ماشین واقعی همانند ماشین‌های تورینگ می‌توانند حافظه مورد نیازش را به کمک دیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در حافظه‌شان ندارند.۴. شرح برنامه‌های ماشین واقعی که از مدل ساده‌تر انتزاعی استفاده می‌کنند، پیچیده‌تر از شرح برنامه‌های ماشین تورینگ است.۵. ماشین تورینگ الگوریتم‌های مستقل را که چقدر از حافظه استفاده می‌کنند، توصیف می‌کند. در دارایی حافظه همهٔ ماشین‌ها، محدودیتی وجود دارد؛ ولی این محدودیت می‌تواند خود سرانه در طول زمان افزایش یابد.ماشین تورینگ به ما اجازه می‌دهد دربارهٔ الگوریتم‌هایی که برای همیشه نگه داشته می‌شوند، توصیفاتی ارائه دهیم؛ بدون در نظر گرفتن پیش رفت در معماری محاسبات با ماشین معمولی.۶. ماشین تورینگ جملات الگوریتم را ساده می‌کند. الگوریتم‌های در حال اجرا در ماشین آلات انتزاعی معادل تورینگ، معمولاً نسبت به همتایان خود که در ماشین‌های واقعی در حال اجرا هستند عمومی ترند. زیرا آن‌ها دارای دقت دلخواه در انواع اطلاعات قابل دسترس هستند و هیچ‌وقت با شرایط غیرمنتظره روبرو نمی‌شوند. یکی از نقطه ضعف‌های ماشین تورینگ این است که برنامه‌های واقعی که نوشته می‌شوند ورودی‌های نامحدودی را در طول زمان دریافت می‌کنند؛ در نتیجه هرگز متوقف نمی‌شوند.مقایسه با ماشین‌های واقعی.ماشین‌های تورینگ از برخی دیگر از انواع اتوماتا، مانند ماشین حالت محدود و اتوماتای پشته‌ای، قدرتمندتر هستند. بر اساس اصل کلی چرچ–تورینگ، ماشین‌های تورینگ به اندازه‌ی ماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی هستند که یک برنامه‌ی واقعی می‌تواند انجام دهد. نکته‌ای که در این بیان نادیده گرفته می‌شود این است که، چون یک ماشین واقعی تنها می‌تواند تعداد محدودی "پیکربندی" داشته باشد، در واقع چیزی جز یک ماشین حالت محدود نیست، در حالی که یک ماشین تورینگ فضای ذخیره‌سازی نامحدودی برای محاسبات خود دارد.روش‌های مختلفی برای توضیح اینکه چرا ماشین‌های تورینگ مدل‌های مفیدی از کامپیوترهای واقعی هستند وجود دارد:محدودیت‌ها.نظریه پیچیدگی محاسباتی.یک محدودیت ماشین‌های تورینگ این است که آن‌ها نقاط قوت یک ترتیب خاص را به‌خوبی مدل‌سازی نمی‌کنند. به‌عنوان مثال، کامپیوترهای مدرن برنامه ذخیره‌شده در واقع نمونه‌هایی از یک فرم خاص از ماشین انتزاعی به نام مدل ماشین برنامه ذخیره‌شده با دسترسی تصادفی (RASP) هستند. مانند ماشین تورینگ جهانی، RASP برنامه خود را در "حافظه" خارجی نسبت به "دستورات" ماشین حالت محدود خود ذخیره می‌کند. برخلاف ماشین تورینگ جهانی، RASP تعداد نامحدودی از "ثبات‌های" متمایز، شماره‌گذاری‌شده و اما بدون حد "ثبت" دارد — سلول‌های حافظه‌ای که می‌توانند هر عدد صحیحی را در خود نگهدارند (مراجعه کنید به Elgot و Robinson (1964)، Hartmanis (1971)، و به‌ویژه Cook-Rechow (1973); منابع در ماشین دسترسی تصادفی). ماشین حالت محدود RASP قابلیت آدرس‌دهی غیرمستقیم دارد (مثلاً محتویات یک ثبات می‌تواند به‌عنوان آدرس برای مشخص کردن یک ثبات دیگر استفاده شود)؛ بنابراین "برنامه" RASP می‌تواند به هر ثبات در دنباله ثبات‌ها دسترسی پیدا کند. نتیجه این تفاوت این است که بهینه‌سازی‌های محاسباتی‌ای وجود دارند که می‌توانند بر اساس شاخص‌های حافظه انجام شوند، که در ماشین تورینگ عمومی ممکن نیستند؛ بنابراین وقتی ماشین‌های تورینگ به‌عنوان مبنای تعیین محدودیت زمان اجرا استفاده می‌شوند، می‌توان یک "حد پایین کاذب" را برای زمان‌های اجرای الگوریتم‌های خاص ثابت کرد (به دلیل فرض ساده‌سازی غلط در مورد ماشین تورینگ). یکی از مثال‌های این موضوع جستجوی دودویی است، الگوریتمی که می‌تواند نشان داده شود که سریع‌تر اجرا می‌شود هنگامی که از مدل محاسباتی RASP استفاده می‌شود تا مدل ماشین تورینگ.تعامل.در روزهای اولیه محاسبات، استفاده از کامپیوتر معمولاً به پردازش دسته‌ای محدود بود، یعنی کارهای غیرتعاملی که هر کدام داده‌های خروجی را از داده‌های ورودی معین تولید می‌کردند. نظریه محاسبات‌پذیری، که محاسبات‌پذیری توابع از ورودی‌ها به خروجی‌ها را مطالعه می‌کند و برای آن ماشین‌های تورینگ اختراع شدند، بازتابی از این عمل بود.از دهه 1970، استفاده تعاملی از کامپیوترها به‌طور قابل توجهی رایج‌تر شد. به‌طور اصولی، این را می‌توان با داشتن یک عامل خارجی که به‌طور همزمان از نوار می‌خواند و به آن می‌نویسد، مدل‌سازی کرد، اما این معمولاً مطابق با نحوه تعامل واقعی نیست؛ بنابراین، هنگام توصیف تعامل، گزینه‌های دیگری مانند اتوماتای ورودی/خروجی معمولاً ترجیح داده می‌شوند.تاریخچه.زمینه تاریخی: ماشین‌های محاسباتی.رابین گاندی (۱۹۱۹–۱۹۹۵)—دانشجوی آلن تورینگ (۱۹۱۲–۱۹۵۴) و دوست مادام‌العمر او—نسب مفهوم "ماشین محاسباتی" را به چارلز ببیج (حدود ۱۸۳۴) برمی‌گرداند و حتی "تز ببیج" را پیشنهاد می‌دهد:تحلیل گاندی از ماشین تحلیلی ببیج پنج عملیات زیر را توصیف می‌کند (نگاه کنید به ص. ۵۲–۵۳):گاندی بیان می‌کند که "توابعی که می‌توانند توسط (۱)، (۲)، و (۴) محاسبه شوند دقیقاً آن‌هایی هستند که قابل محاسبه با تورینگ هستند." (ص. ۵۳). او به پیشنهادهای دیگر برای "ماشین‌های محاسباتی جهانی" از جمله پرسی لودگیت (۱۹۰۹)، لئوناردو تورس کوئودو (۱۹۱۴)، موریس داکن (۱۹۲۲)، لویی کوفینیال (۱۹۳۳)، ونوار بوش (۱۹۳۶)، هوارد آیکن (۱۹۳۷) اشاره می‌کند. اما:مسئله تصمیم‌گیری: سؤال دهم هیلبرت در سال ۱۹۰۰.با توجه به مسائل هیلبرت که توسط ریاضیدان مشهور دیوید هیلبرت در سال ۱۹۰۰ مطرح شد، جنبه‌ای از مسئله شماره ۱۰ تقریباً ۳۰ سال شناور بود تا زمانی که به‌طور دقیق مطرح شد. بیان اصلی هیلبرت برای شماره ۱۰ به شرح زیر است:تا سال ۱۹۲۲، این مفهوم "مسئله تصمیم‌گیری" کمی توسعه یافت، و هاینریش بهمان اظهار داشت که: