ماشین تورینگ

ماشین تورینگ(به انگلیسی: Turing machine) یک مدل ریاضی محاسبات است که یک ماشین انتزاعیمینسکی ۱۹۶۷:۱۰۷ "در مقاله ۱۹۳۶، آ. ام. تورینگ کلاس ماشین‌های انتزاعی را تعریف کرد که اکنون به نام او نامیده می‌شود. ماشین تورینگ یک ماشین حالت محدود است که با نوع خاصی از محیط - نوار آن - همراه است که می‌تواند در آن توالی نمادها را ذخیره و بعداً بازیابی کند." همچنین استون ۱۹۷۲:۸ که واژه "ماشین" را در گیومه می‌آورد. را توصیف می‌کند که نمادها را روی یک نوار طبق جدول قوانین دستکاری می‌کند.استون ۱۹۷۲:۸ بیان می‌کند که "این 'ماشین' یک مدل ریاضی انتزاعی است"، همچنین رجوع کنید به سیپسر ۲۰۰۶:۱۳۷ به بعد که "مدل ماشین تورینگ" را توصیف می‌کند. راجرز ۱۹۸۷ (۱۹۶۷):۱۳ به "توصیف تورینگ" اشاره می‌کند، بولوس، برگس و جفری ۲۰۰۲:۲۵ به "یک نوع خاص از ماشین ایده‌آل" اشاره می‌کنند. با وجود سادگی مدل، قادر به اجرای هر الگوریتم کامپیوتری است.سیپسر ۲۰۰۶:۱۳۷ "یک ماشین تورینگ می‌تواند هر کاری که یک کامپیوتر واقعی می‌تواند انجام دهد را انجام دهد."

این ماشین روی یک نوار حافظه بی‌نهایترجوع کنید به سیپسر ۲۰۰۲:۱۳۷. همچنین، راجرز ۱۹۸۷ (۱۹۶۷):۱۳ یک "نوار کاغذی با طول بی‌نهایت در هر دو جهت" را توصیف می‌کند. مینسکی ۱۹۶۷:۱۱۸ بیان می‌کند "این نوار به عنوان بی‌نهایت در هر دو جهت در نظر گرفته می‌شود." بولوس، برگس و جفری ۲۰۰۲:۲۵ امکان "وجود کسی که در هر انتها مستقر است تا مربع‌های خالی اضافی را در صورت نیاز اضافه کند" را شامل می‌شود. که به سلول‌های گسستهرجوع کنید به راجرز ۱۹۸۷ (۱۹۶۷):۱۳. نویسندگان دیگر از واژه "مربع" استفاده می‌کنند، مثلاً بولوس، برگس، جفری ۲۰۰۲:۳۵، مینسکی ۱۹۶۷:۱۱۷، پنروز ۱۹۸۹:۳۷. تقسیم شده است، کار می‌کند. هر سلول می‌تواند یک نماد از یک مجموعه متناهی از نمادها که الفبای رسمی ماشین نامیده می‌شود را نگه دارد. این ماشین دارای "سر"ی است که در هر لحظه از عملکرد ماشین روی یکی از این سلول‌ها قرار دارد و دارای "حالتی" است که از مجموعه‌ای متناهی از حالت‌ها انتخاب می‌شود. در هر گام از عملکرد، سر نماد موجود در سلول را می‌خواند. سپس، بر اساس نماد و حالت کنونی ماشین، نمادی در همان سلول می‌نویسد، سر را یک گام به چپ یا راست حرکت می‌دهد،بولوس، برگس، جفری ۲۰۰۲:۲۵ ماشین را به عنوان یک شیء متحرک روی نوار نشان می‌دهند. پنروز ۱۹۸۹:۳۶-۳۷ خود را با نوار بی‌نهایت "ناراحت" می‌بیند و بیان می‌کند که "ممکن است سخت باشد که آن را جابجا کنیم!" او ترجیح می‌دهد نوار را به عنوان محیطی خارجی در نظر بگیرد که دستگاه محدود ما می‌تواند در آن حرکت کند. او پیشنهاد می‌دهد که "دریافت تمامی ورودی‌ها از این محیط صورت می‌گیرد". برخی از انواع مدل ماشین تورینگ نیز اجازه می‌دهند که سر در همان موقعیت باقی بماند یا متوقف شود. یا محاسبه را متوقف می‌کند. انتخاب نماد جایگزینی که باید نوشته شود، جهت حرکت سر و توقف یا عدم توقف، بر اساس یک جدول متناهی است که مشخص می‌کند برای هر ترکیب از حالت کنونی و نماد خوانده‌شده چه کاری باید انجام شود. مانند یک برنامه کامپیوتری واقعی، ممکن است ماشین تورینگ وارد یک حلقه بی‌نهایت شود که هرگز متوقف نمی‌شود.

ماشین تورینگ در سال ۱۹۳۶ توسط آلن تورینگ اختراع شد، که آن را "ماشین خودکار" (automatic machine) نامید.رجوع کنید به پاورقی در دیویس ۲۰۰۰:۱۵۱. این آلونزو چرچ، مشاور دکترای تورینگ بود که بعداً واژه "ماشین تورینگ" را در یک نقد ابداع کرد.رجوع کنید به یادداشت در پیشگفتار مجموعه آثار آلونزو چرچ () با این مدل، تورینگ توانست به دو پرسش پاسخ منفی دهد:
 آیا ماشینی وجود دارد که بتواند تعیین کند آیا یک ماشین دلخواه روی نوارش "مدور" است (مثلاً متوقف می‌شود یا ادامه کار محاسباتی خود را انجام نمی‌دهد)؟
 آیا ماشینی وجود دارد که بتواند تعیین کند آیا یک ماشین دلخواه روی نوارش یک نماد خاص را چاپ می‌کند یا خیر؟تورینگ ۱۹۳۶ در غیرقابل تصمیم‌گیری ۱۹۶۵:۱۳۲-۱۳۴؛ تعریف تورینگ از "مدور" در صفحه ۱۱۹ آمده است.
بنابراین با ارائه توضیح ریاضی یک دستگاه بسیار ساده قادر به محاسبات دلخواه، او توانست ویژگی‌های محاسبات به‌طور کلی و به‌طور خاص غیرقابل محاسبه بودن مسئله تصمیم‌گیری Entscheidungsproblem را اثبات کند.تورینگ ۱۹۳۶ در غیرقابل تصمیم‌گیری ۱۹۶۵:۱۴۵

ماشین‌های تورینگ وجود محدودیت‌های اساسی در قدرت محاسبات مکانیکی را اثبات کردند.سیپسر ۲۰۰۶:۱۳۷ مشاهده می‌کند که "یک ماشین تورینگ می‌تواند هر کاری که یک کامپیوتر واقعی می‌تواند انجام دهد، انجام دهد. با این حال، حتی یک ماشین تورینگ نیز نمی‌تواند برخی مسائل را حل کند. به معنای واقعی کلمه، این مسائل فراتر از محدودیت‌های نظری محاسبات هستند." در حالی که آن‌ها می‌توانند محاسبات دلخواه را بیان کنند، طراحی مینیمالیستی آن‌ها باعث می‌شود که برای محاسبات در عمل بسیار کند باشند: کامپیوترهای واقعی بر اساس طراحی‌های متفاوتی ساخته می‌شوند که برخلاف ماشین‌های تورینگ، از حافظه با دسترسی تصادفی استفاده می‌کنند.

کامل بودن تورینگ توانایی یک مدل محاسباتی یا یک سیستم دستورها برای شبیه‌سازی یک ماشین تورینگ است. یک زبان برنامه‌نویسی که کامل تورینگ باشد، از نظر تئوری قادر به بیان تمامی وظایفی است که توسط کامپیوترها قابل انجام است؛ تقریباً همه زبان‌های برنامه‌نویسی کامل تورینگ هستند اگر محدودیت‌های حافظه متناهی نادیده گرفته شوند.

 نمای کلی 
ماشین تورینگ یک مدل ایدئال از یک واحد پردازش مرکزی (CPU) است که تمام دستکاری داده‌های انجام شده توسط کامپیوتر را کنترل می‌کند. ماشین کلاسیک از حافظه ترتیبی برای ذخیره داده‌ها استفاده می‌کند. معمولاً این حافظه ترتیبی به صورت نواری با طول بی‌نهایت نمایش داده می‌شود که ماشین می‌تواند بر روی آن عملیات خواندن و نوشتن انجام دهد.

در زمینه نظریه زبان‌های صوری، ماشین تورینگ (ماشین متناهی) قادر است برخی زیرمجموعه‌های دلخواه از رشته‌های معتبر یک الفبا را شمارش کند. مجموعه‌ای از رشته‌ها که می‌توانند به این روش شمارش شوند، زبان بازگشتی شمارا نامیده می‌شوند. ماشین تورینگ می‌تواند معادل به عنوان مدلی تعریف شود که رشته‌های ورودی معتبر را تشخیص می‌دهد، به جای اینکه رشته‌های خروجی را شمارش کند.

با در نظر گرفتن یک ماشین تورینگ M و یک رشته دلخواه s، معمولاً نمی‌توان تصمیم گرفت که آیا M در نهایت s را تولید می‌کند یا خیر. این موضوع به دلیل غیرقابل حل بودن مسئله توقف است، که تأثیرات عمده‌ای بر محدودیت‌های نظری محاسبات دارد.

ماشین تورینگ قادر به پردازش یک دستور زبان بدون محدودیت است، که به نوبه خود نشان می‌دهد که می‌تواند منطق مرتبه اول را به صورت قوی و به روش‌های بی‌نهایت ارزیابی کند. این امر به طور معروف از طریق حساب لامبدا نشان داده شده است.

یک ماشین تورینگ که قادر به شبیه‌سازی هر ماشین تورینگ دیگری است، ماشین تورینگ جهانی (UTM، یا به سادگی ماشین جهانی) نامیده می‌شود. فرم رسمی ریاضی دیگر، حساب لامبدا، با ماهیت "جهانی" مشابه توسط آلونزو چرچ معرفی شد. کار چرچ با کار تورینگ در هم تنیده شد تا مبنای تز چرچ–تورینگ را تشکیل دهد. این تز بیان می‌کند که ماشین‌های تورینگ، حساب لامبدا، و دیگر فرم‌های مشابه محاسبه واقعاً مفهوم غیررسمی روش مؤثر در منطق و ریاضیات را در بر می‌گیرند و بنابراین مدلی ارائه می‌دهند که از طریق آن می‌توان درباره یک الگوریتم یا "روش مکانیکی" به صورت ریاضی دقیق و بدون وابستگی به هر فرم خاص استدلال کرد. مطالعه ویژگی‌های انتزاعی ماشین‌های تورینگ بسیاری از بینش‌ها را در علوم کامپیوتر، نظریه محاسبات و نظریه پیچیدگی محاسباتی به ارمغان آورده است.

 توصیف فیزیکی 
در مقاله سال ۱۹۴۸ خود، "ماشین‌های هوشمند"، تورینگ نوشت که ماشین او شامل موارد زیر است:

 توصیف 
ماشین تورینگ به طور ریاضی یک ماشینی را مدل‌سازی می‌کند که به طور مکانیکی روی یک نوار عمل می‌کند. بر روی این نوار نمادهایی وجود دارد که ماشین می‌تواند آنها را خوانده و یکی یکی بنویسد، با استفاده از یک سر نوار. عملیات به طور کامل توسط یک مجموعه محدود از دستورات ابتدایی تعیین می‌شود، مانند "در حالت 42، اگر نمادی که دیده می‌شود 0 است، 1 بنویس؛ اگر نمادی که دیده می‌شود 1 است، به حالت 17 تغییر کن؛ در حالت 17، اگر نمادی که دیده می‌شود 0 است، 1 بنویس و به حالت 6 تغییر کن؛" و غیره. در مقاله اصلی ("در مورد اعداد قابل محاسبه، با کاربردی در مسئله تصمیم‌گیری"، همچنین به ارجاعات زیر مراجعه کنید)، تورینگ نه یک مکانیزم، بلکه شخصی به نام "کامپیوتر" را تصور می‌کند که این قوانین مکانیکی قطعی را به طور غلامانه اجرا می‌کند (یا به گفته تورینگ، "به شکلی بی‌هدف").



بیشتر به طور صریح، یک ماشین تورینگ شامل موارد زیر است:
 یک نوار که به سلول‌هایی تقسیم شده است، که یکی پس از دیگری قرار دارند. هر سلول شامل نمادی از یک الفبای محدود است. الفبا شامل یک نماد ویژه فضای خالی (که در اینجا به صورت '0' نوشته شده است) و یک یا چند نماد دیگر است. فرض می‌شود که نوار به طور دلخواه به سمت چپ و راست قابل گسترش است، به طوری که ماشین تورینگ همیشه به اندازه کافی نوار برای محاسبات خود دارد. سلول‌هایی که قبلاً نوشته نشده‌اند، فرض می‌شود که با نماد فضای خالی پر شده‌اند. در برخی مدل‌ها، نوار یک انتهای چپ دارد که با یک نماد ویژه علامت‌گذاری شده است؛ نوار به سمت راست گسترش می‌یابد یا به طور نامحدود قابل گسترش است.
 یک سر که می‌تواند نمادها را روی نوار بخواند و بنویسد و نوار را یک سلول به چپ و راست (و فقط یک سلول) حرکت دهد. در برخی مدل‌ها، سر حرکت می‌کند و نوار ثابت است.
 یک ثبت وضعیت که وضعیت ماشین تورینگ را ذخیره می‌کند، که یکی از تعداد محدودی است. در بین این وضعیت‌ها، وضعیت ویژه وضعیت شروع است که با آن ثبت وضعیت مقداردهی اولیه می‌شود. این وضعیت‌ها، به گفته تورینگ، جایگزین "وضعیت ذهنی" هستند که یک فرد در حین انجام محاسبات معمولاً در آن قرار دارد.
 یک جدول محدودگاهی اوقات به آن جدول عملیات یا تابع انتقال گفته می‌شود. از دستوراتمعمولاً پنج‌تایی‌ها [5-تایی‌ها]: qiaj→qi1aj1dk، اما گاهی اوقات چهار‌تایی‌ها [4-تایی‌ها]. که، با توجه به وضعیت(qi) که ماشین در آن قرار دارد و نماد(aj) که در حال خواندن از نوار است (نمادی که در حال حاضر زیر سر قرار دارد)، به ماشین می‌گوید که در ترتیب زیر عمل کند (برای مدل‌های 5-تایی):
 یا نمادی را پاک کند یا نمادی بنویسد (جایگزینی aj با aj1).
 سر را حرکت دهد (که توسط dk توصیف می‌شود و می‌تواند مقادیر 'L' برای یک گام به چپ یا 'R' برای یک گام به راست یا 'N' برای ایستادن در همان مکان داشته باشد).
 همان وضعیت یا یک وضعیت جدید که تجویز شده است را بپذیرد (به وضعیت qi1 برود).
در مدل‌های 4-تایی، پاک کردن یا نوشتن یک نماد (aj1) و حرکت دادن سر به چپ یا راست (dk) به عنوان دستورات جداگانه مشخص شده‌اند. جدول به ماشین می‌گوید که (ia) یک نماد را پاک کند یا بنویسد یا (ib) سر را به چپ یا راست حرکت دهد، و سپس (ii) همان وضعیت یا وضعیت جدید تجویز شده را بپذیرد، اما نه هر دو عمل (ia) و (ib) را در یک دستور. در برخی مدل‌ها، اگر ورودی برای ترکیب فعلی نماد و وضعیت در جدول وجود نداشته باشد، آنگاه ماشین متوقف می‌شود؛ مدل‌های دیگر نیاز دارند که تمام ورودی‌ها پر شوند.

هر بخش از ماشین (یعنی وضعیت آن، مجموعه نمادها و نوار استفاده‌شده در هر لحظه) و اعمال آن (مانند چاپ، پاک‌کردن و حرکت نوار) محدود، گسسته و قابل تمایز است؛ این نوار نامحدود و زمان اجرا است که به آن فضای ذخیره‌سازی نامحدود می‌دهد.

 تعریف منطقی (انتزاع ذهنی مفاهیم کلی) 
ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت ، که در اینجا:
  برای نمایش مفهوم ماشین انتخاب شده‌است.
  مجموعه‌ای است متناهی، از حالات داخلی.Internal States
  مجموعه‌ای متناهی موسوم به الفبای نوارTape alphabet و حاوی نمادی مخصوص  برای نمایش یک فاصلهٔ خالی روی نوار ماشین است.
  زیرمجموعه‌ای است از  و موسوم به الفبای ورودی. یعنی الفبای ورودی زیر مجموعه‌ای از الفبای نوار است که شامل خالی نیست. نوارهای خالی نمی‌توانند به عنوان ورودی استفاده شوند.
  عبارت است از یک تابع جزئی،Partial function موسوم به تابع انتقالTransition function از دامنهٔ  به برد .
  حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را در آن آغاز می‌کنیم.
به‌طور کلی  یک تابع جزئی روی  است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند.

 مقایسه با ماشین‌های واقعی 
اغلب گفته می‌شود که ماشین تورینگ، برخلاف ماشین‌های اتومات، به اندازه ماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی که ماشین واقعی می‌تواند بکند هستند. چیزی که در این مطلب جا ماند این است که یک ماشین واقعی تنها می‌تواند در بسیاری از تنظیمات متناهی باشد؛ در واقع ماشین واقعی چیزی نیست جز یک ماشین اتوماتیک محدود خطی. از طرف دیگر ماشین تورینگ با ماشین‌هایی که دارای ظرفیت حافظه‌های نامحدود محاسباتی هستند، معادل است. از نظر تاریخی رایانه‌هایی که محاسبات را در حافظه داخلی شان انجام می‌دادند، بعدها توسعه داده شده‌اند.

 چرا ماشین‌های تورینگ مدل‌های مناسبی برای رایانه‌های واقعی هستند؟ 
۱. هرچیزی که ماشین واقعی می‌تواند محاسبه کند، ماشین تورینگ هم می‌تواند. برای مثال ماشین تورینگ، می‌تواند هرچیز طبق روالی که در زبان‌های برنامه‌نویسی پیدا می‌شود شبیه‌سازی کند. همچنین می‌تواند فرایندهای بازگشتی و هریک از پارامترهای مکانیسم شناخته شده را شبیه‌سازی کند.

۲. تفاوت، تنها در قابلیت ماشین تورینگ برای دخالت در مقدار محدودی اطلاعات نهفته است؛ بنابراین، ماشین تورینگ می‌تواند در مدت زمان محدودی، در اطلاعات دخالت داشته باشد هر چند که ماشین تورینگ فاقد حافظه به عنوان انچه امروز شناخته می شود بود.

۳. ماشین واقعی همانند ماشین‌های تورینگ می‌توانند حافظه مورد نیازش را به کمک دیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در حافظه‌شان ندارند.

۴. شرح برنامه‌های ماشین واقعی که از مدل ساده‌تر انتزاعی استفاده می‌کنند، پیچیده‌تر از شرح برنامه‌های ماشین تورینگ است.

۵. ماشین تورینگ الگوریتم‌های مستقل را که چقدر از حافظه استفاده می‌کنند، توصیف می‌کند. در دارایی حافظه همهٔ ماشین‌ها، محدودیتی وجود دارد؛ ولی این محدودیت می‌تواند خود سرانه در طول زمان افزایش یابد.

ماشین تورینگ به ما اجازه می‌دهد دربارهٔ الگوریتم‌هایی که برای همیشه نگه داشته می‌شوند، توصیفاتی ارائه دهیم؛ بدون در نظر گرفتن پیش رفت در معماری محاسبات با ماشین معمولی.

۶. ماشین تورینگ جملات الگوریتم را ساده می‌کند. الگوریتم‌های در حال اجرا در ماشین آلات انتزاعی معادل تورینگ، معمولاً نسبت به همتایان خود که در ماشین‌های واقعی در حال اجرا هستند عمومی ترند. زیرا آن‌ها دارای دقت دلخواه در انواع اطلاعات قابل دسترس هستند و هیچ‌وقت با شرایط غیرمنتظره روبرو نمی‌شوند. یکی از نقطه ضعف‌های ماشین تورینگ این است که برنامه‌های واقعی که نوشته می‌شوند ورودی‌های نامحدودی را در طول زمان دریافت می‌کنند؛ در نتیجه هرگز متوقف نمی‌شوند.

مقایسه با ماشین‌های واقعی
ماشین‌های تورینگ از برخی دیگر از انواع اتوماتا، مانند ماشین حالت محدود و اتوماتای پشته‌ای، قدرتمندتر هستند. بر اساس اصل کلی چرچ–تورینگ، ماشین‌های تورینگ به اندازه‌ی ماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی هستند که یک برنامه‌ی واقعی می‌تواند انجام دهد. نکته‌ای که در این بیان نادیده گرفته می‌شود این است که، چون یک ماشین واقعی تنها می‌تواند تعداد محدودی پیکربندی داشته باشد، در واقع چیزی جز یک ماشین حالت محدود نیست، در حالی که یک ماشین تورینگ فضای ذخیره‌سازی نامحدودی برای محاسبات خود دارد.

روش‌های مختلفی برای توضیح اینکه چرا ماشین‌های تورینگ مدل‌های مفیدی از کامپیوترهای واقعی هستند وجود دارد:

 هر چیزی که یک کامپیوتر واقعی می‌تواند محاسبه کند، یک ماشین تورینگ نیز می‌تواند محاسبه کند. به عنوان مثال: "یک ماشین تورینگ می‌تواند هر نوع زیرروال موجود در زبان‌های برنامه‌نویسی را شبیه‌سازی کند، از جمله روش‌های بازگشتی و هر یک از مکانیزم‌های شناخته‌شده انتقال پارامتر" (هوپکروفت و اولمن صفحه 157). یک ماشین حالت محدود بزرگ نیز می‌تواند هر کامپیوتر واقعی را مدل‌سازی کند، بدون در نظر گرفتن ورودی/خروجی. بنابراین، یک بیانیه درباره‌ی محدودیت‌های ماشین‌های تورینگ، برای کامپیوترهای واقعی نیز صادق است.
 تفاوت فقط در توانایی ماشین تورینگ برای دستکاری مقدار نامحدودی از داده‌ها است. با این حال، با توجه به زمان محدود، یک ماشین تورینگ (مانند یک ماشین واقعی) تنها می‌تواند مقدار محدودی از داده‌ها را دستکاری کند.
 مانند یک ماشین تورینگ، یک ماشین واقعی می‌تواند فضای ذخیره‌سازی خود را با نیاز به خرید دیسک‌ها یا رسانه‌های ذخیره‌سازی دیگر گسترش دهد.
 توصیف برنامه‌های ماشین‌های واقعی با استفاده از مدل‌های انتزاعی ساده‌تر اغلب پیچیده‌تر از توصیف‌ها با استفاده از ماشین‌های تورینگ است. به عنوان مثال، یک ماشین تورینگ که یک الگوریتم را توصیف می‌کند می‌تواند چند صد وضعیت داشته باشد، در حالی که معادل آن در یک ماشین واقعی، یک اتوماتای قطعی حالت محدود (DFA) ممکن است میلیاردها وضعیت داشته باشد. این امر مدل‌سازی DFA را غیرممکن می‌کند.
 ماشین‌های تورینگ الگوریتم‌ها را به‌طور مستقل از مقدار حافظه‌ای که استفاده می‌کنند توصیف می‌کنند. برای هر ماشینی حدی برای حافظه وجود دارد، اما این حد می‌تواند به طور دلخواه در طول زمان افزایش یابد. ماشین‌های تورینگ به ما این امکان را می‌دهند که بیانیه‌هایی درباره‌ی الگوریتم‌ها بدهیم که (از نظر نظری) برای همیشه صادق خواهند بود، صرف‌نظر از پیشرفت‌های معماری ماشین‌های محاسباتی متداول.
 الگوریتم‌هایی که روی ماشین‌های انتزاعی معادل تورینگ اجرا می‌شوند، می‌توانند انواع داده‌ای با دقت دلخواه داشته باشند و نیازی به مواجهه با شرایط غیرمنتظره (از جمله، اما نه محدود به، تمام شدن حافظه) نخواهند داشت.


محدودیت‌ها

نظریه پیچیدگی محاسباتی

یک محدودیت ماشین‌های تورینگ این است که آن‌ها نقاط قوت یک ترتیب خاص را به‌خوبی مدل‌سازی نمی‌کنند. به‌عنوان مثال، کامپیوترهای مدرن برنامه ذخیره‌شده در واقع نمونه‌هایی از یک فرم خاص از ماشین انتزاعی به نام مدل ماشین برنامه ذخیره‌شده با دسترسی تصادفی (RASP) هستند. مانند ماشین تورینگ جهانی، RASP برنامه خود را در "حافظه" خارجی نسبت به "دستورات" ماشین حالت محدود خود ذخیره می‌کند. برخلاف ماشین تورینگ جهانی، RASP تعداد نامحدودی از "ثبات‌های" متمایز، شماره‌گذاری‌شده و اما بدون حد "ثبت" دارد — سلول‌های حافظه‌ای که می‌توانند هر عدد صحیحی را در خود نگهدارند (مراجعه کنید به Elgot و Robinson (1964)، Hartmanis (1971)، و به‌ویژه Cook-Rechow (1973); منابع در ماشین دسترسی تصادفی). ماشین حالت محدود RASP قابلیت آدرس‌دهی غیرمستقیم دارد (مثلاً محتویات یک ثبات می‌تواند به‌عنوان آدرس برای مشخص کردن یک ثبات دیگر استفاده شود)؛ بنابراین "برنامه" RASP می‌تواند به هر ثبات در دنباله ثبات‌ها دسترسی پیدا کند. نتیجه این تفاوت این است که بهینه‌سازی‌های محاسباتی‌ای وجود دارند که می‌توانند بر اساس شاخص‌های حافظه انجام شوند، که در ماشین تورینگ عمومی ممکن نیستند؛ بنابراین وقتی ماشین‌های تورینگ به‌عنوان مبنای تعیین محدودیت زمان اجرا استفاده می‌شوند، می‌توان یک "حد پایین کاذب" را برای زمان‌های اجرای الگوریتم‌های خاص ثابت کرد (به دلیل فرض ساده‌سازی غلط در مورد ماشین تورینگ). یکی از مثال‌های این موضوع جستجوی دودویی است، الگوریتمی که می‌تواند نشان داده شود که سریع‌تر اجرا می‌شود هنگامی که از مدل محاسباتی RASP استفاده می‌شود تا مدل ماشین تورینگ.

تعامل
در روزهای اولیه محاسبات، استفاده از کامپیوتر معمولاً به پردازش دسته‌ای محدود بود، یعنی کارهای غیرتعاملی که هر کدام داده‌های خروجی را از داده‌های ورودی معین تولید می‌کردند. نظریه محاسبات‌پذیری، که محاسبات‌پذیری توابع از ورودی‌ها به خروجی‌ها را مطالعه می‌کند و برای آن ماشین‌های تورینگ اختراع شدند، بازتابی از این عمل بود.

از دهه 1970، استفاده تعاملی از کامپیوترها به‌طور قابل توجهی رایج‌تر شد. به‌طور اصولی، این را می‌توان با داشتن یک عامل خارجی که به‌طور همزمان از نوار می‌خواند و به آن می‌نویسد، مدل‌سازی کرد، اما این معمولاً مطابق با نحوه تعامل واقعی نیست؛ بنابراین، هنگام توصیف تعامل، گزینه‌های دیگری مانند اتوماتای ورودی/خروجی معمولاً ترجیح داده می‌شوند.

 تاریخچه 
 زمینه تاریخی: ماشین‌های محاسباتی 
رابین گاندی (۱۹۱۹–۱۹۹۵)—دانشجوی آلن تورینگ (۱۹۱۲–۱۹۵۴) و دوست مادام‌العمر او—نسب مفهوم "ماشین محاسباتی" را به چارلز ببیج (حدود ۱۸۳۴) برمی‌گرداند و حتی "تز ببیج" را پیشنهاد می‌دهد:

تحلیل گاندی از ماشین تحلیلی ببیج پنج عملیات زیر را توصیف می‌کند (نگاه کنید به ص. ۵۲–۵۳):
 توابع حسابی +، −، ×، که در آن − نشان‌دهنده تفریق "صحیح" است:  اگر .
 هر دنباله‌ای از عملیات یک عملیات است.
 تکرار یک عملیات (n بار تکرار یک عملیات P).
 تکرار شرطی (n بار تکرار یک عملیات P مشروط به "موفقیت" آزمون T).
 انتقال شرطی (یعنی "goto" شرطی).

گاندی بیان می‌کند که "توابعی که می‌توانند توسط (۱)، (۲)، و (۴) محاسبه شوند دقیقاً آن‌هایی هستند که قابل محاسبه با تورینگ هستند." (ص. ۵۳). او به پیشنهادهای دیگر برای "ماشین‌های محاسباتی جهانی" از جمله پرسی لودگیت (۱۹۰۹)، لئوناردو تورس کوئودو (۱۹۱۴)،L. Torres Quevedo. Ensayos sobre Automática – Su definicion. Extension teórica de sus aplicaciones, Revista de la Academia de Ciencias Exacta, Revista 12, pp. 391–418, 1914.Torres Quevedo. L. (1915). "Essais sur l'Automatique - Sa définition. Etendue théorique de ses applications", Revue Génerale des Sciences Pures et Appliquées, vol. 2, pp. 601–611. موریس داکن (۱۹۲۲)، لویی کوفینیال (۱۹۳۳)، ونوار بوش (۱۹۳۶)، هوارد آیکن (۱۹۳۷) اشاره می‌کند. اما:

 مسئله تصمیم‌گیری: سؤال دهم هیلبرت در سال ۱۹۰۰ 
با توجه به مسائل هیلبرت که توسط ریاضیدان مشهور دیوید هیلبرت در سال ۱۹۰۰ مطرح شد، جنبه‌ای از مسئله شماره ۱۰ تقریباً ۳۰ سال شناور بود تا زمانی که به‌طور دقیق مطرح شد. بیان اصلی هیلبرت برای شماره ۱۰ به شرح زیر است:

تا سال ۱۹۲۲، این مفهوم "مسئله تصمیم‌گیری" کمی توسعه یافت، و هاینریش بهمان اظهار داشت که:

 پانویس 

 جستارهای وابسته 
 ماشین محاسبه تورینگ
 آلن تورینگ
 تز چرچ-تورینگ
 ماشین انیگما
 بنفش (ماشین سایفر)
 ماشین تورینگ جهانی
 ماشین تورینگ کوانتومی

 پیوند به بیرون 


 ماشین تورینگ در دانشنامۀ فلسفی استانفورد
 جزئیات اطلاعات فرضیۀ چارچ-تورینگ (دانشنامهٔ فلسفی استانفورد)
 Turing Machine-Like Models در مولکول‌های زیستی به‌منظور درک مکانیسمهای حیات با فرایندهای DNA.
 The Turing machine—Summary about the Turing machine, its functionality and historical facts
 The Wolfram 2,3 Turing Machine Research Prize—Stephen Wolfram's $25,000 prize for the proof or disproof of the universality of the potentially smallest universal Turing Machine. The contest has ended, with the proof affirming the machine's universality.
 "Turing Machine Causal Networks" by Enrique Zeleny, Wolfram Demonstrations Project.

 Purely mechanical Turing Machine
 How Alan Turing Cracked The Enigma Code Imperial War Museums

 منابع 

 مقدمه‌ای بر زبان‌ها و نظریهٔ محاسبات 

 Sudkamp, T. A. , An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed. , Pearson Education, Inc. , 2006. 
 Johnsonbaugh, R. , Discrete Mathematics, 4th ed. , Prentice Hall, 1993. 
 Jackson, Jr. , Philip C. , Introduction to Artificial Intelligence, 2nd enlarged and slightly corrected ed. , Dover Publications, Inc. , New York, 1985. 




رده:ماشین تورینگ
رده:آلن تورینگ
رده:اتوماتا (رایانش)
رده:اتوماتا (مکانیک)
رده:اختراع‌های انگلیسی
رده:روش‌های صوری
رده:زبان‌های صوری
رده:علوم رایانه در ۱۹۳۶ (میلادی)
رده:علوم رایانه در ۱۹۳۷ (میلادی)
رده:علوم نظری رایانه
رده:مدل‌های محاسباتی
رده:نظریه اتوماتا
رده:نظریه بازگشت