ماشین تورینگ

ماشین تورینگ(به انگلیسی: Turing machine) یک مدل ریاضی محاسبات است که یک ماشین انتزاعی^[۱] را توصیف می‌کند که نمادها را روی یک نوار طبق جدول قوانین دستکاری می‌کند.^[۲] با وجود سادگی مدل، قادر به اجرای هر الگوریتم کامپیوتری است.^[۳]

این ماشین روی یک نوار حافظه بی‌نهایت^[۴] که به سلول‌های گسسته^[۵] تقسیم شده است، کار می‌کند. هر سلول می‌تواند یک نماد از یک مجموعه متناهی از نمادها که الفبای رسمی ماشین نامیده می‌شود را نگه دارد. این ماشین دارای "سر"ی است که در هر لحظه از عملکرد ماشین روی یکی از این سلول‌ها قرار دارد و دارای "حالتی" است که از مجموعه‌ای متناهی از حالت‌ها انتخاب می‌شود. در هر گام از عملکرد، سر نماد موجود در سلول را می‌خواند. سپس، بر اساس نماد و حالت کنونی ماشین، نمادی در همان سلول می‌نویسد، سر را یک گام به چپ یا راست حرکت می‌دهد،^[۶] یا محاسبه را متوقف می‌کند. انتخاب نماد جایگزینی که باید نوشته شود، جهت حرکت سر و توقف یا عدم توقف، بر اساس یک جدول متناهی است که مشخص می‌کند برای هر ترکیب از حالت کنونی و نماد خوانده‌شده چه کاری باید انجام شود. مانند یک برنامه کامپیوتری واقعی، ممکن است ماشین تورینگ وارد یک حلقه بی‌نهایت شود که هرگز متوقف نمی‌شود.

ماشین تورینگ در سال ۱۹۳۶ توسط آلن تورینگ اختراع شد،^[۷] که آن را "ماشین خودکار" (automatic machine) نامید.^[۸] این آلونزو چرچ، مشاور دکترای تورینگ بود که بعداً واژه "ماشین تورینگ" را در یک نقد ابداع کرد.^[۹] با این مدل، تورینگ توانست به دو پرسش پاسخ منفی دهد:

• آیا ماشینی وجود دارد که بتواند تعیین کند آیا یک ماشین دلخواه روی نوارش "مدور" است (مثلاً متوقف می‌شود یا ادامه کار محاسباتی خود را انجام نمی‌دهد)؟
• آیا ماشینی وجود دارد که بتواند تعیین کند آیا یک ماشین دلخواه روی نوارش یک نماد خاص را چاپ می‌کند یا خیر؟^[۱۰][۱۱]

بنابراین با ارائه توضیح ریاضی یک دستگاه بسیار ساده قادر به محاسبات دلخواه، او توانست ویژگی‌های محاسبات به‌طور کلی و به‌طور خاص غیرقابل محاسبه بودن مسئله تصمیم‌گیری Entscheidungsproblem را اثبات کند.^[۱۲]

ماشین‌های تورینگ وجود محدودیت‌های اساسی در قدرت محاسبات مکانیکی را اثبات کردند.^[۱۳] در حالی که آن‌ها می‌توانند محاسبات دلخواه را بیان کنند، طراحی مینیمالیستی آن‌ها باعث می‌شود که برای محاسبات در عمل بسیار کند باشند: کامپیوترهای واقعی بر اساس طراحی‌های متفاوتی ساخته می‌شوند که برخلاف ماشین‌های تورینگ، از حافظه با دسترسی تصادفی استفاده می‌کنند.

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

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

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

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

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

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

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

... ظرفیتی نامحدود برای حافظه که به شکل یک نوار بی‌نهایت ارائه شده و به مربع‌هایی تقسیم شده‌است، که هر یک از آن‌ها می‌توانند یک نماد را چاپ کنند. در هر لحظه یک نماد در ماشین وجود دارد؛ این نماد به عنوان نماد اسکن شده شناخته می‌شود. ماشین می‌تواند نماد اسکن شده را تغییر دهد، و رفتار آن تا حدی توسط آن نماد تعیین می‌شود، اما نمادهای روی نوار در جاهای دیگر بر رفتار ماشین تأثیری ندارند. با این حال، نوار می‌تواند به جلو و عقب از طریق ماشین حرکت کند، که این یکی از عملیات ابتدایی ماشین است. بنابراین هر نماد روی نوار ممکن است در نهایت نقشی ایفا کند.^[۱۴]

— تورینگ ۱۹۴۸، صفحه ۳^[۱۵]

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

بیشتر به طور صریح، یک ماشین تورینگ شامل موارد زیر است:

• یک نوار که به سلول‌هایی تقسیم شده است، که یکی پس از دیگری قرار دارند. هر سلول شامل نمادی از یک الفبای محدود است. الفبا شامل یک نماد ویژه فضای خالی (که در اینجا به صورت '0' نوشته شده است) و یک یا چند نماد دیگر است. فرض می‌شود که نوار به طور دلخواه به سمت چپ و راست قابل گسترش است، به طوری که ماشین تورینگ همیشه به اندازه کافی نوار برای محاسبات خود دارد. سلول‌هایی که قبلاً نوشته نشده‌اند، فرض می‌شود که با نماد فضای خالی پر شده‌اند. در برخی مدل‌ها، نوار یک انتهای چپ دارد که با یک نماد ویژه علامت‌گذاری شده است؛ نوار به سمت راست گسترش می‌یابد یا به طور نامحدود قابل گسترش است.
• یک سر که می‌تواند نمادها را روی نوار بخواند و بنویسد و نوار را یک سلول به چپ و راست (و فقط یک سلول) حرکت دهد. در برخی مدل‌ها، سر حرکت می‌کند و نوار ثابت است.
• یک ثبت وضعیت که وضعیت ماشین تورینگ را ذخیره می‌کند، که یکی از تعداد محدودی است. در بین این وضعیت‌ها، وضعیت ویژه وضعیت شروع است که با آن ثبت وضعیت مقداردهی اولیه می‌شود. این وضعیت‌ها، به گفته تورینگ، جایگزین "وضعیت ذهنی" هستند که یک فرد در حین انجام محاسبات معمولاً در آن قرار دارد.
• یک جدول محدود^[۱۶] از دستورات^[۱۷] که، با توجه به وضعیت(q_i) که ماشین در آن قرار دارد و نماد(a_j) که در حال خواندن از نوار است (نمادی که در حال حاضر زیر سر قرار دارد)، به ماشین می‌گوید که در ترتیب زیر عمل کند (برای مدل‌های 5-تایی):

1. یا نمادی را پاک کند یا نمادی بنویسد (جایگزینی a_j با a_j1).
2. سر را حرکت دهد (که توسط d_k توصیف می‌شود و می‌تواند مقادیر 'L' برای یک گام به چپ یا 'R' برای یک گام به راست یا 'N' برای ایستادن در همان مکان داشته باشد).
3. همان وضعیت یا یک وضعیت جدید که تجویز شده است را بپذیرد (به وضعیت q_i1 برود).

در مدل‌های 4-تایی، پاک کردن یا نوشتن یک نماد (a_j1) و حرکت دادن سر به چپ یا راست (d_k) به عنوان دستورات جداگانه مشخص شده‌اند. جدول به ماشین می‌گوید که (ia) یک نماد را پاک کند یا بنویسد یا (ib) سر را به چپ یا راست حرکت دهد، و سپس (ii) همان وضعیت یا وضعیت جدید تجویز شده را بپذیرد، اما نه هر دو عمل (ia) و (ib) را در یک دستور. در برخی مدل‌ها، اگر ورودی برای ترکیب فعلی نماد و وضعیت در جدول وجود نداشته باشد، آنگاه ماشین متوقف می‌شود؛ مدل‌های دیگر نیاز دارند که تمام ورودی‌ها پر شوند.

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

ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت ${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0})\!}$، که در اینجا:

• ${\displaystyle M\!}$ برای نمایش مفهوم ماشین انتخاب شده‌است.
• ${\displaystyle Q\!}$ مجموعه‌ای است متناهی، از حالات داخلی.^[۱۸]
• ${\displaystyle \Gamma \!}$ مجموعه‌ای متناهی موسوم به الفبای نوار^[۱۹] و حاوی نمادی مخصوص ${\displaystyle B\!}$ برای نمایش یک فاصلهٔ خالی روی نوار ماشین است.
• ${\displaystyle \Sigma \!}$ زیرمجموعه‌ای است از ${\displaystyle \Gamma -\{B\}\!}$ و موسوم به الفبای ورودی. یعنی الفبای ورودی زیر مجموعه‌ای از الفبای نوار است که شامل خالی نیست. نوارهای خالی نمی‌توانند به عنوان ورودی استفاده شوند.
• ${\displaystyle \delta \!}$ عبارت است از یک تابع جزئی،^[۲۰] موسوم به تابع انتقال^[۲۱] از دامنهٔ ${\displaystyle Q\times \Gamma \!}$ به برد ${\displaystyle Q\times \Gamma \times \{L,R\}\!}$.
• ${\displaystyle q_{0}\!}$ حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را در آن آغاز می‌کنیم.

به‌طور کلی ${\displaystyle \delta \!}$ یک تابع جزئی روی ${\displaystyle Q\!\times \Gamma \!}$ است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

اینکه تمام توسعه و عملیات تحلیل اکنون توسط ماشین‌آلات قابل اجرا است.

— (ایتالیک‌ها در متن ببیج همانطور که توسط گاندی ذکر شده، صفحه ۵۴)

تحلیل گاندی از ماشین تحلیلی ببیج پنج عملیات زیر را توصیف می‌کند (نگاه کنید به ص. ۵۲–۵۳):

1. توابع حسابی +، −، ×، که در آن − نشان‌دهنده تفریق "صحیح" است: x − y = ۰ اگر y ≥ x.
2. هر دنباله‌ای از عملیات یک عملیات است.
3. تکرار یک عملیات (n بار تکرار یک عملیات P).
4. تکرار شرطی (n بار تکرار یک عملیات P مشروط به "موفقیت" آزمون T).
5. انتقال شرطی (یعنی "goto" شرطی).

گاندی بیان می‌کند که "توابعی که می‌توانند توسط (۱)، (۲)، و (۴) محاسبه شوند دقیقاً آن‌هایی هستند که قابل محاسبه با تورینگ هستند." (ص. ۵۳). او به پیشنهادهای دیگر برای "ماشین‌های محاسباتی جهانی" از جمله پرسی لودگیت (۱۹۰۹)، لئوناردو تورس کوئودو (۱۹۱۴)،^[۲۲][۲۳] موریس داکن (۱۹۲۲)، لویی کوفینیال (۱۹۳۳)، ونوار بوش (۱۹۳۶)، هوارد آیکن (۱۹۳۷) اشاره می‌کند. اما:

… تأکید بر برنامه‌ریزی یک دنباله تکراری ثابت از عملیات حسابی است. اهمیت اساسی تکرار شرطی و انتقال شرطی برای یک نظریه عمومی از ماشین‌های محاسباتی شناخته نشده‌است…

— گاندی ص. ۵۵

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

۱۰. تعیین قابلیت حل یک معادله دیوفانتین. با توجه به یک معادله دیوفانتین با هر تعداد متغیر ناشناخته و ضرایب صحیح گویا: فرآیندی طراحی شود که از طریق آن بتوان در تعداد محدودی از عملیات تعیین کرد که آیا معادله در اعداد صحیح گویا قابل حل است یا خیر. مسئله تصمیم‌گیری [مسئله تصمیم‌گیری برای منطق مرتبه اول] زمانی حل می‌شود که روشی وجود داشته باشد که به ازای هر عبارت منطقی معین بتوان با تعداد محدودی عملیات اعتبار یا قابلیت ارضای آن را تعیین کرد ... مسئله تصمیم‌گیری باید به عنوان مسئله اصلی منطق ریاضی در نظر گرفته شود.

— نقل شده، با این ترجمه و متن اصلی آلمانی، در Dershowitz و Gurevich, 2008

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

... رایج‌ترین شکل مسئله تصمیم‌گیری به شرح زیر است:

یک نسخه کاملاً مشخص و عمومی از قبل تعریف شده مورد نیاز است که به فرد اجازه دهد تا در تعداد محدودی از مراحل حقیقت یا نادرستی یک ادعای منطقی محض داده شده را تعیین کند...

— گاندی ص. ۵۷، نقل قول از بهمان

بهامان اظهار داشت که... مسئله عمومی معادل مسئله تعیین این است که کدام گزاره‌های ریاضی درست هستند.

— همان

اگر کسی قادر به حل مسئله تصمیم‌گیری بود، آنگاه روشی برای حل بسیاری (یا حتی همه) مسائل ریاضی خواهد داشت.

— همان، ص. ۹۲

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

در ویکی‌انبار پرونده‌هایی دربارهٔ ماشین تورینگ موجود است.

• "ماشین تورینگ", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• ماشین تورینگ در دانشنامۀ فلسفی استانفورد
• جزئیات اطلاعات فرضیۀ چارچ-تورینگ (دانشنامهٔ فلسفی استانفورد)
• 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.
• Turing Machines در کرلی
• Purely mechanical Turing Machine
• How Alan Turing Cracked The Enigma Code Imperial War Museums

• مقدمه‌ای بر زبان‌ها و نظریهٔ محاسبات (انگلیسی)

• محمد پارسا عفت روش (۱۳۸۷)، «ماشین‌های تورینگ»، نظریه زبانها و ماشینها (ویراست سوم)، تهران، شابک ۹۶۴-۶۳۴۲-۴۹-۳
• مشارکت‌کنندگان ویکی‌پدیا، «ماشین تورینگ». در دانشنامهٔ ویکی‌پدیای انگلیسی.

در ویکی‌انبار پرونده‌هایی دربارهٔ ماشین تورینگ موجود است.