نمایش مبدأ برای ماشین تورینگ

[[File:Turing Machine Model Davey 2012.jpg|alt=یک مدل فیزیکی از ماشین تورینگ ساخته شده توسط مایک دیوی|thumb|یک مدل فیزیکی از ماشین تورینگ. یک ماشین تورینگ واقعی نوار نامحدودی در هر دو طرف دارد؛ با این حال، مدل‌های فیزیکی تنها مقدار محدودی نوار دارند.|300x300px]]
{{تورینگ}}

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

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

ماشین تورینگ در سال ۱۹۳۶ توسط [[آلن تورینگ]] اختراع شد،<ref name=Hodges-2012>{{cite book |first=اندرو | last=هاجز |author-link =اندرو هاجز |year = ۲۰۱۲ |title =آلن تورینگ: معما |url=https://archive.org/details/alanturingenigma0000hodg |publisher =[[انتشارات دانشگاه پرینستون]] |isbn=978-0-691-15564-7 |edition=نسخه صدساله }}</ref> که آن را "ماشین خودکار" (automatic machine) نامید.<ref>رجوع کنید به پاورقی در دیویس ۲۰۰۰:۱۵۱.</ref> این [[آلونزو چرچ]]، مشاور دکترای تورینگ بود که بعداً واژه "ماشین تورینگ" را در یک نقد ابداع کرد.<ref name="mitpress.mit.edu">رجوع کنید به یادداشت در پیشگفتار مجموعه آثار آلونزو چرچ ({{Cite book |url=https://mitpress.mit.edu/books/collected-works-alonzo-church |title=The Collected Works of Alonzo Church |date=2019-04-23 |publisher=MIT Press |isbn=978-0-262-02564-5 |editor-last=Burge |editor-first=Tyler |location=Cambridge, MA, US |language=en |editor-last2=Enderton |editor-first2=Herbert}})</ref> با این مدل، تورینگ توانست به دو پرسش پاسخ منفی دهد:
* آیا ماشینی وجود دارد که بتواند تعیین کند آیا یک ماشین دلخواه روی نوارش "مدور" است (مثلاً متوقف می‌شود یا ادامه کار محاسباتی خود را انجام نمی‌دهد)؟
* آیا ماشینی وجود دارد که بتواند تعیین کند آیا یک ماشین دلخواه روی نوارش یک نماد خاص را چاپ می‌کند یا خیر؟<ref name="The Undecidable' page 119">تورینگ ۱۹۳۶ در ''غیرقابل تصمیم‌گیری'' ۱۹۶۵:۱۳۲-۱۳۴؛ تعریف تورینگ از "مدور" در صفحه ۱۱۹ آمده است.</ref><ref name="Turing 1937 230–265">{{cite journal |first=آلن ماتیسون |last=تورینگ |title=درباره اعداد محاسبه‌پذیر، با کاربردی برای ''مسئله تصمیم‌گیری'' |journal=نشریه انجمن ریاضی لندن |series=سری ۲ |volume=42 |number=1 |pages=230–265 |year=1937 | doi=10.1112/plms/s2-42.1.230 |s2cid=73712 }}</ref>
بنابراین با ارائه توضیح ریاضی یک دستگاه بسیار ساده قادر به محاسبات دلخواه، او توانست ویژگی‌های محاسبات به‌طور کلی و به‌طور خاص [[محاسبه‌پذیری|غیرقابل محاسبه بودن]] مسئله تصمیم‌گیری ''[[Entscheidungsproblem]]'' را اثبات کند.<ref name="ReferenceA">تورینگ ۱۹۳۶ در ''غیرقابل تصمیم‌گیری'' ۱۹۶۵:۱۴۵</ref>

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

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

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

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

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

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

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

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

{{blockquote|... ظرفیتی نامحدود برای حافظه که به شکل یک نوار بی‌نهایت ارائه شده و به مربع‌هایی تقسیم شده‌است، که هر یک از آن‌ها می‌توانند یک نماد را چاپ کنند. در هر لحظه یک نماد در ماشین وجود دارد؛ این نماد به عنوان نماد اسکن شده شناخته می‌شود. ماشین می‌تواند نماد اسکن شده را تغییر دهد، و رفتار آن تا حدی توسط آن نماد تعیین می‌شود، اما نمادهای روی نوار در جاهای دیگر بر رفتار ماشین تأثیری ندارند. با این حال، نوار می‌تواند به جلو و عقب از طریق ماشین حرکت کند، که این یکی از عملیات ابتدایی ماشین است. بنابراین هر نماد روی نوار ممکن است در نهایت نقشی ایفا کند.<ref>به تعریف "[[ویکی‌واژه:innings|innings]]" در [[ویکی‌واژه]] مراجعه کنید</ref>|تورینگ ۱۹۴۸، صفحه ۳<ref>
{{cite report
| title=ماشین‌های هوشمند
| author=A.M. Turing
| date= جولای ۱۹۴۸
| url=http://www.alanturing.net/Turing_archive/archive/l/l32/L32-004.html
| institution=آزمایشگاه ملی فیزیک
}} اینجا: صفحه ۳-۴
</ref>}}

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

[[پرونده:Turing machine 2a.svg|thumb|right|300px|سر همیشه بر روی یک مربع خاص از نوار قرار دارد؛ تنها یک بخش محدود از مربع‌ها نشان داده شده است. وضعیت ماشین (q<sub>4</sub>) بر روی مربع پردازش شده نمایش داده شده است. (ترسیم پس از کلین (1952) صفحه 375.)]]

[[پرونده:Turing machine 2b.svg|thumb|right|300px|در اینجا وضعیت داخلی (q<sub>1</sub>) درون سر نمایش داده شده است، و تصویر نشان می‌دهد که نوار بی‌نهایت است و پیش‌فرض با "0" پر شده است، که نماد نمایانگر فضای خالی است. وضعیت کامل سیستم (یا "پیکربندی کامل" آن) شامل وضعیت داخلی، هر نماد غیر خالی روی نوار (در این تصویر "11B")، و موقعیت سر نسبت به آن نمادها از جمله فضای خالی‌ها، یعنی "011B". (ترسیم پس از مینسکی (1967) صفحه 121.)]]

بیشتر به طور صریح، یک ماشین تورینگ شامل موارد زیر است:
* یک ''نوار'' که به سلول‌هایی تقسیم شده است، که یکی پس از دیگری قرار دارند. هر سلول شامل نمادی از یک الفبای محدود است. الفبا شامل یک نماد ویژه فضای خالی (که در اینجا به صورت '0' نوشته شده است) و یک یا چند نماد دیگر است. فرض می‌شود که نوار به طور دلخواه به سمت چپ و راست قابل گسترش است، به طوری که ماشین تورینگ همیشه به اندازه کافی نوار برای محاسبات خود دارد. سلول‌هایی که قبلاً نوشته نشده‌اند، فرض می‌شود که با نماد فضای خالی پر شده‌اند. در برخی مدل‌ها، نوار یک انتهای چپ دارد که با یک نماد ویژه علامت‌گذاری شده است؛ نوار به سمت راست گسترش می‌یابد یا به طور نامحدود قابل گسترش است.
* یک ''سر'' که می‌تواند نمادها را روی نوار بخواند و بنویسد و نوار را یک سلول به چپ و راست (و فقط یک سلول) حرکت دهد. در برخی مدل‌ها، سر حرکت می‌کند و نوار ثابت است.
* یک ''ثبت وضعیت'' که وضعیت ماشین تورینگ را ذخیره می‌کند، که یکی از تعداد محدودی است. در بین این وضعیت‌ها، وضعیت ویژه ''وضعیت شروع'' است که با آن ثبت وضعیت مقداردهی اولیه می‌شود. این وضعیت‌ها، به گفته تورینگ، جایگزین "وضعیت ذهنی" هستند که یک فرد در حین انجام محاسبات معمولاً در آن قرار دارد.
* یک ''جدول محدود''<ref>گاهی اوقات به آن ''جدول عملیات'' یا ''[[سیستم انتقال|تابع انتقال]]'' گفته می‌شود.</ref> از دستورات<ref>معمولاً پنج‌تایی‌ها [5-تایی‌ها]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>، اما گاهی اوقات چهار‌تایی‌ها [4-تایی‌ها].</ref> که، با توجه به ''وضعیت''(q<sub>i</sub>) که ماشین در آن قرار دارد ''و'' نماد''(a<sub>j</sub>)'' که در حال خواندن از نوار است (نمادی که در حال حاضر زیر سر قرار دارد)، به ماشین می‌گوید که در ''ترتیب'' زیر عمل کند (برای مدل‌های 5-[[تایی]]):
# یا نمادی را پاک کند یا نمادی بنویسد (جایگزینی a<sub>j</sub> با a<sub>j1</sub>).
# سر را حرکت دهد (که توسط d<sub>k</sub> توصیف می‌شود و می‌تواند مقادیر 'L' برای یک گام به چپ ''یا'' 'R' برای یک گام به راست ''یا'' 'N' برای ایستادن در همان مکان داشته باشد).
# همان وضعیت یا یک ''وضعیت جدید'' که تجویز شده است را بپذیرد (به وضعیت q<sub>i1</sub> برود).
در مدل‌های 4-تایی، پاک کردن یا نوشتن یک نماد (a<sub>j1</sub>) و حرکت دادن سر به چپ یا راست (d<sub>k</sub>) به عنوان دستورات جداگانه مشخص شده‌اند. جدول به ماشین می‌گوید که (ia) یک نماد را پاک کند یا بنویسد ''یا'' (ib) سر را به چپ یا راست حرکت دهد، ''و سپس'' (ii) همان وضعیت یا وضعیت جدید تجویز شده را بپذیرد، اما نه هر دو عمل (ia) و (ib) را در یک دستور. در برخی مدل‌ها، اگر ورودی برای ترکیب فعلی نماد و وضعیت در جدول وجود نداشته باشد، آنگاه ماشین متوقف می‌شود؛ مدل‌های دیگر نیاز دارند که تمام ورودی‌ها پر شوند.

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

== تعریف منطقی (انتزاع ذهنی مفاهیم کلی) ==
ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت <math>M = (Q, \Sigma, \Gamma, \delta, q_0) \!</math>، که در اینجا:
* <math>M \!</math> برای نمایش مفهوم ماشین انتخاب شده‌است.
* <math>Q \!</math> [[مجموعه (ریاضی)|مجموعه‌ای]] است متناهی، از حالات داخلی.<ref>Internal States</ref>
* <math>\Gamma \!</math> مجموعه‌ای متناهی موسوم به الفبای نوار<ref>Tape alphabet</ref> و حاوی نمادی مخصوص <math>B \!</math> برای نمایش یک فاصلهٔ خالی روی نوار ماشین است.
* <math>\Sigma \!</math> [[زیرمجموعه]]‌ای است از <math> \Gamma - \{B\} \!</math> و موسوم به الفبای ورودی. یعنی الفبای ورودی زیر مجموعه‌ای از الفبای نوار است که شامل خالی نیست. نوارهای خالی نمی‌توانند به عنوان ورودی استفاده شوند.
* <math>\delta \!</math> عبارت است از یک تابع جزئی،<ref>Partial function</ref> موسوم به تابع انتقال<ref>Transition function</ref> از دامنهٔ <math> Q \times \Gamma \!</math> به برد <math>Q \times \Gamma \times \{L, R\} \!</math>.
* <math>q_0 \!</math> حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را در آن آغاز می‌کنیم.
به‌طور کلی <math>\delta \!</math> یک [[تابع جزئی]] روی <math>Q \! \times \Gamma \!</math> است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند.

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

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

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

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

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

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

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

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

==مقایسه با ماشین‌های واقعی==
[[File:Lego Turing Machine.jpg|thumb|مدل‌سازی ماشین تورینگ با استفاده از قطعات [[Lego]]]]
ماشین‌های تورینگ از برخی دیگر از انواع اتوماتا، مانند [[ماشین حالت محدود]] و [[اتوماتای پشته‌ای]]، قدرتمندتر هستند. بر اساس [[اصل کلی چرچ–تورینگ]]، ماشین‌های تورینگ به اندازه‌ی ماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی هستند که یک برنامه‌ی واقعی می‌تواند انجام دهد. نکته‌ای که در این بیان نادیده گرفته می‌شود این است که، چون یک ماشین واقعی تنها می‌تواند تعداد محدودی ''پیکربندی'' داشته باشد، در واقع چیزی جز یک ماشین حالت محدود نیست، در حالی که یک ماشین تورینگ فضای ذخیره‌سازی نامحدودی برای محاسبات خود دارد.

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

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

[[File:Turingmachine.jpg|thumb|مدل‌سازی دیگری از ماشین تورینگ]]

===محدودیت‌ها===

====نظریه پیچیدگی محاسباتی====
{{further|نظریه پیچیدگی محاسباتی}}

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

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

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

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

{{نقل قول|''اینکه تمام توسعه و عملیات تحلیل اکنون توسط ماشین‌آلات قابل اجرا است.''|''(ایتالیک‌ها در متن ببیج همانطور که توسط گاندی ذکر شده، صفحه ۵۴)''}}

تحلیل گاندی از [[ماشین تحلیلی]] ببیج پنج عملیات زیر را توصیف می‌کند (نگاه کنید به ص. ۵۲–۵۳):
# توابع حسابی +، −، ×، که در آن − نشان‌دهنده تفریق "صحیح" است: {{nowrap|''x'' − ''y'' {{=}} ۰}} اگر {{nowrap|''y'' ≥ ''x''}}.
# هر دنباله‌ای از عملیات یک عملیات است.
# تکرار یک عملیات (n بار تکرار یک عملیات P).
# تکرار شرطی (n بار تکرار یک عملیات P مشروط به "موفقیت" آزمون T).
# انتقال شرطی (یعنی "[[goto]]" شرطی).

گاندی بیان می‌کند که "توابعی که می‌توانند توسط (۱)، (۲)، و (۴) محاسبه شوند دقیقاً آن‌هایی هستند که [[قابلیت تورینگ|قابل محاسبه با تورینگ]] هستند." (ص. ۵۳). او به پیشنهادهای دیگر برای "ماشین‌های محاسباتی جهانی" از جمله [[پرسی لودگیت]] (۱۹۰۹)، [[لئوناردو تورس کوئودو]] (۱۹۱۴)،<ref name="LTQ1914es">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.</ref><ref name="LTQ1915fr">Torres Quevedo. L. (1915). [https://diccan.com/dicoport/Torres.htm "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.</ref> [[موریس داکن]] (۱۹۲۲)، [[لویی کوفینیال]] (۱۹۳۳)، [[ونوار بوش]] (۱۹۳۶)، [[هوارد آیکن]] (۱۹۳۷) اشاره می‌کند. اما:

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

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

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

مسئله تصمیم‌گیری [مسئله تصمیم‌گیری برای [[منطق مرتبه اول]]] زمانی حل می‌شود که روشی وجود داشته باشد که به ازای هر عبارت منطقی معین بتوان با تعداد محدودی عملیات اعتبار یا قابلیت ارضای آن را تعیین کرد ... مسئله تصمیم‌گیری باید به عنوان مسئله اصلی منطق ریاضی در نظر گرفته شود.|نقل شده، با این ترجمه و متن اصلی آلمانی، در Dershowitz و Gurevich, 2008}}

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

{{نقل قول|... رایج‌ترین شکل مسئله تصمیم‌گیری به شرح زیر است:
<blockquote>یک نسخه کاملاً مشخص و عمومی از قبل تعریف شده مورد نیاز است که به فرد اجازه دهد تا در تعداد محدودی از مراحل حقیقت یا نادرستی یک ادعای منطقی محض داده شده را تعیین کند...</blockquote>|گاندی ص. ۵۷، نقل قول از بهمان}}
{{نقل قول|بهامان اظهار داشت که... مسئله عمومی معادل مسئله تعیین این است که کدام گزاره‌های ریاضی درست هستند.|''همان''}}
{{نقل قول|اگر کسی قادر به حل مسئله تصمیم‌گیری بود، آنگاه روشی برای حل بسیاری (یا حتی همه) مسائل ریاضی خواهد داشت.|''همان''، ص. ۹۲}}

== پانویس ==
{{پانویس|چپ‌چین=بله}}

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

== پیوند به بیرون ==
{{ویکی‌انبار|Category:Turing machine}}
* {{springer|title=ماشین تورینگ|id=p/t094460}}
* [http://plato.stanford.edu/entries/turing-machine/ ماشین تورینگ در دانشنامۀ فلسفی استانفورد]
* [http://plato.stanford.edu/entries/church-turing/ جزئیات اطلاعات فرضیۀ چارچ-تورینگ] (دانشنامهٔ فلسفی استانفورد)
* [https://web.archive.org/web/20060622074841/http://www.weizmann.ac.il/mathusers/lbn/new_pages/Research_Turing.html/Research_Turing.html Turing Machine-Like Models] در مولکول‌های زیستی به‌منظور درک مکانیسمهای حیات با فرایندهای DNA.
* [https://web.archive.org/web/20190905085621/http://www.saschaseidel.de/html/programmierung/download_The_Turing_machine.php The Turing machine]—Summary about the Turing machine, its functionality and historical facts
* [http://www.wolframscience.com/prizes/tm23/ 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.
* "[http://demonstrations.wolfram.com/TuringMachineCausalNetworks/ Turing Machine Causal Networks]" by Enrique Zeleny, [[Wolfram Demonstrations Project]].
* {{dmoz|Computers/Computer_Science/Theoretical/Automata_Theory/Turing_Machines|Turing Machines}}
* [https://web.archive.org/web/20150905194426/http://www.turing2012.fr/?p=530&lang=en Purely mechanical Turing Machine]
* [http://www.iwm.org.uk/history/how-alan-turing-cracked-the-enigma-code How Alan Turing Cracked The Enigma Code] Imperial War Museums

== منابع ==
{{پانویس}}
* [http://www.amazon.com/gp/reader/0072322004/ref=sib_dp_pop_fc?ie=UTF8&p=S001#reader-link مقدمه‌ای بر زبان‌ها و نظریهٔ محاسبات] {{نشان زبان | en}}

{{چپ‌چین}}
* Sudkamp, T. A. , ''An Introduction to the Theory of Computer Science, Languages and Machines'', 3rd ed. , Pearson Education, Inc. , 2006. {{ISBN|0-321-32221-5|en}}
* Johnsonbaugh, R. , ''Discrete Mathematics'', 4th ed. , Prentice Hall, 1993. {{ISBN|0-13-518242-5|en}}
* Jackson, Jr. , Philip C. , ''Introduction to Artificial Intelligence'', 2nd enlarged and slightly corrected ed. , Dover Publications, Inc. , New York, 1985. {{ISBN|0-486-24864-X|en}}
{{پایان چپ‌چین}}
* {{یادکرد
|فصل= ماشین‌های تورینگ
|کتاب= نظریه زبانها و ماشینها
|نویسنده = محمد پارسا عفت روش
|ترجمه=
|ناشر =
|شهر=تهران
|کوشش=
|ویرایش= سوم
|صفحه=
|سال=۱۳۸۷
|شابک=964-6342-49-3
}}
* {{یادکرد-ویکی
|عنوان = ماشین تورینگ
|زبان = انگلیسی
}}

{{انبار-رده}}

{{زبان‌ها و دستور زبان‌های صوری}}
{{فناوری‌های واحد پردازش مرکزی}}
{{داده‌های کتابخانه‌ای}}


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