انواع ماشینهای محاسبه تورینگ چیست و چه کاربردی دارد؟
ماشین تورینگ جهانی
یک ماشین محاسبه تورینگ یک متغیر محاسباتی خاص را با استفاده از رشته‌ای از داده‌ها از طریق الفبای (صفر و یک) آن محاسبه می‌کند. از این لحاظ، این ماشین مانند یک کامپیوتر با برنامه ثابت عمل می‌نماید؛ ولیکن، می‌توان جدول عملگرهای هر ماشین تورینگی را به صورت رشته‌ای از داده‌ها رمزگذاری نمود؛ بنابراین می‌توان ماشین محاسبه تورینگی ساخت که بر روی نوار ذخیره اطلاعات آن رشته‌ای از داده‌ها برای توصیف جدول عملگرها به همراه رشته‌ای برای توصیف نوار ورودی وجود داشته باشد و نواری را که ماشین تورینگ رمزگذاری کرده‌است، محاسبه نماید. تورینگ در مقاله سال ۱۹۳۶ خود این ساختار را با جزئیات کامل توصیف نمود: "این امکان وجود دارد که ماشینی را اختراع نمود تا بتواند هر تابع قابل محاسبه‌ای را محاسبه نماید. اگر این ماشین (U) دارای نواری باشد که در ابتدای آن توضیحات استاندارد (S.D) از جدول عملگرهای بعضی از ماشینهای محاسبه M نوشته شده باشد بنابراین U یعنی ماشین می‌تواند همان تابع را به عنوان M محاسبه نماید.
آزمون تورینگ
تست تورینگ یک تست از توانایی ماشین است برای نمایش دادن رفتاری هوشمندانه شبیه به انسان. آزمون تورینگ در سال ۱۹۵۰ توسط آلن تورینگ، ریاضیدان انگلیسی مطرح گردید. ایت آزمون توانایی یک ماشین در نشان دادن رفتار هوشمندانه معادل، یا غیرقابل تشخیص از یک انسان است. تورینگ پیشنهاد کرد که یک ارزیاب انسانی در مورد مکالمات زبان طبیعی بین یک انسان و ماشینی که برای تولید پاسخ های شبیه انسان طراحی شده است، قضاوت کند. ارزیاب آگاه خواهد بود که یکی از دو شریک در گفتگو یک ماشین است، و همه شرکت کنندگان از یکدیگر جدا خواهند شد. مکالمه به یک کانال تنها متن مانند صفحه کلید کامپیوتر و صفحه نمایش محدود می شود تا نتیجه به توانایی ماشین در تبدیل گفتار به کلمات بستگی نداشته باشد. [3] اگر ارزیاب نتواند به طور قابل اعتمادی به ماشین از انسان بگوید، گفته می شود که ماشین آزمایش را پشت سر کرده است. نتایج آزمایش به توانایی ماشین در دادن پاسخ های درست به سوالات بستگی ندارد، تنها اینکه پاسخ های آن چقدر نزدیک به پاسخ هایی است که یک انسان میدهد. ماشین تورینگ متناوب
formula_35 به صورت مشابه برای محاسبات با حافظهٔ محدود تعریف می‌شود. نظریه محاسباتی ذهن
محاسبگر فقط به معنی یک کامپیوتر الکترونیکی مدرن نیست بلکه یک دست کاری‌کننده نمادهاست که اعمال گام به گام را برای محاسبه روی ورودی و ایجاد خروجی دنبال می‌کند. آلن تورینگ این نوع ماشین محاسبه گر را با ماشین تورینگ توصیف می‌کند. ماشین تورینگ چندمسیره
اگر بخواهیم یک ماشین تورینگ تک مجرایی معادل با ماشین تورینگ ۲ مجرایی بسازیم، الفبای آن به صورت زوج مرتب تعریف می‌شود. نماد a از ماشین تورینگ 'M به شکل یک زوج مراتب [x,y] در ماشین تورینگ M تعریف می‌شود. ماشین تورینگ تک نوارهٔ معادل به صورت زیر تعریف می‌شود: M= formula_15 که تابع انتقال آن برابر است با formula_16 کامل بودن تورینگ
کامپیوتری با دستیابی به نوار نامتناهی به داده‌ها، قدرتمندتر از یک دستگاه تورینگ می‌باشد زیرا این نوار می‌تواند در اصل شامل راه حلی برای مشکلات مکث کردن یا هر مشکلا غیرقابل تصمیم‌گیری دیگری باشد. نوار نامتناهی داده‌ها، یک اوراکل تورینگ می‌باشد. حتی یک اوراکل تورینگ با داده‌های تصادفی، قابل محاسبه نمی‌باشد زیرا تنها محاسبات زیادی وجود دارند ولی اوراکل‌های زیادی وجود دارند. دستگاهی که به استثناء دستیابی به برخی از اوراکل‌های تورینگ، جامع است، جامع ضعیف نامیده می‌شود. ماشین تورینگ متناوب
این کلاس‌ها، با در نظر گرفتن منابعی که یک ATM به جای ماشین تورینگ قطعی استفاده می‌کند، شبیه به تعریف‌های P و PSPACE و EXPTIME هستند. محاسبه‌پذیری
در اینجا ممکن است بیش از یک نوار وجود داشته باشد. و حتی ممکن است چندین head برای یک نوار وجود داشته باشد. با کمال تعجب، هر محاسبه‌ای که می‌تواند توسط این نوع ماشین انجام شود می‌تواند توسط یک ماشین تورینگ معمولی نیز انجام شود، هر چند که حالت دوم ممکن است آهسته‌تر باشد یا به یک منطقه بزرگتر از نوار نیاز داشته باشد. الگوریتم‌های مافوق بازگشتی
در نظریهٔ محاسبه پذیری، الگوریتم‌های مافوق بازگشتی، (به انگلیسی: Super-recursive algorithm)تعمیمی از الگوریتم‌های معمولی هستند که قدرت بیشتری برای محاسبه دارند. یعنی در واقع از قدرت محاسبهٔ آن‌ها از ماشین تورینگ بیشتر است. این عبارت برای اولین بار توسط مارک بورگین عنوان شد. وی کتابی به همین نام دارد که در آن این نظریه گسترش یافته و مدل‌های ریاضی مختلفی برای آن ارائه کرده است. ماشین تورینگ و دیگر مدل‌های الگوریتم‌های معمولی به محققان اجازه می‌دهند تا خواص الگوریتم‌های بازگشتی و نحوهٔ محاسبهٔ آن‌ها را کشف کنند. به همین ترتیب مدل‌های ریاضی الگوریتم‌های مافوق بازگشتی، مثل ماشین تورینگ استنتاجی، به محققان کمک می‌کنند تا خواص و نحوهٔ محاسبهٔ الگوریتم‌های مافوق بازگشتی را کشف کنند. بورگین، همانند دیگر محققان (از جمله سلیم آکل، ایگویین ابرباخ، پیتر کوگل، جان ون لویین، هاوا سیگلمن، پیتر ونگر و جیری ویدرمن) این نظریه که انواع مختلفی از الگوریتم‌های مافوق بازگشتی را مورد بررسی قرار داده و به گسترش آن کمک کرده‌اند؛ استدلال می‌کنند که نظریه الگوریتم‌های مافوق بازگشتی می‌تواند برای رد قضیهٔ چرچ-تورینگ مورد استفاده قرار بگیرد، اما این دیدگاه از طرف جامعهٔ ریاضی دانان مورد نقد قرار گرفته است و به همین دلیل مورد اقبال عمومی نمی‌باشد. ماشین پست-تورینگ
این ماشین پُست-تورینگ عملیات محاسبهٔ ضرب را به صورت بازگشتی توسط دو حلقه انجام می‌دهد. آزمون تورینگ
تورینگ پیش بینی کرد که ماشین ها در نهایت قادر خواهند بود آزمون را بگذرانند؛ در واقع او تخمین زد که تا سال ۲۰۰۰ ماشین هایی با حدود ۱۰۰ مگابایت ذخیره سازی قادر خواهند بود ۳۰٪ قضات انسان را در یک آزمایش پنج دقیقه ای گول بزنند و مردم دیگر عبارت «ماشین تفکر» را متناقض در نظر نخواهند گرفت. [۵] (در عمل، از سال ۲۰۰۹–۲۰۱۲، شرکت کنندگان جایزه لوبنر تنها یکبار موفق به گول زدن یک قاضی شدند، [۹۶] و این تنها به دلیل شرکت کننده انسانی¬ای بود که وانمود می کرد چت بات است. [97]) او بیشتر پیش بینی کرد که یادگیری ماشین بخش مهمی از ساخت ماشین های قدرتمند خواهد بود، ادعایی که توسط محققان معاصر در هوش مصنوعی قابل قبول تلقی می شود. [70] دکتر شین تی مولر در مقاله ای که در سال ۲۰۰۸ به نوزدهمین کنفرانس هوش مصنوعی و علوم شناختی غرب میانه ارائه شد، پیش بینی کرد که یک آزمایش تورینگ اصلاح شده به نام «دکاتلون شناختی» می تواند ظرف پنج سال انجام شود. [98] ری کورزویل آینده گرا با برون یابی رشد نمایی فناوری در طول چند دهه پیش بینی کرد که رایانه های با قابلیت آزمایش تورینگ در آینده ای نزدیک ساخته خواهند شد. او در سال ۱۹۹۰ سال را در حدود سال ۲۰۲۰ تعیین کرد. [۹۹] تا سال ۲۰۰۵، او برآورد خود را تا سال ۲۰۲۹ تمدید کرده بود. [100] پروژه شرط بندی طولانی شرط Nr. 1 شرط بندی 20،000 دلار بین میچ کاپور (بدبین) و ری کورزویل (خوش بین) در مورد اینکه آیا یک کامپیوتر موفق خواهد شد که آزمون تورینگ طولانی را تا سال 2029 بگذارند. در طول آزمون طولانی در حال حاضر تورینگ، هر یک از سه قاضی آزمون تورینگ مصاحبه های آنلاین از هر یک از چهار نامزد آزمون تورینگ (یکی، کامپیوتر و سه تورینگ تست فویل انسان) به مدت دو ساعت هر یک به مدت مجموع هشت ساعت مصاحبه انجام دهد. شرط بندی برخی شرایط را در به جزئیات مشخص می کند. [101] سال ۱۹۹۰ چهارمین سالگرد اولین انتشار مقاله «ماشین آلات و هوش محاسباتی» تورینگ بود و علاقه مجدد به این آزمون را به خود دید. دو رویداد قابل توجه در آن سال رخ داد: اولی کنفرانس تورینگ بود که در ماه آوریل در دانشگاه ساسکس برگزار شد، و دانشگاهیان و محققان را از رشته های بسیار متنوعی گرد هم آورد تا در مورد آزمون تورینگ از نظر گذشته، حال و آینده اش بحث کنند؛ دومی تشکیل مسابقه سالانه جایزه لوبنر بود. بلای ویتبی چهار نقطه عطف عمده در تاریخ آزمون تورینگ را یاد کرد- انتشار "ماشین آلات محاسباتی و هوش" در سال ۱۹۵۰، معرفی ELLIZA توسط جوزف ویزنبام در سال ۱۹۶۶، توسعه¬ی PARRY توسط کنت کولبی که برای اولین بار در سال ۱۹۷۲ معرفی شد و کنفرانس تورینگ در سال 1990. [102] ماشین تورینگ متقارن
در تعریف این ماشین‌ها به صورت رسمی، دسته‌ای از ماشین‌های تورینگ را با استفاده از مجموعه از انتقال‌ها به شکل (p,ab,D،cd,q) تعریف می‌کنیم که در آن p و q نشان دهنده وضعیت‌های ماشین، ab و cd زوج‌هایی از نمادها و D نشان دهنده جهت حرکت کلاهک است. بورینگ
تراشکاری بورینگ یک عملیات برشکاری است که با استفاده از یک ابزار برش تک نقطه‌ای یا یک سر بورینگ با بزرگ کردن دهانه موجود در یک قطعه کار ، سطوح مخروطی یا استوانه ای تولید می‌کند. برای سوراخ‌های غیر مخروطی ، ابزار برش موازی با محور چرخش حرکت می‌کند. برای سوراخ‌های مخروطی، ابزار برش با یک زاویه نسبت به محور چرخش حرکت می‌کند. هندسه‌های متفاوتی از بسیار ساده تا بسیار پیچیده با قطرهای مختلف را می‌توان با استفاده از کاربردهای بورینگ تولید کرد. بورینگ یکی از اساسی ترین کارهای ماشین تراش در کنار تراشکاری و حفاری و سوراخکاری است. ماشین تورینگ جهانی
او این رمز را در مربع‌های یک در میان قرار داده‌است یعنی "مربعهای F" و خالی گذارن مربع‌های E. جمع‌بندی نهایی کدها بر روی نوار ماشین محاسبه شامل قرار دادن دو نماد خاص ('e') یکی پس از دیگری، و سپس رمزی که مربع‌ها را از یکدیگر جدا کرده‌است و بالاخره نماد '::' (فضای خالی که با "." نمایش داده شده برای درک بهتر) ee. ; D.A.D.D.C.R.D.A.A. ;.D.A.A.D.D.A.A.A. ;.D.A.A.A.D.D.C.C.R.D.A.A.A.A. ;.D.A.A.A.A.D.D.R.D.A. :: ماشین خواندنی تورینگ
این مدل معادل با DFA است. اثبات آن شامل ساخت جدولی است که نتایج حاصل از پیمایش معکوس با شرایط خاص را برای هر وضعیت داده شده فهرست می‌کند. در آغاز محاسبه، پیمایش معکوس برابر با تلاش برای گذشتن از نشانگر پایان است. ماشین خواندنی تورینگ
حالت‌های دیگر این مدل، پیچیدگی‌های محاسباتی بیشتری دارند. با یک پشتهٔ نا متناهی، این مدل می‌تواند تمام زبان‌هایی را که، با ماشین تورینگ در مرتبهٔ زمانی خطی پردازش می‌شوند، تجزیه کند. به عنوان یک حالت خاص، زبان {abc} می‌تواند، تحت‌الگوریتمی که ابتدا تشخیص دهد تعداد aها و bها برابر و سپس تعداد bها و cها برابر هستند، تجزیه شود. ریاضیات
علوم رایانه شامل نظریه محاسبه پذیری، نظریه پیچیدگی محاسباتی و نظریه اطلاعات است. نظریه رایانش‌پذیری محدودیت‌های مدل‌های مختلف نظری رایانه‌ها را بررسی می‌کند که شامل بسیاری از مدل‌های شناخته شده چون ماشین تورینگ می‌شود. نظریه پیچیدگی به مطالعهٔ رام پذیری حل مسائل در رایانه می‌پردازد. برخی مسائل وجود دارند که با وجود این که از لحاظ نظری توسط رایانه قابل حل هستند، اما در عمل هزینه حل کردنشان از نظر زمان یا فضا زیاد است و عملاً با وجود پیشرفت‌های سریع سخت‌افزاری در دنیای رایانه حل آن‌ها به نظر نامعقول می‌آید. یک مسئله مشهور در این وادی مسئلهٔ "P=NP"؟ است که برای حل آن جایزهٔ مسائل هزاره تعیین شده‌است. در نهایت، نظریه اطلاعات با حجمی از داده‌ها سر و کار دارد که بتوان آن‌ها را بر روی یک وسیله خاص ذخیره کرد، پس این علم با مفاهیمی چون فشرده سازی و انتروپی سروکار دارد. ماشین خواندنی تورینگ
در حقیقت این ماشین‌ها از نظر قدرت محاسباتی معادل یک ماشین تعیین‌پذیر حالات متناهی هستند که فقط می‌توانند عمل تجزیه و تحلیل را روی یک زبان منظم انجام دهند. ماشین تورینگ متناوب
در نظریه پیچیدگی محاسباتی، یک ماشین تورینگ متناوب ، ماشین تورینگی غیر قطعی است و شامل قانونی برای پذیرش محاسباتی است که قوانین استفاده شده در تعریف کلاس‌های پیچیدگی NP و co-NP را کلیت می‌بخشد. مفهوم ATM توسط Chandra و Stockmeyer و مستقلاً توسط Kozen در سال ۱۹۷۶، و سپس به صورت مشترک، باانتشار در یک مجله در سال ۱۹۸۱ مطرح شد. ماشین تورینگ غیرقطعی
در علوم کامپیوتر نظری، ماشین تورینگ نظری یک ماشین است که در آزمایش‌های فکری برای آزمایش توانایی‌ها و محدودیت‌های کامپیوتر استفاده می‌شود. دراصل، ماشین تورینگ به صورت یک کامپیوتر ساده تصور می‌شود که با دنبال کردن مجموئه‌ای از قوانین، نمادها را در واحد زمان می‌خواند و بر روی یک نوار بی پایان می‌نویسد؛ و با توجه به وضعیت جاری نمادی که دیده است، تعیین می‌کند چه عملی باید انجام دهد. یک مثال از قوانین ماشین تورینگ: «اگر در وضعیت ۲ هستید و نماد 'A' دیدید، آن را به 'B' تغییر دهید و به چپ بروید.» ماشین تورینگ جهانی
جدول عملگرهای ماشین محاسبه (جدول تغییر حالت) مسئول رمزگشایی نمادها است. جدول عملکرد تورینگ با قرار دادن حروف نشانه 'u', 'v', 'x', 'y'، 'z' در "مربعهای E" در سمت راست نماد مشخص شده، کاملاً از جایگاه خود آگاهی می‌یابد. مثلاً برای نشان دادن دستور جاری، z در سمت راست علامت ';' قرار می‌گیرد و x ترتیب کنونی m با DAA را حفظ می‌کند. جدول عملگرهای ماشین محاسبه در طی اجرای فرایند محاسبه بین این نمادها حرکت می‌کند (آن‌ها را حذف می‌کند و در محل‌های دیگری قرار می‌دهد) ee. ; D.A.D.D.C.R.D.A.A. ;zD.A.AxD.D.R.D.A.A.A. ;.D.A.A.A.D.D.C.C.R.D.A.A.A.A. ;.D.A.A.A.A.D.D.R.D.A. :: جدول عملگرهای تورینگ در ماشین محاسباتی وی بسیار کاربرد دارد. ماشین تورینگ متناوب
ATM برای بررسی تمام مقادیر متغیرهای وجودی (از چپ به راست) به صورت وجودی و برای بررسی تمام مقادیر متغیرهای عمومی (از چپ به راست) به صورت عمومی منشعب می‌شود. پس از بررسی یک مقدار برای تمامی متغیرها، اگر نتیجه Boolean formula برابر true باشد ماشین آن را پذیرش و اگر false باشد ماشین آن را نمی‌پذیرد. ماشین تورینگ
یکی از محدودیت‌ها و معایب ماشین‌های تورینگ این است که آن‌ها توانایی چیدمان خوب را ندارند. برای مثال کامپیوترهای برنامه‌ای با ذخیره مدرن، نمونه‌هایی از یک مدل خاص ماشین انتزاعی که به نام ماشین برنامه دسترسی رندم یا مدل ماشین RASP می‌باشند. بورینگ
ماشین‌های بورینگ در اندازه و سبک‌های با تنوع زیاد ارائه می‌شوند. بورینگ روی قطعه‌های کوچک را می‌توان روی ماشین تراش انجام داد در حالی که قطعه های بزرگتر روی فرز بورینگ تراشیده می‌شوند. قطعه‌کارها معمولاً 1 تا 4 متر (3 فوت 3 تا 13 فوت 1 اینچ) اندازه دارند ، اما می‌توانند به اندازه 20 متر (66 فوت) برسند. قدرت مورد نیاز می‌تواند تا 200 اسب بخار (150 کیلووات) باشد. خنک‌سازی منافذ از طریق یک مجرای توخالی از طریق میله بورینگ انجام می‌شود که در آن ماده خنک‌کننده می‌تواند آزادانه جریان یابد. دیسک‌های آلیاژ تنگستن در ميله مهر و موم می‌شوند تا اثرات ارتعاشات و صداها را در حين عمليات بورينگ خنثي كنند. سیستم‌های کنترل می‌توانند مبتنی بر رایانه باشند ، امکان اتوماسیون و افزایش استحكام و ثبات را فراهم می‌کنند. از آنجا که منظور از بورينگ کاهش تلورانس در حفره‌هايي كه از قبل در قطعه وجود دارد، است، چندین ملاحظات طراحی اعمال می‌شود. اول ، سوراخ‌هاي با قطر بزرگ در مقايسه با طول به دلیل انحراف ابزار برش ترجیح داده نمی‌شوند. سپس، سوراخ‌هايي كه از ميان قطعه عبور مي‌كنند نسبت به سوراخ‌هاي كور(سوراخ‌هایی که ضخامت قطعه‌کار را طي نمي‌كنند) ترجيح داده مي‌شوند. ترجیحاً از سطوح داخلی کار قطع شده، جایی که ابزار و سطح برش تماس ناپیوسته دارند، دوري شود. میله بورينگ بازوی برجسته دستگاهی است که ابزارهاي برش را در خود نگه می‌دارد و باید بسیار سفت و محکم باشد. ماشین خواندنی تورینگ
ماشین پشته‌ای کاهش‌پذیری تورینگ
از دیدگاه الگوریتمی، شرح عمل کاهش به این صورت است که الگوریتمی برای حل مسئلهٔ formula_1 تعریف می‌شود به‌طوری‌که در آن بخش اصلی حل مسئله بر دوش زیرروالی است که خود شامل الگوریتم حل مسئلهٔ formula_2 است. این پیاده‌سازی را می‌توان به کمک ماشین‌های اوراکل به انجام رساند. دو مجموعهٔ formula_1 و formula_2 متشکل از اعداد طبیعی را در نظر بگیرید. کاهش‌پذیری formula_1 به formula_2 به معنای وجود تابعی است که دامنهٔ آن مجموعهٔ formula_1 و تابع هدف آن مجموعهٔ formula_2 باشد و به صورت زیر نمایش داده می‌شود: ماشین تورینگ جهانی
داده در ماشین تورینگ می‌تواند به شکل الفبایی (صفر و یک) فرض شود، هر الفبای دیگری می‌تواند به شکل صفر و یک رمزگذاری گردد. عملکرد یک ماشین تورینگ (M) از طریق تابع متغیر آن تعریف می‌شود. این تابع نیز می‌تواند به سادگی به رشته‌ای از دستورهای صفر و یک تبدیل گردد. مقدار الفبای M، تعداد نوارهای ذخیره اطلاعات و اندازه فواصل آن‌ها می‌تواند از جدول توابع متغیر استخراج شود. حالات و نمادهای متفاوت از طریق جایگاه آن‌ها تعیین می‌شوند مثلاً دو حالت اول به‌طور قراردادی حالات شروع و پایان را نشان می‌دهند. در نتیجه، هر ماشین محاسبه تورینگ می‌تواند رشته‌ای از دستورهای الفبایی صفر و یک را رمزگذاری نماید. به علاوه، می‌توان نتیجه گرفت که هر گونه رمزگذاری نامعتبری نمایانگر یک محاسبه تورینگ نامعتبر است که متوقف می‌شود و هر ماشین تورینگ می‌تواند با رمزگذاری مداوم و ثابت با عدد قراردادی یک (۱) در انتهای یک دستور، تعداد نامحدودی رمزگذاری انجام دهد دقیقاً مانند توضیحاتی که در یک زبان برنامه‌نویسی می‌آید. تعجب‌آور نیست که با توجه به وجود عدد «گودل» و معادله محاسباتی میان ماشین تیورینگ و عملگرهای بازگشتی µ می‌توان به این رمزگذاری دست یافت. همچنین این توضیح و تفسیر در تمامی دستورهای باینری (صفر و یک) α و ماشین تورینگ Mα مشترک است. با نگاهی به آغاز این نوع رمزگذاری در سال ۱۹۹۶ توسط «هِنی» و «اِستِرن» می‌توان دریافت که اگر ماشین تورینگ را Mα فرض کنیم که داده X را در مراحل N متوقف می‌کند، پس ماشین محاسبه تورینگ چند نوارای به وجود می‌آید که در داده α، x (با فرض نوارهای متفاوت) در CN پردازش مراحل N را شروع می‌کند، C مقدار ثابتی است که به طول دستور x بستگی ندارد، اما به اندازه، تعداد نوارهای ذخیره اطلاعات و تعداد حالات M وابسته است. این عمل در متغیر O نیز شبیه‌سازی می‌شود. (N آغاز پردازش N) نظریه رایانش‌پذیری
دانشمندان کامپیوتر، برای مطالعهٔ جدی نظریه رایانش (شماره پذیری)، با یک مفهوم انتزاعی ریاضی برای کامپیوترها که مدل رایانش گفته می‌شود، سر و کار دارند. قاعده سازی‌های متعددی، برای استفاده وجود دارد، اما ماشین تورینگ(Turing) در این میان بیش‌ترین کاربرد را دارد. یک ماشین تورینگ را می‌توان هم ارز یک کامپیوتر شخصی رومیزی، در نظر گرفت، با حافظهٔ بی‌نهایت که به این حافظه از طریق تعداد زیادی تکه‌های کوچک گسسته، دسترسی دارد. دانشمندان کامپیوتر به دلیل قابلیت سادگی قاعده سازی، تحلیل و آنالیز و قابل استفاده برای اثبات نتایج از این ماشین استفاده می‌کنند. چون حافظهٔ بی‌نهایت یک نسبت غیر مادی در نظر گرفته می‌شود، برای هر مسئله که با استفاده از ماشین تورینگ حل می‌شود، حافظهٔ مورد استفاده همواره محدود است. در نتیجه هر مسئله را می‌توان با استفاده از یک کامپیوتر شخصی که حافظهٔ مورد نیاز بر روی آن نصب شده، از طریق یک ماشین تورینگ حل کرد. ماشین تورینگ چندمسیره
ماشین تورینگ چندمسیره یا چندمجرایی نوع خاصی از ماشین تورینگ چندنواره است. در یک ماشین تورینگ استاندارد با n نوار ،n کلاهک به صورت مستقل در امتداد n مسیر حرکت می‌کنند. در یک ماشین تورینگ چند مجرایی با n مجرا یک کلاهک روی تمام مجراها عمل خواندن و نوشتن را به صورت هم‌زمان انجام می‌دهد. هر موقعیت در این ماشین تورینگ شامل n نماد از حروف الفبا می‌باشد. این ماشین تورینگ، معادل ماشین تورینگ استاندارد است و زبان‌های شمارا را، که به صورت بازگشتی تعریف شده‌اند، می‌پذیرد. ماشین تورینگ چندمسیره
یک ماشین تورینگ چند مجرایی به صورت رسمی توسط یک ۶ تایی به صورت formula_1 تعریف می‌شود که در آن: ماشین تورینگ
۱-عملگرهای ریاضی + و - و *و% قضیه ماشین تورینگ جهانی
قابل شمارش می‌باشد . ماشین تورینگ متناوب
برای خروجی، وجود یا عدم وجود مداری که با K گیت بتواند تابع F را پیاده‌سازی کند، بررسی می‌شود. آلن تورینگ
تا امروز ماشین‌های تورینگ موضوع اصلی تحقیقات در تئوری محاسبات بوده‌اند. او برای اثبات این که «انسکیدانس پرابلم» هیچ حلی ندارد، ابتدا نشان داد که هالتینگ پرابلم برای ماشین تورینگ قابل حل نیست: مشخص نیست که ماشین تورینگ در چه زمانی متوقف می‌شود. ماشین تورینگ چندنواره
یک ماشین تورینگ چند نواره می‌تواند به صورت یک ۶ تائی‌ به فرم formula_1 تعریف شود که در آن‌: ماشین پست-تورینگ
مدل‌های معرفی شده همگی به لحاظ قدرت محاسباتی، معادل ماشین تورینگ استاندارد هستند. ماشین تورینگ
ماشین تورینگ یک دستگاه فرضی است که روی نشان‌های روی یک قطعه نوار بر اساس جدول قوانین دست‌کاری انجام می‌دهد. با وجود اینکه مکانیزم ماشین تورینگ مقدماتی است، مفهومش برای پوشش عملکردهای بسیار پیچیده کافی و گسترده‌است. ماشین تورینگ می‌تواند برای شبیه‌سازی هر الگوریتم کامپیوتری و توضیح نحوه عملکرد یک واحد پردازشگر مرکزی به کار آید. حافظه این ماشین ساختاری بسیار ساده دارد. یعنی می‌تواند به صورت یک آرایه یک بعدی از عناصر (سلولها) باشد که هر یک می‌توانند حافظ تنها یک نماد باشند. این آرایه از هر دو طرف باز و نامحدود است (حافظه بینهایت) و اطلاعات آن می‌توانند به هر ترتیبی فراخوانی شوند. ماشین تورینگ جهانی
در علوم رایانه‌ای، ماشین تورینگ جهانی نوعی ماشین محاسباتی است که می‌تواند براساس یک داده تصادفی یک محاسبه تورینگ تصادفی را شبیه‌سازی نماید. این ماشین محاسباتی اساساً با خواندن توضیح ماشین و نیز داده مربوطه از روی نوار موجود در خود ماشین این کار را انجام می‌دهد. آلن تورینگ این ماشین را بین سال‌های ۱۹۳۷–۱۹۳۶ معرفی کرد. این الگو از نظر بعضی (مانند مارتین دیویس) منشأ ساخت قطعه «ذخیره‌کننده دستورهای برنامه‌های کامپیوتری» می‌باشد که توسط جان فون نویمان در ابزار محاسباتی الکترونیکی بکار می‌رفت و اکنون در علم رایانه «ساختار فون نویمان» نام دارد. این ماشین همچنین ماشین محاسبه جامع، ماشین جامع (UM) و ماشین (U) نامیده می‌شود. ماشین تورینگ چندنواره
بنابراین ماشین تورینگ‌های چند نواره نمیتوانند توابع ای بیش از آنچه ماشین‌های تورینگ‌ چند نواره محاسبه میکنند ،محاسبه کنند و هیچ‌کدام از کلاس‌های پیچیدگی محاسباتی (مانندکلاس P ) با تغییر یک ماشین تورینگ چند نواره به تک نواره تحت تأثیر قرار نمی‌گیرند. ماشین تورینگ
۳. ماشین واقعی همانند ماشین‌های تورینگ می‌توانند حافظه مورد نیازش را به کمک دیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در حافظه‌شان ندارند. آزمون تورینگ
آزمون تورینگ روشی برای سنجش میزان هوشمندی ماشین است. آزمون به این صورت انجام می‌گیرد که یک شخص به عنوان آزمایشگر، با یک ماشین و یک انسان به گفتگو می‌نشیند، و سعی در تشخیص ماشین از انسان دارد. در صورتی که ماشین بتواند قاضی را به گونه‌ای بفریبد که در قضاوت خود دچار اشتباه شود، توانسته‌است آزمون را با موفقیت پشت سر بگذارد. برای اینکه تمرکز آزمون بر روی هوشمندی ماشین باشد، و نه توانایی آن در تقلید صدای انسان، مکالمه تنها از طریق متن و صفحه کلید و نمایشگر کامپیوتر صورت می‌گیرد. ماشین خواندنی تورینگ
ماشین‌های خواندنی تورینگ یا ماشین‌های تعیین‌پذیر حالات متناهی ۲مسیره رده‌ای از مدل‌های محاسبه پذیری هستند که مانند یک ماشین تورینگ استاندارد عمل می‌کنند و می‌توانند در هر ۲ جهت روی نوار حرکت کنند اما نمی‌توانند چیزی بنویسند. آزمون تورینگ
ساول ترایگر استدلال می کند که حداقل سه نسخه اولیه از آزمون تورینگ وجود دارد که دو نسخه از آن ها در "ماشین آلات محاسباتی و هوش" و نسخه ای که او آن را «تفسیر استاندارد» توصیف می کند، ارائه می شود. [46] در حالی که برخی بحث ها در مورد اینکه آیا "تفسیر استاندارد"آن است که توسط تورینگ توصیف شده است و یا، در عوض، بر اساس خواندن غلط مقاله، این سه نسخه به عنوان معادل در نظر گرفته نمی شود،[46] و نقاط قوت و ضعف خود را دارند. [47] هوما شاه اشاره می کند که خود تورینگ نگران این بود که آیا یک ماشین می تواند فکر کند یا نه و روش ساده ای برای بررسی این موضوع ارائه می داد: از طریق جلسات پرسش و پاسخ انسان-ماشین. [۴۸] شاه استدلال می کند که یک بازی تقلیدی وجود دارد که همنطور که تورینگ توصیف کرد می تواند به دو روش مختلف عملی شود: الف) آزمون بازپرس-ماشین یک به یک، و ب) مقایسه همزمان یک ماشین با یک انسان، هر دو به موازات یک بازپرس مورد پرسش قرار می گیرد. [25] از آنجا که آزمون تورینگ آزمونی از تشخیص ناپذیری در ظرفیت عملکرد است، نسخه کلامی به طور طبیعی به تمام ظرفیت عملکرد انسان، کلامی و همچنین غیرکلامی (رباتیک) عمومیت می بخشد. [49] مقاله اصلی تورینگ یک بازی مهمانی ساده را توصیف می کند که شامل سه بازیکن می شود. بازیکن الف مرد است، بازیکن ب یک زن است و بازیکن ج (که نقش بازجو را بازی می کند) از هر دو جنس است. در بازی تقلید، بازیکن ج قادر به دیدن بازیکن الف یا بازیکن ب نیست، و تنها از طریق یادداشت های کتبی می تواند با آن ها ارتباط برقرار کند. بازیکن ج با پرسیدن سوالات از بازیکن الف و بازیکن ب سعی می کند مشخص کند که کدام یک از این دو مرد است و کدام زن است. نقش بازیکن الف این است که فریب بازجو را به تصمیم گیری اشتباه، در حالی که بازیکن ب تلاش برای کمک به بازجو در ساخت یکی از حق است. [7] تورینگ سپس می پرسد: چه اتفاقی خواهد افتاد زمانی که یک ماشین نقش الف را در این بازی ایفا کند؟ آیا بازجو همانطور به اشتباه تصمیم خواهد گرفت مانند هنگامی که در نسخه ی اصلی بازی اشتباه تصمیم میگرفت؟ این سوالات جایگزین اصلی ما می شوند، "آیا ماشین ها می توانند فکر کنند؟" [24] ماشین تورینگ متقارن
اثبات از ضرب زیگزاگی گراف‌ها برای ساخت expander گراف‌ها به صورت بهینه، استفاده می‌کند ان‌پی کامل
دو تعریف برای NP یکی به عنوان مجموعه مسائلی که قابل حل با ماشین تورینگ غیرقطعی در زمان اجرای چندجمله‌ای هستند و دیگری مجموعه مسائلی که دارای یک بررسی‌کننده با زمان اجرای چندجمله‌ای در یک ماشین تورینگ قطعی هستند با هم معادلند. اثبات این برابری در بسیاری از کتاب‌ها آمده‌است به‌طور مثال در کتاب: Sipser’s Introduction to the theory of computation section ۷٫۳ برای نشان دادن این ابتدا فکر کنیم که یک بررسی‌کننده قطعی داریم یک ماشین تورینگ غیرقطعی می‌تواند به راحتی به صورت غیرقطعی بررسی‌کننده را بر روی تمام حالات ممکن از رشته‌ها بررسی کند. (این کار تنها نیازمند مراحل چند جمله گونه است زیرا این ماشین می‌تواند با حرکات غیرقطعی کاراکتر بعدی را در رشتهٔ مورد نظر را در هر مرحله پیدا کند و طول رشتهٔ داده شده نیز باید محدود به چندجمله‌ای باشد) اگر یکی از این رشته‌های بررسی‌کننده معتبر باشد بعضی از مسیرها مورد قبول واقع می‌شوند و اگر هیچ رشته‌ای معتبر نباشد رشته یک زبان به حساب نمی‌آید و پس داده می‌شود. از طرف دیگر فرض کنیم ما یک ماشین تورینگ غیرقطعی به نام A داشته باشیم و یک زبان L به آن ارائه کنیم. در هر کدام از مراحل با شمار چندجمله‌ای این ماشین، شاخه‌های درخت محاسبه با یک عدد صحیح ثابت مشخص می‌شوند که نشان دهندهٔ جهت هاست. وجود حداقل یک راه درست الزامی است و رشته‌ای که این مسیر را مشخص می‌کند گواهی برای بررسی‌کننده است. پس از آن اثبات‌کننده می‌تواند به صورت قطعی A را به صورت عبور از مسیر پذیرفته شده و بررسی اینکه ار آخر نیز پذیرفته می‌شود پیاده‌سازی کند. اگر A داده را قبول نکند هیچ راه پذیرفته شده‌ای وجود ندارد و بررسی‌کننده هیچ‌گاه به جواب بله نمی‌رسد. ماشین تورینگ
ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت formula_1، که در اینجا: به‌طور کلی formula_8 یک تابع جزئی روی formula_13 است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند. ماشین تورینگ متناوب
ماشین تورینگ متناوبی که یک تناوب دارد و از حالتی وجودی آغاز به کار می‌کند می‌تواند این مسئله را در مرتبهٔ زمانی چند جمله‌ای حل کند.(این کار با آزمایش مدارهای احتمالی با K گیت و مقایسه خروجی آنها با مدار اصلی انجام می‌شود). ماشین تورینگ غیرقطعی
ماشین تورینگ معمولی (قطعی - DTM) دارای تابع انتقال است که برای وضعیت داده شده و نمادی که روی نوار به آن اشاره می‌شود، ۳ چیز را مشخص می‌کند: نمادی که باید روی نوار نوشته شود، جهت حرکت هد (چپ، راست یا هیچکدام) و وضعیت بعدی ... ماشین تورینگ غیرقطعی
روش دیگر شبیه‌سازی NTM، استفاده از DTM با ۳ نواراست؛ که نوار اول همیشه ورودی اولیه را نگهداری می‌کند، نوار دوم محاسبات مشخص NTM را شبیه‌سازی می‌کند و نوار سوم مسیر را در درخت محاسبات NTM کدگذاری می‌کند. ماشین پست-تورینگ
در سال ۱۹۷۸ دیویس دومین مدل خود را در قالب مقالهٔ "محاسبات چیست" (به انگلیسی: "what is computation") به نام ماشین تورینگ-پُست ارائه کرد. سیستم قطعی
یک مدل محاسبه قطعی، برای نمونه یک ماشین تورینگ قطعی، یک مدل از محاسبه است به گونه‌ای که حالت‌های پیاپی ماشین و عملیاتی که باید اجرا شود، کاملاً توسط حالت قبلی مشخص شده‌اند. ماشین تورینگ
در مدل‌های ۴تایی پاک کردن یا نوشتن یک نماد (a_j۱) و حرکت کلاهک نوار به سمت چپ یا راست (d_k) به صورت دستورالعمل‌های جداگانه مشخص شده‌اند. به‌طور خاص، جدول به ماشین می‌گوید که چیزی را پاک کند یا یک نماد را بنویسد (ia) یا کلاهک نوار به سمت چپ و راست حرکت کند (ib). فرض کنید که حالتهای مشابه یا حالتهای جدیدی مشخص شده‌اند. اما عملیات‌های (ia) و (ib) دستورالعمل‌های یکسانی ندارند. در برخی از مدلها، اگر در جدول، ورودی از نمادها و حالتها نداشته باشیم، ماشین متوقف خواهد شد. سایر مدلها، نیاز به همه ورودی‌ها دارند تا پر شوند. توجه داشته باشید که هر بخش از ماشین- حالتها و نمادها، مجموعه‌ها، اقدامات، چاپ کردن، پاک کردن و حرکت نوار- محدود، گسسته و تشخیص پذیر است. این، پتانسیل نامحدود نوارهاست که خود مقدار نامحدودی از یک فضای ذخیره‌سازی است. نظریه محاسبات
از نظر دانشمندان رایانه مطالعه ماشین تورینگ به این دلیل ساده است که می‌توان با آن به تدوین، فرموله، تجزیه و تحلیل و اثبات نتایج پرداخت. در نظر آن‌ها ماشین تورینگ قدرتمندترین مدل یعنی مدل معقول از محاسبه را ممکن می‌سازد. ماشین تورینگ غیرقطعی
NTMها درموارد خاص شامل DTMها می‌شوند؛ بنابراین واضح است که DTMها قدرتمندتر نیستند. ممکن است به نظر برسد که NTMها از DTMها قدرتمندترند، زیرا آن‌ها یک درخت از محاسبات ممکن را ناشی از حالت مشابه ممکن می‌سازند و رشته را اگر هر یک از شاخه‌های درخت پذیرشش کند، می‌پذیرند. ماشین خواندنی تورینگ
ماشین خواندنی تورینگ در تعریف ماشین محاسبه تورینگ برای پذیرش ماشین تورینگی که می‌خواهد مدل سازی شود، استفاده می‌شود. پس از آن، محاسبات با یک ماشین تورینگ استاندارد ادامه می‌یابد. ان ال
به کمک تعریف اصلی ماشین تورینگ ساده که تنها دارای یک نوار است، مسائل پیچیدگی فضای لگاریتمی قابل بحث نیستند زیرا اندازه خود ورودی به صورت بدیهی از مرتبه formula_3 است و استفاده از حافظه از مرتبه formula_4 بی‌معنی خواهد بود. به همین دلیل تعریف ماشین تورینگ تغییر پیدا می‌کند. ماشین تورینگ متناوب
کلاس‌های پیچیدگی زیر برای تعریف ماشین تورینگ متناوب مورد استفاده قرار می‌گیرند: آلن تورینگ
او با معرفی ماشین تورینگ، یک مدل ریاضی برای تحلیل توانایی‌های ذاتی الگوریتم‌ها بنیان گذاشت. به همین دلیل ماشین تورینگ یکی از عناصر اصلی در نظریه محاسبات و نظریه پیچیدگی محاسباتی است. معادل‌های ماشین تورینگ
در این ماشین به جای نوار از یک طرف بینهایت از نوار بینهایت از دو طرف استفاده شده که قابل شبیه‌سازی با نوار یک طرفه است. ماشین تورینگ کوانتومی
یک ماشین تورینگ کوانتومی که به آن ماشین تورینگ جهانی نیز می‌گویند یک ماشین انتزاعی است که برای مدل کردن تأثیرات یک کامپیوتر کوانتومی استفاده می‌شود. این ماشین یک مدل بسیار ساده را ارائه می‌کند که قدرت محاسبات کوانتومی را نشان می‌دهد. هر الگوریتم کوانتومی می‌تواند به صورت رسمی توسط یک ماشین تورینگ کوانتومی بیان شود. این نوع ماشین تورینگ نخستین بار توسط دانشمند فیزیکدان دانشگاه اکسفورد David Deutsch در سال ۱۹۸۵ ارائه شد. وی پیشنهاد کرد که گیت‌های کوانتومی می‌توانند همانند گیت‌های منطقی دودویی کلاسیک عمل کنند. معمولاً ماشین‌های تورینگ کوانتومی برای آنالیز کردن محاسبات کوانتومی مورد استفاده قرار نمی‌گیرند و معمولاً از مدل مدارات کوانتومی که مدل‌های رایج تری هستند استفاده می‌شود و این مدل‌ها با یکدیگر معادل هستند. ماشین‌های تورینگ کوانتومی می‌توانند توسط ماتریس‌های انتقال با ماشین تورینگ‌های احتمالی کلاسیک معادل شوند. ماشین تورینگ
یکی دیگر از محدودیت‌های ماشین تورینگ این است که همزمانی را خوب ارائه نمی‌دهد. برای مثال برای اندازه عدد صحیحی که می‌تواند توسط «متوقف کننده غیر قطعی دایمی» محاسبه شود، محدودیت وجود دارد. ماشین تورینگ روی یک نوار خالی شروع می‌کند. در مقابل، ماشین‌های «همیشه متوقف» همزمان هستند که بدون ورودی می‌توانند عدد صحیح نامتناهی را محاسبه کنند. ماشین تورینگ
۶. ماشین تورینگ جملات الگوریتم را ساده می‌کند. الگوریتم‌های در حال اجرا در ماشین آلات انتزاعی معادل تورینگ، معمولاً نسبت به همتایان خود که در ماشین‌های واقعی در حال اجرا هستند عمومی ترند. زیرا آن‌ها دارای دقت دلخواه در انواع اطلاعات قابل دسترس هستند و هیچوقت با شرایط غیرمنتظره روبرو نمی‌شوند. یکی از نقطه ضعف‌های ماشین تورینگ این است که برنامه‌های واقعی که نوشته می‌شوند ورودی‌های نامحدودی را در طول زمان دریافت می‌کنند؛ در نتیجه هرگز متوقف نمی‌شوند. معادل‌های ماشین تورینگ
معادل‌های ماشین تورینگ (به انگلیسی ) می‌تواند توسط یک فرایند تک مرحله ای به ماشین تورینگ تبدیل شود. به صورت مخفف به آن معادل تورینگ نیز گفته می‌شود. یک زبان یا ابزار می‌تواند در تئوری یک زبان یا ابزار دیگر را شبیه‌سازی کند. توانایی معادل‌های تورینگ ماشین با خود ماشین تورینگ برابر است و بیشتر نیست اما می‌توانند در زمان و حافظهٔ کمتر یا بیشتری انجام شوند. از معروف‌ترین معادل‌های ماشین تورینگ می‌توان به ماشین تورینگ دارای چند نوار اشاره کرد. ماشین‌های تورینگ معادل انواع بسیار زیادی دارند که در ادامه به بررسی اجمالی آن‌ها می‌پردازیم. طیف وسیعی از آن‌ها را ماشین‌های تورینگ با حالت‌های مختلف برای نوار در بر می‌گیرند برای مثال می‌توان از ماشین وانگ نام برد. طیف دیگری از ماشین‌های تورینگ معادل ماشین‌های دارای رجیستر تشکیل می‌دهند که به جای نوار از رجیستر استفاده می‌کنند و انواع مختلفی دارند اولین آن‌ها ماشین شمارنده است. طیف دیگر آن‌ها نیز ماشین‌هایی با نوارهای ورودی و خروجی هستند. حتی ابزارها و الگوریتم‌هایی معادل ماشین تورینگ وجود دارد، برای مثال مدل محاسباتی جبر لاندا را می‌توان معادل یک تورینگ ماشین در نظر گرفت. ماشین تورینگ
اغلب گفته می‌شود که ماشین تورینگ، بر خلاف ماشین‌های اتومات، به اندازه ماشین‌های واقعی قدرتمند هستند و قادر به انجام هر عملیاتی که ماشین واقعی می‌تواند بکند هستند. چیزی که در این مطلب جا ماند این است که یک ماشین واقعی تنها می‌تواند در بسیاری از تنظیمات متناهی باشد؛ در واقع ماشین واقعی چیزی نیست جز یک ماشین اتوماتیک محدود خطی. از طرف دیگر ماشین تورینگ با ماشین‌هایی که دارای ظرفیت حافظه‌های نامحدود محاسباتی هستند، معادل است. از نظر تاریخی رایانه‌هایی که محاسبات را در حافظه داخلی شان انجام می‌دادند، بعدها توسعه داده شده‌اند. ماشین تورینگ متناوب
ماشین تورینگ متقارن یک ۵ تایی به صورتformula_1است که: ماشین اوراکل
به طرز جالبی، پارادوکس پایان‌پذیری هنوز در مورد این ماشین‌ها نیز صدق می‌کند؛ با وجود اینکه این ماشین‌ها می‌توانند تعیین کنند که آیا ماشین تورینگ خاصی با ورودی‌های خاصی به حالت پایان خواهد رسید، به‌طور کلی، آن‌ها نمی‌توانند تعیین کنند که آیا ماشین‌های معادل خودشان به حالت پایان خواهند رسید. این حقیقت منجر به ایجاد سلسله مراتبی از ماشین‌ها به نام سلسله مراتب محاسباتی می‌شود، که هر رده دارای اوراکل پایان‌پذیری قوی‌تر و مسئلۀ پایان‌پذیری قوی‌تری است. کامل بودن تورینگ
سیستم‌های محاسباتی (الجبرا، حساب) که به عنوان سیستم‌های تورینگ کامل موردبحث قرار می‌گیرند، سیستم‌های موردنظر برای مطالعه علوم کامپیوتری تئوریکی می‌باشند. آن‌ها خیلی ساده هستند بنابراین درک محدودیت‌های محاسباتی، اسانتراست. دراینجا برخی از آن‌ها موجود می‌باشند: اکثر زبان‌های برنامه‌نویسی، مرسوم و غیرمرسوم، تورینگ کامل می‌باشند. این زبان‌ها عبارتند از: تورنیگ کامل، گزاره‌ای از توانایی می‌باشد به جای تجویزی از ویژگی‌های خاص زبان استفاده شده برای پیاده‌سازی ان توانایی. ویژگی‌های استفاده شده برای انجام تورینگ کامل می‌توانند کاملاً متفاوت باشند. سیستم‌های فرترن از ساختارهای حلقه‌ای حتی گزاره‌های goto برای انجام تکرار استفاده می‌کنند؛ Haskell ,Prolog، که فاقد حله می‌باشند از بازگشت استفاده می‌کنند. تورینگ کامل در SQL، از طریق ویژگی‌های استاندارد پیشرفته پیاده‌سازی می‌شود، که دلیلی برای قدرتمندبودن زبان‌های غیراز تورینگ، نادر است. هرچقدر این زبان، قدرتمندتر باشد، وظایفی که برای ان انجام می‌شود، پیچیده‌تر می‌باشد و فقدان کامل بودن ان به صورت یک مانع و اشکال، زودتر می‌باشد و بسط والحاق ان را تشویق می‌کند تا اینکه تورینگ کامل شود. حساب لاندا، تورینگ کامل می‌باشد ولی حساب‌های لاندای زیادی شامل سیستم F تورینگ کامل نمی‌باشند. ارزش سیستم‌های معلوم شده مبتنی بر توانایی آن‌ها برای نمایش معمولترین برنامه‌های کامپیوتری در حین شناسایی خطاهای بیشتر می‌باشد. قانون ۱۱۰ و بازی زندگی Conway، تورینگ کامل می‌باشند. ماشین تورینگ جهانی
نمونه زیر برگرفته از نظریه تورینگ می‌باشد. برای کسب اطلاعات بیشتر در این زمینه به صفحه مثال‌های ماشین تورینگ مراجعه شود. تورینگ برای رمزگذاری هریک از ۵ حروف از ۷ نماد (A, C, D, R, L, N, ;) استفاده نمود، همان‌طور که در مقاله ماشین محاسبه تورینگ توضیح داده شد، ۷ حروف وی فقط از نوع N1, N2, N3 هستند. تعداد هر ترتیب m (دستورالعمل، حالت) با حرف 'D' نشان داده می‌شود که رشته‌ای از یگان A به دنبال دارد مثلاً Q3=DAAA. وی در روشی مشابه نماد blank (خالی) را با حرف 'D'، نماد "." را با حرف 'DC'، نماد "۱" را با حروف DCC رمزگذاری می‌کند. نماد 'R', 'L', 'N' به همان شکل باقی می‌مانند. ماشین پست-تورینگ
او مدل محاسباتی را در دوران تدریس در دانشگاه نیویورک و در سال ۱۹۷۳ و ۱۹۷۴ مورد استفاده قرار داد که آن را ماشین پُست-تورینگ نامیده‌است. دستورها زبان پُست-تورینگ به صورت ترتیبی اجرا می‌شوند و این‌گونه هستند: دقت شود که در این مدل هم دستوری برای توقف روال اجرا وجود ندارد و برنامه زمانی متوقف می‌شود که تمامی دستورها آن اجرا شده باشند. معادل‌های ماشین تورینگ
و یا اگر بخواهیم نحوهٔ تبدیل ماشین چندنواره تورینگ را به ماشین تک نواره تورینگ نشان می‌دهیم. در این ماشین هر نوار دارای هِد جداگانه برای نوشتن و خواندن است و تابع انتقال قابلیت خواندن، نوشتن و حرکت دادن هد را بر روی تمامی نوارها به صورت همزمان می‌دهد. باید نشان دهیم که با ماشین تک نواره می‌توانیم ماشین چندنواره را شبیه‌سازی کنیم، برای این کار نشان می‌دهیم که ماشین تک نواره می‌تواند تأثیر چندین نوار را بر روی یک نوار ذخیره‌سازی کند. برای ماشین تک نواره نماد # را تعریف می‌کنیم که به عنوان جداکنندهٔ محتوای نوارهاست. برای این که بدانیم محل هر هد در نوارها کجاست یک نقطه بر روی هر خانه که هد روی آن قرار دارد قرار می‌دهیم؛ و با استفاده از این نمادها اثبات را کامل می‌کنیم. ماشین تورینگ
ماشین تورینگ به ما اجازه می‌دهد دربارهٔ الگوریتم‌هایی که برای همیشه نگه داشته می‌شوند، توصیفاتی ارائه دهیم؛ بدون در نظر گرفتن پیش رفت در معماری محاسبات با ماشین معمولی. محاسبه‌پذیری
تعدادی از مدل‌های محاسباتی بر اساس همزمانی توسعه یافته‌اند، از جمله حافظه دسترسی تصادفی موازی و شبکه پتری. در حال حاضر این مدل‌ها قدرتی فراتر از ماشین تورینگ ندارند. ماشین تورینگ کامل
برهان‌های زیر نشان می‌دهد توابعی که با ماشین‌های همیشه متوقف محاسبه می‌شوند را نمی‌توان به همه توابع محاسبه‌پذیر جزئی تعمیم داد که از این می‌توان اینطور فهمید که جواب سؤال اول منفی می‌باشد. این واقعیت رابطه نزدیکی با الگوریتم حل‌ناپذیر مسئله توقف دارد. در حقیقت، اگر g تابع محاسبه‌پذیر کلی گسترش‌یافته f باشد، آن‌گاه g می‌تواند توسط بعضی از ماشین‌های تورینگ قابل محاسبه باشد. e را شاخص چنین ماشین‌هایی قرار دهید. با استفاده از قضیه بازگشت کلیین، ماشین تورینگ M را بسازید که در آن ورودی صفر ماشینی با شاخص e را شبیه‌سازی می‌کند که بر روی شاخص n_M برای M اجرا می‌شود. (در نتیجه ماشین M می‌تواند شاخص خودش را تولید کند و این همان نقش قضیه بازگشت است) فرض کنید این شبیه‌سازی نهایتاً به یک جواب برگردد. M را تعریف کنید، سپس اگر g(nM) = m آنگاه مقدار بازگشتی M، m+1 می‌شود؛ بنابراین f(nM)، مقدار بازگشتی درستM روی ورودی صفر، با g(nM) برابر نمی‌شود. در نتیجه g، f را گسترش نمی‌دهد. محاسبه‌پذیری
محاسبه‌پذیری توانایی حل یک مسئله به روشی مؤثر است؛ که یک موضوع کلیدی در زمینه نظریه محاسبه پذیری در منطق ریاضی و نظریه محاسبات در علوم کامپیوتر است. محاسبه‌پذیری یک مسئله ارتباط نزدیکی با وجود یک الگوریتم برای حل مسئله دارد. گسترده‌ترین مدل‌های مورد مطالعه از محاسبات توابع تورینگ-محاسبه پذیر، μ-بازگشتی و حساب لامبدا هستند، که تمامی آن‌ها دارای قدرت محاسباتی معادل هستند. از انواع دیگر مطالعه محاسبه پذیری، همچنین: مفاهیم محاسبه‌پذیری ضعیف تر از ماشین‌های تورینگ که در نظریه اتوماتا مطالعه می‌شود و مفاهیم محاسبه‌پذیری قوی تر از ماشین تورینگ که در زمینه hypercomputation مطالعه می‌شود را می‌توان نام برد. نظریه رایانش‌پذیری
یک محاسبه به صورت یک تابع بازگشتی مو است، اگر دنبالهٔ تعریف شدهٔ آن، متغیرهای ورودی و یک دنبالهٔ توابع بازگشتی همراه با ورودی‌ها و خروجی‌های آن مشخص باشند؛ بنابراین اگر در تعریف دنبالهٔ بازگشتی تابع formula_1، توابع formula_2 و formula_3 وجود داشته باشند، در نتیجه عباراتی به شکل g(۵)=۷ یا h(۳٬۲)=۱۰ ممکن است ظاهر شوند. در این گونه توابع، اگر آخرین عبارت مقدار تابع بازگشتی ایی که به ورودی‌ها داده شده‌است؛ را بدهد، محاسبات پایان می‌پذیرند. ؛ الگوریتم مارکف یک سیستم رشته‌ای با قابلیت دوباره نویسی، که از قوانین گرامری شکلی برای به کار انداختن رشته‌ها استفاده می‌کند. یک کامپیوتر ایده‌آل تئوریک است! متغیرهای بیشتری وجود دارد. در بسیاری از آن‌ها، هر رجیستر می‌تواند یک عدد طبیعی با سایز نامحدود، را نگهداری کند، دستور العمل‌ها ساده هستند؛ برای مثال فقط کاستن پله‌ای و نمو وجود دارد. کمبود ذخیرهٔ خارجی که در ماشین‌های تورینگ دیده می‌شود، می‌تواند با جایگذاری نقشش با استفاده از روش‌های عددی Godel درک شود. این حقیقت که هر رجیستر قابلیت نگهداری یک عدد طبیعی را دارد، امکان نمایش یک چیز پیچیده‌تر (مثلاً یک دنباله یا یک ماتریس)، را فراهم می‌سازد. همانند ماشین‌های تورینگ، این روش نیز از نشان‌های بی‌نهایت (بدون دسترسی تصادفی) استفاده می‌کند. هم چنین تعداد دستورالعمل‌ها کمتر است. اما این دستورالعل‌ها بسیار متفاوت هستند، بنابراین بر خلاف ماشین تورینگ، P" نیازی به نگه داشتن یک حالت مشخص نیست، چرا که تمام عملیات حافظه گونه فقط با استفاده از نوار تأمین می‌شود. به جای دوباره‌نویسی نشان جاری، می‌تواند یک نمو حسابی پیمانه‌ای را انجام دهد.http://en.wikipedia.org/wiki/Theory_of_computation آلن تورینگ
به دلیل انتشار اثبات او پس از اثبات معادل آلونزو چرچ در جبر لاندا، کار او قابل درک و پذیرفتنی است. همچنین مفهوم «ماشین جامع (تورینگ)» و این ایده که چنین ماشینی می‌تواند کار هر ماشین دیگر را انجام دهد، کاملاً بدیع است. این مقاله همچنین اعداد تعریف‌پذیر را نیز معرفی می‌کند. ماشین اوراکل
ماشین اوراکل را می‌توان یک ماشین تورینگ متصّل به یک اوراکل تصوّر کرد. اوراکل، در این مبحث، موجودیّتی قادر به حل یک سری مسائل است، که به عنوان مثال می‌تواند مسئلۀ تصمیم یا مسئلۀ تابع باشد. مسئله ممکن است محاسبه‌پذیر نباشد؛ اوراکل یک ماشین تورینگ یا برنامۀ کامپیوتری تلقّی نمی‌شود. اوراکل به طورِ ساده یک «جعبۀ سیاه» است که قادر به تولید پاسخی برای هر نمونه از یک مسئلۀ محاسباتی است: محاسبه‌پذیری
تصور کنید یک ماشین که در آن هر مرحله از محاسبات نیاز به نیمی از زمان مرحله قبل را دارد. اگر ما به ۱ واحد زمان برای مرحله اول نیاز داشته باشیم، انگاه زمان مورد نیاز برای اجرای ماشین به صورت: ... +۱+۱/۲+۱/۴ است. این سری همگرا به ۲ واحد زمان است، که به این معنی است که این ماشین تورینگ می‌تواند بی‌نهایت بار در ۲ واحد زمان اجرا شود. این ماشین می‌تواند مشکل تصمیم‌گیری توقف را به‌طور مستقیم با شبیه‌سازی سؤال به صورت بالا حل کند؛ که می‌توان ان را به کار با هر سری همگرا گسترش داد. اگر فرض کنیم این سری همگرا به یک مقدار n است آنگاه ماشین تورینگ عملیات نامتناهی را در n واحد زمان انجام می‌دهد. ماشین اوراکل
در نظریۀ پیچیدگی و نظریۀ محاسبه‌پذیری، ماشین اوراکل (یا ماشین سروش) یک ماشین انتزاعی برای مطالعۀ مسائل تصمیم است. می‌توان آن‌را به عنوان ماشین تورینگ همراه با یک جعبۀ سیاه ، که به آن اوراکل گفته می‌شود، در نظر گرفت که قادر به تصمیم‌گیریِ مسائل تصمیم خاصّی در یک تک‌اقدام است. مسئله می‌تواند از هر ردۀ پیچیدگی باشد. حتّی مسائل تصمیم‌ناپذیر، مثلِ مسئلۀ توقّف، می‌توانند استفاده شوند. تز چرچ-تورینگ
تز چرچ-تورینگ را آلونزو چرچ در سال ۱۹۳۶ میلادی پیشنهاد نموده‌است. این تز بیان می‌دارد که هر محاسبهٔ مؤثر صورت‌یافته، در هر سیستم الگوریتمی را می‌توانیم با استفاده از یک ماشین تورینگ به انجام برسانیم. چنانچه بخواهیم این تز بسیار اساسی در تئوری محاسبات را تنها به‌عنوان تعریفی از محاسبات الگوریتمی به حساب بیاوریم، آن‌را فقط از منظری فوق‌العاده محدود ملاحظه کرده‌ایم. ماشین تورینگ غیرقطعی
ماشین تورینگ غیرقطعی به‌طور رسمی یک ۶-تایی formula_1 است به طوریکه: تز چرچ-تورینگ
سخرانی روزر در سال ۱۹۳۶ در مورد مفهوم "شمارش پذیری مؤثر" بدین صورت بود که: واضح است که وجود CC و RC (اثبات " چرج و روزر") مستلزم تعریف دقیق از " مؤثر بودن " است.روش مؤثر بودن در اینجا در مفهوم نسبتاً خاصی از یک روش که در آن هر مرحله دقیقاً از پیش تعیین شده و مسلم است به تولید پاسخ در تعداد متناهی مرحله، استفاده می‌شود. بنابراین صفت و قید "مؤثر بودن "در اینجا به یک معنا است و آن," گرفتن یک تصمیم مطمئن یا اثر مطمئن است " و " توانایی رسیدن به نتیجه ". همچنین در ادامه کلمه شمارش پذیری مؤثر به معنای " به هر طریقی به طور مستقیم مؤثر تولید کردن " و محاسبه پذیری مؤثر به معنای " توسط ماشین تورینگ یا هر ماشین مکانیکی معادل تولید شدن " است. تعریف "تورینگ" در پاورقی رساله دکتری خود به نام " سیستم‌های منطقی برحسب ترتیب" که زیر نظر چرچ در سال ۱۹۳۹تهیه کرده بود، تقریباًَ یکسان اند. "ما باید از عبارت "توابع قابل محاسبه" به منظور تابعی که با ماشین محاسبه شده است استفاده کنیم، و عبارت "شمارش پذیر مؤثر" را برای اشاره به ایده‌هایحسی که با توجه به این تعاریف هیچ هویتی ندارند، استفاده کنیم." همچین در این پایان‌نامه عبارت زیر وجود دارد که: ""تمام توابع شمارش پذیر مؤثر همان توابع قابل محاسبه‌اند."" ماشین تورینگ متناوب
ماشین تورینگ متناوب با مرتبهٔ زمانی چند جمله‌ای و K تناوب، با شروع از یک حالت وجودی (عمومی) می‌تواند تمام مسائل کلاس formula_36(formula_37) را بررسی کند. از این کلاس‌ها اغلب به صورتformula_38(formula_39) در مسائل یاد می‌شود. ماشین پست-تورینگ
ماشین پُست-تورینگ (به انگلیسی: Post-Touring Machine) نام رده‌ای خاص از توصیف برنامه‌های محاسباتی است که بر اساس نسخه‌ای ساده از ماشین تورینگ تعریف می‌شود. این نسخهٔ ماشین تورینگ با الهام از مدل ریاضی و ماشین ارائه شده توسط امیل پُست (به انگلیسی: Emel Post) برای محاسبات ساخته و توصیف می‌شود. تز چرچ-تورینگ
در نظریهٔ محاسبات، تز چرچ-تورینگ (Church–Turing thesis) پیرامون مفهوم یک روش مؤثر یا مکانیکی در منطق و ریاضیات شکل یافته‌است. در اویل قرن ۲۰ تلاش‌های فراوانی برای فرمول سازی محاسبات انجام شد. ماشین تورینگ
۱. هرچیزی که ماشین واقعی می‌تواند محاسبه کند، ماشین تورینگ هم می‌تواند. برای مثال ماشین تورینگ، می‌تواند هرچیز طبق روالی که در زبان‌های برنامه‌نویسی پیدا می‌شود شبیه‌سازی کند. همچنین می‌تواند فرایندهای بازگشتی و هریک از پارامترهای مکانیسم شناخته شده را شبیه‌سازی کند. ماشین خواندنی تورینگ
با ۲ حافظهٔ پشته‌ای نامتناهی، ماشین معادل با یک تورینگ ماشین است و می‌تواند هر زبان صوری بازگشتی را تجزیه و تحلیل کند. آزمون تورینگ
آزمایش تورینگ ، با نام اصلی بازی تقلید، توسط آلن تورینگ و در سال ۱۹۵۰ معرفی شد، این آزمایش دربارهٔ توانایی یک ماشین برای ارائه رفتارهای هوشمندانه برابر یا غیرقابل تمایز از رفتارهای یک انسان است. تورینگ پیشنهاد کرد که یک ارزیابی کننده انسانی گفتگوی زبان طبیعی بین یک انسان و یک ماشین که قصد تولید پاسخ‌های شبه انسانی دارد، را قضاوت نماید. ارزیابی کننده فقط از این موضوع اطلاع دارد که یکی از دو شریک در گفتگو یک ماشین است و همه مشارکت کننده‌ها از یکدیگر تفکیک شده‌اند. این گفتگو فقط به کانال متنی محدود است، مثل یک کیبرد و نمایشگر رایانه‌ای، از این رو نتایج به توانایی ماشین برای ارائه کلمات به صورت گفتار بستگی ندارد. در اینجا اگر ارزیابی کننده نتواند ماشین را از انسان تشخیص دهد، گفته می‌شود که ماشین آزمایش را پشت سر گذاشته‌است (پاس کرده‌است). نتایج این آزمایش به توانایی ماشین برای تحویل جواب‌های صحیح به سوالات بستگی ندارد، یعنی فقط به این بستگی دارد که چقدر جواب‌ها با جواب‌هایی که یک انسان می‌دهد شباهت دارد و نزدیک است. کامل بودن تورینگ
زبان‌های محاسباتی زیادی وجود دارند که تورینگ کامل نمی‌باشند. یک چنین نمونه‌ای، مجموعه‌ای از زبان‌های قانونی می‌باشد که با دستگاه‌های خودکار متناهی تولید می‌شوند. یک الحاق قدرتمندتر ولی غیرتورینگ کامل از دستگاه‌های خودکار متناهی، گروهی از ماشین‌های خودکار و گرامرهای بدون متن می‌باشد که برای ایجاد درخت‌های پویشی در مرحله ابتدایی برنامه استفاده می‌شوند. نمونه‌های بیشتر شامل برخی از نسخه‌های ابتدایی زبان‌های سایه زنی پیکسل جاسازی شده در Direct3D و OpenGL می‌باشند. در زبان‌های برنامه‌نویسی تابعی کلی، تمام توابع، کلی می‌باشند و باید پایان یابند نظیر Charity, Epigram. Charity، از یک سیستم نوعی و ساختارهای کنترلی مبتنی بر تئوری گروهی استفاده می‌کند درحالیکه Epigram از نوع‌های وابسته استفاده می‌کند. زبان LOOP طراحی می‌شود بنابراین تنها توابعی را محاسبه نماید که بازگشتی ضروری می‌باشند. تمام اینها، زیرمجموعه‌های مناسب از توابع قابل محاسبه را محاسبه می‌کنند زیرا مجموعه کاملی از توابع قابل محاسبه، شمارش پذیر نمی‌باشند. ماشین تورینگ جهانی
تعداد دیگری از مفسران (بخصوص پِنسور در سال ۱۹۸۹) نمونه‌های دیگری از روش‌های رمزگذاری دستورهای را در ماشین محاسباتی تورینگ ارائه دادند. بیشتر مفسران نیز مانند پِنسور فقط از نمادهای باینری (صفر و یک) یا (جای خالی و علامت ا) استفاده می‌کنند. پِنسور فراتر می‌رود و سیستم رمزگذاری مخصوص به خود را می‌نویسد. وی ادعا می‌کند که این علائم سیستم رمزگذاری واقعی و درست هستند، عدد بزرگی که به اندازه ۲ صفحه ۱ و ۰ (صفر و یک) است. محاسبه‌پذیری
تقریباً شبیه به ماشین با وضعیت‌های متناهی است، با این تفاوت که ورودی در "نوار" اجرایی داده می‌شود که ماشین تورینگ می‌تواند از روی ان بخواند، روی ان بنویسد، یا توسط "head" خود به جلو و عقب حرکت کند. نوار می‌تواند به اندازه دلخواه رشد کند. ماشین تورینگ توانایی انجام محاسبات پیچیده که ممکن است مدت زمان اجرای نامعلوم داشته باشد، را دارد. این مدل است که احتمالاً مهم‌ترین مدل محاسبه در علوم کامپیوتر است، چرا که محاسبه‌پذیری را در غیاب محدودیت منابع از پیش تعریف شده شبیه‌سازی می‌کند. ماشین تورینگ کوانتومی
Iriyama، Ohya و Volovich مدل دیگری از ماشین تورینگ کوانتومی را تحت عنوان ماشین تورینگ کوانتومی خطی (LQTM) ارائه دادند. این نوع ماشین تورینگ حالتی کلی از ماشین‌های تورینگ کوانتومی کلاسیک هستند که توابع انتقال غیرقابل برگشت را مدل می‌کنند. این مسئله باعث می‌شود که بتوان اندازه‌گیری‌های کوانتومی را بدون نتیجه خروجی کلاسیک بیان کرد. ماشین تورینگ چندنواره
ماشین تورینگ چند نواره مانند ماشین تورینگ‌های معمول است که به جای یک نوار چندین نوار دارد .هر نوار کلاهک مخصوص به خود را، برای عمل خواندن و نوشتن، دارد .در ابتدا، رشتهٔ ورودی بر روی نوار اول نمایش داده می‌شود و بقیه نوارها خالی‌ هستند . محاسبه‌پذیری
ماشین تورینگ می‌تواند هر زبان مستقل از متن را پذیرش کند به علاوه می‌تواند زبان‌هایی که توسط ماشین پشته‌ای قطعی قابل تصمیم‌گیری نیستند، مانند زبان اعداد اول، را نیز پذیرش کند. این مدل یک مدل به شدت قوی محاسبه‌پذیری می‌باشد. از آنجا که ماشین تورینگ توانایی «بازگشت» در نوار ورودی خود را دارد، برای یک ماشین تورینگ این احتمال وجود دارد که برای مدت زمان طولانی اجرا شود در حالی که این عمل در هیچ‌یک از مدل‌های محاسبه‌پذیری دیگری که قبلاً توضیح دادیم امکان‌پذیر نمی‌باشد. ممکن است که یک ماشین تورینگ ساخته شود که برای برخی از ورودی‌ها هیچ وقت متوقف نشود. می‌گوییم یک ماشین تورینگ یک زبان را می‌پذیرد اگر به ازای تمام رشته‌های ورودی ان زبان ماشین متوقف شود. زبانی که به صورت فوق قابل تصمیم‌گیری است یک زبان بازگشتی نامیده می‌شود. می‌توان ماشین تورینگ‌هایی تعریف کرد که برای هر ورودی در زبان یک جواب تولید کند و سپس متوقف شود، اما ممکن است برای رشته‌های ورودی که در زبان نیستند ماشین متوقف نشود. چنین ماشین‌های تورینگی می‌توانند به ما بگویند که یک رشته داده شده در زبان هست، اما بر اساس رفتار آن ممکن است هرگز نفهمیم که یک رشته داده شده در یک زبان نیست، چرا که در بعضی حالت‌ها ممکن است ماشین هرگز متوقف نشود. زبانی که توسط چنین ماشین تورینگی پذیرش می‌شود زبان شمارش پذیر بازگشتی نامیده می‌شود. ماشین تورینگ، که یک مدل بسیار قدرتمند اتوماتا است. تلاش برای اصلاح تعریف ماشین تورینگ برای تولید یک ماشین قدرتمند تر به طرز شگفت‌آوری با شکست روبرو شده‌است. به عنوان مثال، اضافه کردن تعداد دلخواهی از نوارها به ماشین تورینگ، می‌توان ماشین بدست آمده را توسط یک ماشین تورینگ تک نواره شبیه‌سازی کرد. در نتیجه این مدل قوی تر نیست. در واقع، نتیجهٔ قضیه Church-Turing این است که هیچ مدل منطقی محاسبه‌پذیری که بتواند زبانی را که توسط یک ماشین تورینگ قابل تصمیم‌گیری نیست را پذیرش کند. فیزیک دیجیتال
متعادل‌ترین نسخه از تز چرچ-تورینگ مدعی آن است که هیچ کامپیوتری با توانمندی ماشین تورینگ نمی‌تواند حتی با دادن زمان کافی هر چیزی را که بشر می‌تواند محاسبه کند، به دست آورد. نسخهٔ قوی‌تر ادعا می‌کند که یک ماشین تورینگ جهانی به هیچ وجه نمی‌تواند چیزی را محاسبه کند به این مفهوم که امکان ساختن یک ابررایانه (یک ابر رایانهٔ تورینگ) وجود ندارد. اما مرزها و حدهای محاسبات کاربردی با فیزیک تحمیل می‌شود و نه با علوم رایانهٔ نظری: «تورینگ نشان نداد که ماشین‌های او می‌توانند هر مسئله‌ای را که قابل حل باشد، حل کنند»، با آموزش‌ها، قوانین وضع شدهٔ مشخص، یا پردازش‌ها، همچنین او ثابت نکرد که ماشین تورینگ جهانی «می‌تواند هر تابعی را محاسبه کند که هر کامپیوتر بدون در نظر گرفتن ساختارش بتواند آن را محاسبه کند.» او ثابت کرد که ماشین جامع جهانی‌اش می‌تواند هر تابعی را که توسط ماشین تورینگ قابل محاسبه‌است، محاسبه کند؛ و او یک استدلال فلسفی پیشرفته برای حفظ آن قرار داد. این قضیه، قضیهٔ تورینگ نامیده شد. اما قضیه به حد روش‌های مؤثری بستگی دارد (که می‌توان گفت، بستگی داشتن به حد پردازش‌های یک فرمان معین که بشر توانایی اجرا کردن آن را به‌طور ماشینی دارد) که هیچ دلالتی به بستگی حد پردازش‌هایی که ماشین‌ها توانایی اجرا کردنش را دارند، ندارد؛ حتی ماشین‌هایی که طبق «قوانین وضع شدهٔ مشخص» عمل می‌کنند. در این بین وجود ماشینی با عملکردهای اتمی شاید آن‌هایی باشد که هیچ انسانی به وسیلهٔ ماشین آلات و با کمک هر چیز دیگری نتواند با آن عمل کند. ماشین تورینگ کامل
در عمل، اغلب توابع مربوط به بهره و سود، با ماشین‌های همیشه متوقف محاسبه می‌شوند. می‌توان ماشینی که فقط از حافظه متناهی برای هر ورودی خاص استفاده می‌کند را با محدود کردن روند کنترل، متوقف کرد و به این ترتیب دیگر هیچ داده‌ای باعث نمی‌شود که ماشین در حلقه بی‌نهایت وارد شود. به عنوان یک مثال جزئی می‌توان ماشینی را نام برد که درخت تصمیم‌گیری محدودی را اجرا می‌کند. علی‌رغم تضمین توقف، نیازی نیست که ماشین حتماً فاقد قابلیت‌های حلقه باشد. اگر ما حلقه‌ها را برای رسیدن به اندازه‌ای متناهی و قابل پیش‌بینی محدود کنیم (نه برعکس حلقه FOR در بیسیک)، می‌توانیم اولیه را بیان کنیم. برای نمونه‌ی چنین ماشینی، می‌توان زبان اسباب‌بازی PL-{GOTO} را که توسط Brainerd و Landweber در ۱۹۷۴ معرفی شد، در نظر گرفت. معادل‌های ماشین تورینگ
برای این که نشان دهیم ماشین تورینگ معادل است باید بتوانیم توسط ماشین تورینگ آن را شبیه‌سازی کنیم. ماشین خواندنی تورینگ
در پژوهش‌های مدرن، این مدل برای توصیف رده جدیدی از Quantum finite automata یا probabilistic automata اهمیت پیدا کرده‌است. معادل‌های ماشین تورینگ
از مهم‌ترین معادل‌های ماشین تورینگ ماشین تورینگ غیرقطعی است. در ماشین تورینگ قطعی، مجموعهٔ قوانین به ازای هر وضعیت داده شده، حداکثر یک حرکت را مجاز می‌کند. ماشین تورینگ غیرقطعی برخلاف ماشین تورینگ قطعی، دارای مجموعه قوانینی است که به ازای هر وضعیت، بیشتر از یک حرکت را مجاز می‌کند. برای مثال، ماشین تورینگ غیرقطعی ممکن است هر دو قوانین «اگر در وضعیت ۳ هستید و نماد ‘D’ دیدید، آن را به ‘B’ تغییر دهید و به چپ بروید.» و «اگر در وضعیت ۳ هستید و نماد ‘D’ دیدید، آن را به ‘C’ تغییر دهید و به راست بروید» را در مجموعه قوانینش داشته باشد. برای این که بدانیم این ماشین رشتهٔ ورودی را پذیرش می‌کند یا نه در هر مرحله که چند حرکت ممکن ماشین به چند کپی از خودش تقسیم می‌شود و هرکدام یکی از حرکت‌های ممکن را دنبال می‌کند. اگر حداقل یکی از شاخه‌های درخت به وضعیت پذیرش برود، می‌گوییم ماشین تورینگ غیرقطعی ورودی را پذیرفته‌است. آزمون تورینگ
محققان در بریتانیا تا ده سال پیش از تأسیس رشته تحقیقات هوش مصنوعی در سال ۱۹۵۶ در حال کاوش در «هوش ماشینی»بودند. [15] این موضوع مشترک در میان اعضای باشگاه نسبت بود - یک گروه غیر رسمی از محققان سایبرنتیک و الکترونیک بریتانیا که شامل آلن تورینگ بود. [16] تورینگ، به ویژه، حداقل از سال ۱۹۴۱[۱۷] درگیر فکر مفهوم هوش ماشینی بود و یکی از اولین ذکر های شناخته شده از «هوش کامپیوتری» توسط او در سال ۱۹۴۷ ساخته شد. [۱۸] در گزارش تورینگ، "ماشین آلات هوشمند"،[۱۹] او به بررسی «این سوال که آیا امکان نشان دادن رفتار هوشمندانه برای ماشین آلات وجود دارد یا نه»[۲۰] پرداخت ؛ و به عنوان بخشی از آن تحقیق، آنچه را که ممکن است مقدمه آزمایش های بعدی او محسوب شود، پیشنهاد کرد: ابداع یک ماشین کاغذی که بازی نه چندان بد شطرنج را انجام خواهد داد کار سختی نیست. [21] حال سه مرد الف، ب و ج را به عنوان سوژه برای آزمایش در نظر بگیرید. الف و ج را به جای بازیکنان ضعیف شطرنج در نظر بگیرید، و ب مسئولی است که با ماشین کاغذی کار می کند. ... از دو اتاق با تدارکات مشخصی برای برقراری ارتباط استفاده می شود، و یک بازی بین ج و یا الف یا ماشین کاغذ انجام می شود. ممکن است تعیین این که دارد با الف بازی می¬کند یا با ماشین کاغذی برای ج کاملا دشوار باشد. [22] "ماشین آلات محاسبات و هوش"(۱۹۵۰)اولین مقاله منتشر شده توسط تورینگ بود که در آن منحصراً بر روی هوش ماشینتمرکز کرد. تورینگ مقاله سال ۱۹۵۰ را با این ادعا آغاز می کند، «من پیشنهاد می کنم این سوال را در نظر بگيریم که آیا ماشین ها می توانند فکر کنند؟ ' [5] همانطور که او خاطر نشان کرد، رویکرد سنتی به چنین سوالی این است که با تعاریف هر دو اصطلاح "ماشین" و""هوش" شروع کنیم. تورینگ انتخاب می کند که این کار انجام ندهد؛ در عوض او سوال را با سوال جدیدی جایگزین می کند که «ارتباط نزدیکی با آن دارد و با کلمات نسبتاً بدون ابهام بیان می شود.» [۵] در واقع او پیشنهاد می کند که این سوال را از «آیا ماشین ها می توانند فکر کنند؟» به «آیا ماشین ها می توانند کاری را انجام دهند که ما (به عنوان نهادهای تفکر) می توانیم انجام دهیم؟» [۲۳] تورینگ استدلال می کند که مزیت پرسش جدید، ، این است که «خط نسبتاً دقیقی بین توان های جسمی و فکری یک انسان» ترسیم می کند. [24] برای نشان دادن این رویکرد تورینگ آزمونی را پیشنهاد می کند که از یک بازی مهمانی الهام گرفته شده است که به «بازی تقلیدی» معروف است و در آن یک مرد و یک زن به اتاق های جداگانه ای می روند و مهمانان سعی می کنند با نوشتن یک سری پرسش ها و خواندن پاسخ های تایپی ارسال شده آن ها را از هم تشخیص دهند. در این بازی هم مرد و هم زن هدفش متقاعد کردن مهمانان است که دیگری هستند. (هوما شاه استدلال می کند که این نسخه دو انسانی از بازی توسط تورینگ تنها برای معرفی خواننده به آزمون پرسش و پاسخِ ماشین-انسان ارائه شده است. [25]) تورینگ نسخه جدید خود از این بازی را این طور توصیف کرد: اکنون این سوال را می پرسیم که «وقتی یک ماشین در این بازی به عنوان بخشی از الف عمل کند چه اتفاقی خواهد افتاد؟» آیا بازجو همانند و با همان نرخ به اشتباه تصمیم خواهد گرفت که وقتی بازی این طور انجام می شود در مقابل زمانی که بازی بین یک مرد و یک زن انجام می شود؟ این سوالات جایگزین اصلی ما می شوند، "آیا ماشین ها می توانند فکر کنند؟" [24] بعدها در مقاله تورینگ یک فرمول بندی جایگزین "معادل" را پیشنهاد می کند که شامل یک قاضی است که تنها با یک کامپیوتر و یک انسان طرف است.[۲۶] در حالی که هیچ یک از این فرمول بندی ها دقیقاً با نسخه آزمون تورینگ که امروزه به طور کلی تر شناخته شده است مطابقت ندارد، او یک آزمون سوم را نیز در سال ۱۹۵۲ پیشنهاد کرد. در این نسخه که تورینگ در یک پخش رادیویی بی بی سی به آن پرداخت، یک هیئت منصفه سوالاتی از یک کامپیوتر می پرسد و نقش کامپیوتر این است که بخش قابل توجهی از هیئت منصفه بر این باورند که واقعا ً یک انسان است. [27] مقاله تورینگ ۹ مورد عمده را در نظر گرفت که شامل تمام استدلال های علیه هوش مصنوعی است که در سال های پس از انتشار مقاله مطرح شده است (رجوع کنید به "ماشینآلات محاسباتی و هوش"). [6] در سال ۱۹۶۶ جوزف ویزنبام برنامه ای ایجاد کرد که به نظر می رسید آزمون تورینگ را پشت سر می نهد. این برنامه که با نام ELIZA شناخته می شود با بررسی نظرات تایپ شده یک کاربر برای کلمات کلیدی کار میکرد. اگر یک کلمه کلیدی پیدا شود، قاعده ای که نظرات کاربر را منتقل می دهد جایگزین می شود، و جمله حاصل برمی گردد. اگر کلمه کلیدی یافت نشد، ELIZA یا با یک جواب عمومی یا با تکرار یکی از نظرات قبلی پاسخ می دهد. [28] علاوه بر این ، ویزنبام نسخه دیگری از ELIZA را که برای تقلید رفتار یک روانشناس راجری بود را توسعه داد، که به ELIZA اجازه می دهد آزادانه با فرض دانستن تقریبا هیچ چیز از جهان واقعی عمل کند. [29] با این تکنیک ها ، برنامه ویزنبام قادر بود برخی از مردم را گول گول بزند که آنها در حال صحبت کردن با یک فرد واقعی هستند [29] بنابراین ، برخی ادعا کردند که یکی از برنامه ها (شاید اولی) قادر به پاس شدن آزمون تورینگ هست،[29][30] حتی اگر در این دیدگاه نزاع بسیار باشد (اینجا را نگاه کنید). کنت کولبی در سال ۱۹۷۲ PARRY را ایجاد کرد، برنامه ای که به عنوان "ELIZA¬ی با نگرش" توصیف شد. [31] که تلاشی برای مدل کردن رفتار یک بیمار اسکیزوفرنی پارانویید بود، که از رویکردی مشابه (حتی پیشرفته تر) رویکردی که ویزنبام داشت، استفاده می¬کرد. برای اعتبار بخشیدن به کار، PARRY در اوایل دهه ۱۹۷۰ با استفاده از انواع آزمون های تورینگ مورد آزمایش قرار گرفت. گروهی از روانپزشکان با تجربه ترکیبی از بیماران واقعی و رایانه هایی را که PARRY را اجرا می¬کردند، مورد تجزیه و تحلیل قرار دادند. متن مکالمات را به گروه دیگری شامل ۳۳ روانپزشک نشان دادند. سپس از این دو گروه خواسته شد تا شناسایی کنند که کدام یک از «بیماران» انسان هستند و کدام یک برنامه های کامپیوتری. [۳۲] روانپزشکان توانستند شناسایی صحیح را تنها در ۴۸ درصد از موارد - رقمی سازگار با حدس تصادفی- انجام دهند. [33] در قرن بیست و یکم، نسخه هایی از این برنامه ها (که اکنون با نام"chatterbots"شناخته می شود) همچنان مردم را گولمی زنند. CyberLove که یک برنامه بدافزار است، با متقاعد کردن مردم به «آشکار کردن اطلاعات مربوط به هویت شان یا هدایت آن ها به بازدید از یک وب سایت که محتوای مخرب را به رایانه هایشان تحویل خواهد داد» کاربران را طعمه خود می¬کرد. [34] این برنامه به عنوان "خطرِ ولنتاین" با سر به سر گذاشتن با مردم در جهت برقراری روابط آنلاین، به منظور جمع آوری اطلاعات شخصی آن ها ظهور کرد. [35] مقاله ذهن ، مغز ، و برنامه¬ها ی جان سرل در سال 1980 آزمایش "اتاق چینی" را پیشنهاد کرد و استدلال کرد که آزمون تورینگ نمی تواند مورد استفاده قرار گیرد برای تعیین اینکه آیا یک ماشین می تواند فکر کند یا نه. سرل اشاره کرد که نرم افزارها (مانند ELIZA) می توانند آزمون تورینگ را به سادگی با دستکاری نمادهایی که هیچ درک درستی از آن ها ندارند، بگذرانند. بدون درک ، نمی توان آن ها را «متفکر» به همان معنا انسان ها هستند توصیف کرد. بنابراین سرل نتیجه می گیرد، آزمایش تورینگ نمی تواند ثابت کند که یک ماشین می تواند فکر کند. [36] بسیار شبیه به خود آزمون تورینگ، استدلالی که سرل ارائه داد هم به طور گسترده ای مورد انتقاد قرار گرفت [37] و هم بسیار تایید شده است. [38] استدلال هایی مانند سرل و دیگرانی که بر روی فلسفه ذهن کار می کردند، جرقه ای برای بحث شدیدتر در مورد ماهیت هوش، امکان ماشین های هوشمند و ارزش آزمون تورینگ را روشن کرد که تا سال های ۱۹۸۰ و ۱۹۹۰ ادامه یافت. [39] جایزه لوبنر یک بستر سالانه برای آزمایش های عملی تورینگ فراهم می کند که اولین مسابقه¬ی آن در نوامبر ۱۹۹۱ برگزار شد. [۴۰] توسط هیو لوبنر نوشته شده است. مرکز مطالعات رفتاری کمبریج در ماساچوست ایالات متحده آمریکا جوایز این مسابقه را تا سال ۲۰۰۳ سازماندهی کرد. همان طور که لوبنر آن را توصیف کرد، یکی از دلایل ایجاد این رقابت پیشبرد وضعیت تحقیقات هوش مصنوعی، حداقل تا حدودی است، زیرا با وجود ۴۰ سال بحث در مورد آن، کسی برای اجرای آزمون تورینگ گام برداشته نبود. [41] اولین مسابقه جایزه لوبنر در سال ۱۹۹۱ منجر به بحث مجدد و زنده ماندن آزمون تورینگ و تبئین ارزش پیگیری آن، هم در مطبوعات محبوب[۴۲] و هم در آکادمی شد. [43] در اولین مسابقه توسط یک برنامه بدون-فکر و بدون هوشِ قابل شناسایی که موفق به گول زدن بازجویان ساده لوح به شناساییِ اشتباه، برنده شد. این موضوع چند کاستی از آزمون تورینگ را برجسته کرد(مورد بحث در زیر ):برنامه ی ساده¬ی ارائه شده برنده شد، زیرا حداقل در بخشی از آن، قادر به "تقلید از خطاهای تایپانسان"بود ؛ [42] بازجویان ساده لوح به راحتی گول میخورند. [43] و برخی محققان هوش مصنوعی احساس میکردند که این آزمون صرفا یک حواس پرتی از تحقیقات پربارتر است. [44] جوایز نقره (فقط متن) و طلا (صوتی و بصری) هرگز به کسی داده نشد. با این حال، این رقابت هر سال مدال برنز را برای سیستم کامپیوتری¬ای اعطا کرده است که به نظر قضات، «انسانی ترین» رفتار مکالمه ای را در میان مدخل های آن سال نشان می دهد. نهاد رایانه ای اینترنت زبانی مصنوعی (A.L.I.C.E) در سه نوبت در سال های(۲۰۰۰، ۲۰۰۱، ۲۰۰۴) برنده جایزه برنز شده است. جایزه لوبنر هوش مکالمه ای را آزمایش می کند؛ برندگان به طور معمول برنامه های chatterbot، و یا نهادهای مکالمه نهادهای مکالمه مصنوعی (ACE). هستند. قوانین اولیه جایزه لوبنر مکالمات را محدود می کرد: هر ورودی مسابقه و انسان های پنهان(انسان پنهان) بر روی یک موضوع واحد متمرکز می شدند،[۴۵] به این ترتیب بازجویان به یک خط پرسش در هر تعامل محدود می شدند. قانون مکالمه محدود برای جایزه لوبنر در سال ۱۹۹۵ برداشته شد. مدت تعامل بین قاضی و نهاد در جوایز لوبنر متفاوت بوده است. در لوبنر ۲۰۰۳، در دانشگاه سوری، به هر بازجو پنج دقیقه اجازه داده شد تا با یک نهاد، ماشین یا انسان پنهان تعامل داشته باشد. بین سال های ۲۰۰۴ تا ۲۰۰۷ زمان تعامل مجاز در جوایز لوبنر بیش از بیست دقیقه بود. محاسبه‌پذیری
آرمان نظری جالبی از یک کامپیوتر است. چندین نوع دارد. در بسیاری از آنها، هر ثبت نام می‌تواند تعدادی عدد طبیعی (با اندازه نامحدود) نگه دارد، و دستورالعمل‌ها ساده‌اند (و کم)، به عنوان مثال تنها عمل کاهش (همراه با پرش شرطی) و افزایش (و توقف) وجود دارد. عدم وجود بی‌نهایت (و یا رشد پویا) ذخیرهٔ خارجی (که در ماشین تورینگ وجود دارد) را می‌توان با جایگزینی نقش ان با تکنیک‌های شماره‌گذاری گودل درک کرد:این واقعیت است که هر ثبت نام یک عدد طبیعی دارد که اجازه می‌دهد تا بتواند نمایندهٔ یک شیء پیچیده باشد (به عنوان مثال یک دنباله، یا یک ماتریس) توسط عدد طبیعی بزرگ مناسب - عدم ابهام در هر دو حالت به نمایندگی گرفتن و تفسیر کردن را می‌توان با پایه‌های نظریه اعدادی این تکنیک‌ها ایجاد کرد.