موضوع مقاله: ماشین تورینگ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماشین تورینگ | مقدمه: یک ماشین تورینگ واقعی نوار نامحدودی در هر دو طرف دارد؛ با این حال، مدل‌های فیزیکی تنها مقدار محدودی نوار دارند.|300x300px ماشین تورینگ(به انگلیسی: Turing machine) یک مدل ریاضی محاسبات است که یک ماشین انتزاعیمینسکی ۱۹۶۷:۱۰۷ "در مقاله ۱۹۳۶، آ. | ## بخش 1: ماشین تورینگ | ماشین تورینگ یک ماشین حالت محدود است که با نوع خاصی از محیط - نوار آن - همراه است که می‌تواند در آن توالی نمادها را ذخیره و بعداً بازیابی کند." همچنین استون ۱۹۷۲:۸ که واژه "ماشین" را در گیومه می‌آورد. را توصیف می‌کند که نمادها را روی یک نوار طبق جدول قوانین دستکاری می‌کند.استون ۱۹۷۲:۸ بیان می‌کند که "این 'ماشین' یک مدل ریاضی انتزاعی است"، همچنین رجوع کنید به سیپسر ۲۰۰۶:۱۳۷ به بعد که "مدل ماشین تورینگ" را توصیف می‌کند. راجرز ۱۹۸۷ (۱۹۶۷):۱۳ به "توصیف تورینگ" اشاره می‌کند، بولوس، برگس و جفری ۲۰۰۲:۲۵ به "یک نوع خاص از ماشین ایده‌آل" اشاره می‌کنند. با وجود سادگی مدل، قادر به اجرای هر الگوریتم کامپیوتری است.سیپسر ۲۰۰۶:۱۳۷ "یک ماشین تورینگ می‌تواند هر کاری که یک کامپیوتر واقعی می‌تواند انجام دهد را انجام دهد." این ماشین روی یک نوار حافظه بی‌نهایترجوع کنید به سیپسر ۲۰۰۲:۱۳۷. همچنین، راجرز ۱۹۸۷ (۱۹۶۷):۱۳ یک "نوار کاغذی با طول بی‌نهایت در هر دو جهت" را توصیف می‌کند. مینسکی ۱۹۶۷:۱۱۸ بیان می‌کند "این نوار به عنوان بی‌نهایت در هر دو جهت در نظر گرفته می‌شود." بولوس، برگس و جفری ۲۰۰۲:۲۵ امکان "وجود کسی که در هر انتها مستقر است تا مربع‌های خالی اضافی را در صورت نیاز اضافه کند" را شامل می‌شود. نویسندگان دیگر از واژه "مربع" استفاده می‌کنند، مثلاً بولوس، برگس، جفری ۲۰۰۲:۳۵، مینسکی ۱۹۶۷:۱۱۷، پنروز ۱۹۸۹:۳۷. هر نماد از یک مجموعه متناهی از نمادهای که الفبای رسمی ماشین نامیده می‌شود، می‌تواند انتخاب شود. این ماشین دارای یک "اشاره‌گر" است که در هر عملیات ماشین می‌تواند به یک سلول‌ اشاره کند؛ نماد موجود در سلول را بخواند و بر اساس حالت کنونی ماشین، نمادی در همان سلول بنویسد. ماشین در مرحله بعد تصمیم ‌می‌گیرد اشاره‌گر را یک گام به چپ یا راست حرکت دهد،بولوس، برگس، جفری ۲۰۰۲:۲۵ ماشین را به عنوان یک شیء متحرک روی نوار نشان می‌دهند. پنروز ۱۹۸۹:۳۶-۳۷ خود را با نوار بی‌نهایت "ناراحت" می‌بیند و بیان می‌کند که "ممکن است سخت باشد که آن را جابجا کنیم!" او ترجیح می‌دهد نوار را به عنوان محیطی خارجی در نظر بگیرد که دستگاه محدود ما می‌تواند در آن حرکت کند. برخی از انواع مدل ماشین تورینگ نیز اجازه می‌دهند که اشاره‌گر در همان موقعیت باقی بماند یا متوقف شود. انتخاب نماد جایگزینی که باید نوشته شود، جهت حرکت اشاره‌گر و توقف یا عدم توقف، بر اساس یک جدول متناهی است که مشخص می‌کند برای هر ترکیب از حالت کنونی و نماد خوانده‌شده چه کاری باید انجام شود. این جدول متناهی مانند یک برنامه کامپیوتری واقعی، ممکن است ماشین تورینگ را وارد یک حلقه بی‌نهایت کند که هرگز متوقف نمی‌شود. این آلونزو چرچ، مشاور دکترای تورینگ بود که بعداً واژه "ماشین تورینگ" را در یک نقد ابداع کرد.رجوع کنید به یادداشت در پیشگفتار مجموعه آثار آلونزو چرچ با این مدل، تورینگ توانست به دو پرسش پاسخ منفی دهد: آیا ماشینی وجود دارد که بتواند تعیین کند آیا یک ماشین دلخواه روی نوارش "مدور" است (مثلاً متوقف می‌شود یا ادامه کار محاسباتی خود را انجام نمی‌دهد)؟ آیا ماشینی وجود دارد که بتواند تعیین کند آیا یک ماشین دلخواه روی نوارش یک نماد خاص را چاپ می‌کند یا خیر؟تورینگ ۱۹۳۶ در غیرقابل تصمیم‌گیری ۱۹۶۵:۱۳۲-۱۳۴؛ تعریف تورینگ از "مدور" در صفحه ۱۱۹ آمده است. بنابراین با ارائه توضیح ریاضی یک دستگاه بسیار ساده قادر به محاسبات دلخواه، او توانست ویژگی‌های محاسبات به‌طور کلی و به‌طور خاص غیرقابل محاسبه بودن مسئله تصمیم‌گیری Entscheidungsproblem را اثبات کند.تورینگ ۱۹۳۶ در غیرقابل تصمیم‌گیری ۱۹۶۵:۱۴۵ ماشین‌های تورینگ وجود محدودیت‌های اساسی در قدرت محاسبات مکانیکی را اثبات کردند.سیپسر ۲۰۰۶:۱۳۷ مشاهده می‌کند که "یک ماشین تورینگ می‌تواند هر کاری که یک کامپیوتر واقعی می‌تواند انجام دهد، انجام دهد. به معنای واقعی کلمه، این مسائل فراتر از محدودیت‌های نظری محاسبات هستند." در حالی که آن‌ها می‌توانند محاسبات دلخواه را بیان کنند، طراحی مینیمالیستی آن‌ها باعث می‌شود که برای محاسبات در عمل بسیار کند باشند: کامپیوترهای واقعی بر اساس طراحی‌های متفاوتی ساخته می‌شوند که برخلاف ماشین‌های تورینگ، از حافظه با دسترسی تصادفی استفاده می‌کنند. کامل بودن تورینگ توانایی یک مدل محاسباتی یا یک سیستم دستورها برای شبیه‌سازی یک ماشین تورینگ است. یک زبان برنامه‌نویسی که کامل تورینگ باشد، از نظر تئوری قادر به بیان تمامی وظایفی است که توسط کامپیوترها قابل انجام است؛ تقریباً همه زبان‌های برنامه‌نویسی کامل تورینگ هستند اگر محدودیت‌های حافظه متناهی نادیده گرفته شوند. نمای کلی ماشین تورینگ یک مدل ایدئال از یک واحد پردازش مرکزی (CPU) است که تمام دستکاری داده‌های انجام شده توسط کامپیوتر را کنترل می‌کند. معمولاً این حافظه ترتیبی به صورت نواری با طول بی‌نهایت نمایش داده می‌شود که ماشین می‌تواند بر روی آن عملیات خواندن و نوشتن انجام دهد. در زمینه نظریه زبان‌های صوری، ماشین تورینگ (ماشین متناهی) قادر است برخی زیرمجموعه‌های دلخواه از رشته‌های معتبر یک الفبا را شمارش کند. مجموعه‌ای از رشته‌ها که می‌توانند به این روش شمارش شوند، زبان بازگشتی شمارا نامیده می‌شوند. ماشین تورینگ می‌تواند معادل به عنوان مدلی تعریف شود که رشته‌های ورودی معتبر را تشخیص می‌دهد، به جای اینکه رشته‌های خروجی را شمارش کند. با در نظر گرفتن یک ماشین تورینگ M و یک رشته دلخواه s، معمولاً نمی‌توان تصمیم گرفت که آیا M در نهایت s را تولید می‌کند یا خیر. این موضوع به دلیل غیرقابل حل بودن مسئله توقف است، که تأثیرات عمده‌ای بر محدودیت‌های نظری محاسبات دارد. ماشین تورینگ قادر به پردازش یک دستور زبان بدون محدودیت است، که به نوبه خود نشان می‌دهد که می‌تواند منطق مرتبه اول را به صورت قوی و به روش‌های بی‌نهایت ارزیابی کند. یک ماشین تورینگ که قادر به شبیه‌سازی هر ماشین تورینگ دیگری است، ماشین تورینگ جهانی (UTM، یا به سادگی ماشین جهانی) نامیده می‌شود. فرم رسمی ریاضی دیگر، حساب لامبدا، با ماهیت "جهانی" مشابه توسط آلونزو چرچ معرفی شد. این تز بیان می‌کند که ماشین‌های تورینگ، حساب لامبدا، و دیگر فرم‌های مشابه محاسبه واقعاً مفهوم غیررسمی روش مؤثر در منطق و ریاضیات را در بر می‌گیرند و بنابراین مدلی ارائه می‌دهند که از طریق آن می‌توان درباره یک الگوریتم یا "روش مکانیکی" به صورت ریاضی دقیق و بدون وابستگی به هر فرم خاص استدلال کرد. | ## بخش 2: ماشین تورینگ | مطالعه ویژگی‌های انتزاعی ماشین‌های تورینگ بسیاری از بینش‌ها را در علوم کامپیوتر، نظریه محاسبات و نظریه پیچیدگی محاسباتی به ارمغان آورده است. توصیف فیزیکی در مقاله سال ۱۹۴۸ خود، "ماشین‌های هوشمند"، تورینگ نوشت که ماشین او شامل موارد زیر است: توصیف ماشین تورینگ به طور ریاضی یک ماشینی را مدل‌سازی می‌کند که به طور مکانیکی روی یک نوار عمل می‌کند. بر روی این نوار نمادهایی وجود دارد که ماشین می‌تواند آنها را خوانده و یکی یکی بنویسد، با استفاده از یک اشاره‌گر نوار. عملیات به طور کامل توسط یک مجموعه محدود از دستورات ابتدایی تعیین می‌شود، مانند "در حالت 42، اگر نمادی که دیده می‌شود 0 است، 1 بنویس؛ اگر نمادی که دیده می‌شود 1 است، به حالت 17 تغییر کن؛ در حالت 17، اگر نمادی که دیده می‌شود 0 است، 1 بنویس و به حالت 6 تغییر کن؛" و غیره. در مقاله اصلی ("در مورد اعداد قابل محاسبه، با کاربردی در مسئله تصمیم‌گیری"، همچنین به ارجاعات زیر مراجعه کنید)، تورینگ نه یک مکانیزم، بلکه شخصی به نام "کامپیوتر" را تصور می‌کند که این قوانین مکانیکی قطعی را به طور غلامانه اجرا می‌کند (یا به گفته تورینگ، "به شکلی بی‌هدف"). وضعیت کامل سیستم (یا "پیکربندی کامل" آن) شامل وضعیت داخلی، هر نماد غیر خالی روی نوار (در این تصویر "11B")، و موقعیت اشاره‌گر نسبت به آن نمادها از جمله فضای خالی‌ها، یعنی "011B". (ترسیم پس از مینسکی (1967) صفحه 121.) بیشتر به طور صریح، یک ماشین تورینگ شامل موارد زیر است: یک نوار که به سلول‌هایی تقسیم شده است، که یکی پس از دیگری قرار دارند. الفبا شامل یک نماد ویژه فضای خالی (که در اینجا به صورت '0' نوشته شده است) و یک یا چند نماد دیگر است. فرض می‌شود که نوار به طور دلخواه به سمت چپ و راست قابل گسترش است، به طوری که ماشین تورینگ همیشه به اندازه کافی نوار برای محاسبات خود دارد. در برخی مدل‌ها، نوار یک انتهای چپ دارد که با یک نماد ویژه علامت‌گذاری شده است؛ نوار به سمت راست گسترش می‌یابد یا به طور نامحدود قابل گسترش است. یک اشاره‌گر که می‌تواند نمادها را روی نوار بخواند و بنویسد و نوار را یک سلول به چپ و راست (و فقط یک سلول) حرکت دهد. در بین این وضعیت‌ها، وضعیت ویژه وضعیت شروع است که با آن ثبت وضعیت مقداردهی اولیه می‌شود. این وضعیت‌ها، به گفته تورینگ، جایگزین "وضعیت ذهنی" هستند که یک فرد در حین انجام محاسبات معمولاً در آن قرار دارد. که، با توجه به وضعیت(qi) که ماشین در آن قرار دارد و نماد(aj) که در حال خواندن از نوار است (نمادی که در حال حاضر زیر اشاره‌گر قرار دارد)، به ماشین می‌گوید که در ترتیب زیر عمل کند (برای مدل‌های 5-تایی): یا نمادی را پاک کند یا نمادی بنویسد (جایگزینی aj با aj1). اشاره‌گر را حرکت دهد (که توسط dk توصیف می‌شود و می‌تواند مقادیر 'L' برای یک گام به چپ یا 'R' برای یک گام به راست یا 'N' برای ایستادن در همان مکان داشته باشد). در مدل‌های 4-تایی، پاک کردن یا نوشتن یک نماد (aj1) و حرکت دادن اشاره‌گر به چپ یا راست (dk) به عنوان دستورات جداگانه مشخص شده‌اند. جدول به ماشین می‌گوید که (ia) یک نماد را پاک کند یا بنویسد یا (ib) اشاره‌گر را به چپ یا راست حرکت دهد، و سپس (ii) همان وضعیت یا وضعیت جدید تجویز شده را بپذیرد، اما نه هر دو عمل (ia) و (ib) را در یک دستور. در برخی مدل‌ها، اگر ورودی برای ترکیب فعلی نماد و وضعیت در جدول وجود نداشته باشد، آنگاه ماشین متوقف می‌شود؛ مدل‌های دیگر نیاز دارند که تمام ورودی‌ها پر شوند. هر بخش از ماشین (یعنی وضعیت آن، مجموعه نمادها و نوار استفاده‌شده در هر لحظه) و اعمال آن (مانند چاپ، پاک‌کردن و حرکت نوار) محدود، گسسته و قابل تمایز است؛ این نوار نامحدود و زمان اجرا است که به آن فضای ذخیره‌سازی نامحدود می‌دهد. تعریف منطقی (انتزاع ذهنی مفاهیم کلی) ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت ، که در اینجا: برای نمایش مفهوم ماشین انتخاب شده‌است. مقایسه با ماشین‌های واقعی اغلب گفته می‌شود که ماشین تورینگ، برخلاف ماشین‌های اتومات، به اندازه ماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی که ماشین واقعی می‌تواند بکند هستند. چیزی که در این مطلب جا ماند این است که یک ماشین واقعی تنها می‌تواند در بسیاری از تنظیمات متناهی باشد؛ در واقع ماشین واقعی چیزی نیست جز یک ماشین اتوماتیک محدود خطی. از طرف دیگر ماشین تورینگ با ماشین‌هایی که دارای ظرفیت حافظه‌های نامحدود محاسباتی هستند، معادل است. از نظر تاریخی رایانه‌هایی که محاسبات را در حافظه داخلی شان انجام می‌دادند، بعدها توسعه داده شده‌اند. برای مثال ماشین تورینگ، می‌تواند هرچیز طبق روالی که در زبان‌های برنامه‌نویسی پیدا می‌شود شبیه‌سازی کند. همچنین می‌تواند فرایندهای بازگشتی و هریک از پارامترهای مکانیسم شناخته شده را شبیه‌سازی کند. تفاوت، تنها در قابلیت ماشین تورینگ برای دخالت در مقدار محدودی اطلاعات نهفته است؛ بنابراین، ماشین تورینگ می‌تواند در مدت زمان محدودی، در اطلاعات دخالت داشته باشد هر چند که ماشین تورینگ فاقد حافظه به عنوان انچه امروز شناخته می شود بود. ماشین واقعی همانند ماشین‌های تورینگ می‌توانند حافظه مورد نیازش را به کمک دیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در حافظه‌شان ندارند. شرح برنامه‌های ماشین واقعی که از مدل ساده‌تر انتزاعی استفاده می‌کنند، پیچیده‌تر از شرح برنامه‌های ماشین تورینگ است. ماشین تورینگ الگوریتم‌های مستقل را که چقدر از حافظه استفاده می‌کنند، توصیف می‌کند. | ## بخش 3: ماشین تورینگ | در دارایی حافظه همهٔ ماشین‌ها، محدودیتی وجود دارد؛ ولی این محدودیت می‌تواند خود سرانه در طول زمان افزایش یابد. ماشین تورینگ به ما اجازه می‌دهد دربارهٔ الگوریتم‌هایی که برای همیشه نگه داشته می‌شوند، توصیفاتی ارائه دهیم؛ بدون در نظر گرفتن پیش رفت در معماری محاسبات با ماشین معمولی. الگوریتم‌های در حال اجرا در ماشین آلات انتزاعی معادل تورینگ، معمولاً نسبت به همتایان خود که در ماشین‌های واقعی در حال اجرا هستند عمومی ترند. زیرا آن‌ها دارای دقت دلخواه در انواع اطلاعات قابل دسترس هستند و هیچ‌وقت با شرایط غیرمنتظره روبرو نمی‌شوند. یکی از نقطه ضعف‌های ماشین تورینگ این است که برنامه‌های واقعی که نوشته می‌شوند ورودی‌های نامحدودی را در طول زمان دریافت می‌کنند؛ در نتیجه هرگز متوقف نمی‌شوند. بر اساس اصل کلی چرچ–تورینگ، ماشین‌های تورینگ به اندازه‌ی ماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی هستند که یک برنامه‌ی واقعی می‌تواند انجام دهد. نکته‌ای که در این بیان نادیده گرفته می‌شود این است که، چون یک ماشین واقعی تنها می‌تواند تعداد محدودی پیکربندی داشته باشد، در واقع چیزی جز یک ماشین حالت محدود نیست، در حالی که یک ماشین تورینگ فضای ذخیره‌سازی نامحدودی برای محاسبات خود دارد. روش‌های مختلفی برای توضیح اینکه چرا ماشین‌های تورینگ مدل‌های مفیدی از کامپیوترهای واقعی هستند وجود دارد: هر چیزی که یک کامپیوتر واقعی می‌تواند محاسبه کند، یک ماشین تورینگ نیز می‌تواند محاسبه کند. به عنوان مثال: "یک ماشین تورینگ می‌تواند هر نوع زیرروال موجود در زبان‌های برنامه‌نویسی را شبیه‌سازی کند، از جمله روش‌های بازگشتی و هر یک از مکانیزم‌های شناخته‌شده انتقال پارامتر" (هوپکروفت و اولمن صفحه 157). یک ماشین حالت محدود بزرگ نیز می‌تواند هر کامپیوتر واقعی را مدل‌سازی کند، بدون در نظر گرفتن ورودی/خروجی. بنابراین، یک بیانیه درباره‌ی محدودیت‌های ماشین‌های تورینگ، برای کامپیوترهای واقعی نیز صادق است. با این حال، با توجه به زمان محدود، یک ماشین تورینگ (مانند یک ماشین واقعی) تنها می‌تواند مقدار محدودی از داده‌ها را دستکاری کند. مانند یک ماشین تورینگ، یک ماشین واقعی می‌تواند فضای ذخیره‌سازی خود را با نیاز به خرید دیسک‌ها یا رسانه‌های ذخیره‌سازی دیگر گسترش دهد. توصیف برنامه‌های ماشین‌های واقعی با استفاده از مدل‌های انتزاعی ساده‌تر اغلب پیچیده‌تر از توصیف‌ها با استفاده از ماشین‌های تورینگ است. به عنوان مثال، یک ماشین تورینگ که یک الگوریتم را توصیف می‌کند می‌تواند چند صد وضعیت داشته باشد، در حالی که معادل آن در یک ماشین واقعی، یک اتوماتای قطعی حالت محدود (DFA) ممکن است میلیاردها وضعیت داشته باشد. ماشین‌های تورینگ الگوریتم‌ها را به‌طور مستقل از مقدار حافظه‌ای که استفاده می‌کنند توصیف می‌کنند. برای هر ماشینی حدی برای حافظه وجود دارد، اما این حد می‌تواند به طور دلخواه در طول زمان افزایش یابد. ماشین‌های تورینگ به ما این امکان را می‌دهند که بیانیه‌هایی درباره‌ی الگوریتم‌ها بدهیم که (از نظر نظری) برای همیشه صادق خواهند بود، صرف‌نظر از پیشرفت‌های معماری ماشین‌های محاسباتی متداول. الگوریتم‌هایی که روی ماشین‌های انتزاعی معادل تورینگ اجرا می‌شوند، می‌توانند انواع داده‌ای با دقت دلخواه داشته باشند و نیازی به مواجهه با شرایط غیرمنتظره (از جمله، اما نه محدود به، تمام شدن حافظه) نخواهند داشت. به‌عنوان مثال، کامپیوترهای مدرن برنامه ذخیره‌شده در واقع نمونه‌هایی از یک فرم خاص از ماشین انتزاعی به نام مدل ماشین برنامه ذخیره‌شده با دسترسی تصادفی (RASP) هستند. مانند ماشین تورینگ جهانی، RASP برنامه خود را در "حافظه" خارجی نسبت به "دستورات" ماشین حالت محدود خود ذخیره می‌کند. ماشین حالت محدود RASP قابلیت آدرس‌دهی غیرمستقیم دارد (مثلاً محتویات یک ثبات می‌تواند به‌عنوان آدرس برای مشخص کردن یک ثبات دیگر استفاده شود)؛ بنابراین "برنامه" RASP می‌تواند به هر ثبات در دنباله ثبات‌ها دسترسی پیدا کند. نتیجه این تفاوت این است که بهینه‌سازی‌های محاسباتی‌ای وجود دارند که می‌توانند بر اساس شاخص‌های حافظه انجام شوند، که در ماشین تورینگ عمومی ممکن نیستند؛ بنابراین وقتی ماشین‌های تورینگ به‌عنوان مبنای تعیین محدودیت زمان اجرا استفاده می‌شوند، می‌توان یک "حد پایین کاذب" را برای زمان‌های اجرای الگوریتم‌های خاص ثابت کرد (به دلیل فرض ساده‌سازی غلط در مورد ماشین تورینگ). یکی از مثال‌های این موضوع جستجوی دودویی است، الگوریتمی که می‌تواند نشان داده شود که سریع‌تر اجرا می‌شود هنگامی که از مدل محاسباتی RASP استفاده می‌شود تا مدل ماشین تورینگ. تعامل در روزهای اولیه محاسبات، استفاده از کامپیوتر معمولاً به پردازش دسته‌ای محدود بود، یعنی کارهای غیرتعاملی که هر کدام داده‌های خروجی را از داده‌های ورودی معین تولید می‌کردند. نظریه محاسبات‌پذیری، که محاسبات‌پذیری توابع از ورودی‌ها به خروجی‌ها را مطالعه می‌کند و برای آن ماشین‌های تورینگ اختراع شدند، بازتابی از این عمل بود. به‌طور اصولی، این را می‌توان با داشتن یک عامل خارجی که به‌طور همزمان از نوار می‌خواند و به آن می‌نویسد، مدل‌سازی کرد، اما این معمولاً مطابق با نحوه تعامل واقعی نیست؛ بنابراین، هنگام توصیف تعامل، گزینه‌های دیگری مانند اتوماتای ورودی/خروجی معمولاً ترجیح داده می‌شوند. تاریخچه زمینه تاریخی: ماشین‌های محاسباتی رابین گاندی (۱۹۱۹–۱۹۹۵)—دانشجوی آلن تورینگ (۱۹۱۲–۱۹۵۴) و دوست مادام‌العمر او—نسب مفهوم "ماشین محاسباتی" را به چارلز ببیج (حدود ۱۸۳۴) برمی‌گرداند و حتی "تز ببیج" را پیشنهاد می‌دهد: تحلیل گاندی از ماشین تحلیلی ببیج پنج عملیات زیر را توصیف می‌کند (نگاه کنید به ص. گاندی بیان می‌کند که "توابعی که می‌توانند توسط (۱)، (۲)، و (۴) محاسبه شوند دقیقاً آن‌هایی هستند که قابل محاسبه با تورینگ هستند." (ص. او به پیشنهادهای دیگر برای "ماشین‌های محاسباتی جهانی" از جمله پرسی لودگیت (۱۹۰۹)، لئوناردو تورس کوئودو (۱۹۱۴)،L. موریس داکن (۱۹۲۲)، لویی کوفینیال (۱۹۳۳)، ونوار بوش (۱۹۳۶)، هوارد آیکن (۱۹۳۷) اشاره می‌کند. | ## جمع‌بندی | اما: مسئله تصمیم‌گیری: سؤال دهم هیلبرت در سال ۱۹۰۰ با توجه به مسائل هیلبرت که توسط ریاضیدان مشهور دیوید هیلبرت در سال ۱۹۰۰ مطرح شد، جنبه‌ای از مسئله شماره ۱۰ تقریباً ۳۰ سال شناور بود تا زمانی که به‌طور دقیق مطرح شد.