یک زبان کامل بودن تورینگ زبانی است که می‌تواند هر محاسباتی را انجام دهد. تز چرچ-تورینگ بیان می‌کند که هر نوع محاسبه قابل اجرایی را می‌توان با یک ماشین تورینگ انجام داد. یک ماشین تورینگ ماشینی است با حافظه نامحدود و یک برنامه محدود که مشخص می‌کند که باید چه چیزی را بخواند، بنویسد، چه موقع در حافظه حرکت کند و یا بایستد. ورودی یک ماشین تورینگ قبل از آغاز، در حافظه قرار میگیرد.
ماشین تورینگ بر اساس چیز هایی که در حافظه می‌بیند، تصمیم میگیرد
زبانی که فقط از عملیات + - * / بر روی اعداد صحیح پشتیبانی می‌کند، یک کامل بودن تورینگ به حساب نمی‌آید چون نمی‌تواند بر اساس ورودی تصمیم بگیرد ولی ماشین تورینگ می‌تواند.
ماشین تورینگ می‌تواند تا ابد اجرا شود
زبان های برنامه‌نوسی مثل جاوا، جاوا اسکریپت یا پایتون را در نظر بگیرید. اگر هر نوع قابلیت حلقه، GOTO یا تابع را از آنها بگیریم، دیگر یک زبان کامل بودن تورینگ به حساب نمی‌آیند چون نمی‌توانند یک محاسبه را که تا ابد طول می‌کشد انجام دهند.
ماشین تورینگ حافظه دارد
زبانی که شما را محدود به استفاده از حافظه فقط از طریق Pop و Push می‌کند، یک کامل بودن تورینگ به حساب نمی‌آید. اگر زبانی داشته باشیم که که فقط می‌تواند یک بار یک رشته را بخواند و از حافظه فقط از طریق Push و Pop استفاده کند، می‌تواند هر وقت که ) در رشته دید Push کند و هر وقت ( را دید، Pop کند. اما نمی‌تواند بگوید که آیا هر )، ( مخصوص به خود و هر [، ] مخصوص به خود را در طول رشته دارد. اما ماشین تورینگ این قابلیت را دارد که از حافظه خود استفاده کند و () را جدا و [] ها را جدا بررسی کند. زبان های پشته ای این قابلیت را ندارند.
ماشین تورینگ می‌تواند از حافظه نامحدود استفاده کند
اگر یک زبان مثل جاوا وقتی 4 گیگابایت از حافظه را استفاده می‌کرد، متوقف میشد، نمی‌توانستیم آن را یک زبان کامل بودن تورینگ در نظر بگیریم چون یک ماشین تورینگ می‌تواند از حافظه نامحدود استفاده کند. بخاطر همین هست که واقعا نمی‌توانیم یک ماشین تورینگ بسازیم اما جاوا را یک ماشین تورینگ حساب می‌کنیم چون جاوا محدودیتی در استفاده از حافظه ندارد. یکی از دلایلی که زبان های منظم در دسته ماشین های تورینگ قرار نمی‌گیرند همین است.
ماشین تورینگ می‌تواند هر ماشین تورینگ دیگری را شبیه سازی کند
اگر به یک ماشین تورینگ یک برنامه مناسب بدهیم، می‌تواند برنامه یک ماشین تورینگ دیگر را شبیه سازی کند. اگر زبانی وجود داشت که اجازه استفاده از مفصر پایتون را نمی‌داد، آن زبان یک ماشین کامل بودن تورینگ به حساب نمی‌آید.
نمونه هایی از ماشین کامل بودن تورینگ
اگر زبانی دارای حافظه نامحدود، دستورات شرطی و حلقه ای داشته باشد، احتمالا یک ماشین کامل بودن تورینگ محسوب می‌شود. از نمونه های ماشین کامل بودن تورینگ به می‌توان به C، C++، Python، Java اشاره کرد.
آزمون تورینگ آزمایشی است که نشان می‌دهد آیا یک کامپیوتر می‌تواند مانند یک انسان فکر کند یا نه. آلن تورینگ مطرح کرده است در صورتی می‌توان به کامپیوتر گفت هوش مصنوعی دارد که بتواند تحت شرایط خاص از رفتار انسان تقلید کند.
آزمون اصلی شامل سه قسمت است که هر کدام بطور فیزیکی از هم جدا شده اند. یکی از این قسمت ها کامپیوتر و دو قسمت دیگر انسان هستند. در طول آزمون یکی از انسان ها سوال می‌پرسد، انسان دوم و کامپیوتر جواب سوال را می‌دهند. سوال کننده، جواب دریافتی را در زمینه های مختلف بررسی می‌کند، بعد از گذشت زمان و پرسیدن سوال های متعدد، سوال کننده تعیین می‌کند که کدام یک از پاسخ دهنده ها انسان و کدام کامپیوتر بود.
آزمون چند بار تکرار می‌شود. اگر پرسشگر در نصف یا کمتر تعداد تکرار ها بتواند درست تشخیص بدهد، کامپیوتر را دارای هوش مصنوعی می‌دانند.
تورینگ این آزمون را در مقاله خود با نام محاسبات و هوش ماشینی زمانی که در دانشگاه منچستر درس می‌خواند منتشر کرد. در این مقاله تورینگ عبارت بازی تقلید را مطرح کرد. هوش مصنوعی در بازی تقلید حضور نداشت. بازی تقلید شامل سه انسان در سه اتاق بود. هر اتاق یک تلویزیون و کیبورد دارد و یک اتاق مرد، یک اتاق زن و یک اتاق یک قاضی مرد یا زن دارد. شرکت کننده زن تلاش می‌کند تا قاضی را متقاعد کند که مرد است و قاضی باید تشخیص دهد که حقیقت است یا نه.
تورینگ این آزمون را تغییر داد و هوش مصنوعی را در آن جا داد. حالا آزمون شامل یک پرسشگر انسان، یک شرکت کننده انسان و یک هوش مصنوعی بود.
در طول سالیان، آزمون تورینگ انتقاد های زیادی داشته است. مثلا برای سالها اگر از کامپیوتر ها سوال های با جواب بله/خیر می‌پرسیدید، امتیاز بالایی در آزمون دریافت می‌کرد اما اگر سوالاتی می‌پرسیدید که احتیاج به جواب تشریحی داشت، عملکرد خوبی از کامپیوتر دریافت نمی‌کردید. یا برنامه ای مثل ELIZA می‌توانست به راحتی با دستکاری نماد ها آزمون را با موفقیت پشت سر بگذارد.
انواع مختلفی از آزمون تورینگ را معرفی کرده‌اند که در زیر تعدادی را می‌خوانیم:
آزمون تورینگ معکوس: در این آزمون یک انسان سعی می‌کند به کامپیوتر بفهماند که یک کامپیوتر نیست. مثل CAPTCHA
آزمون تورینگ کامل: در این آزمون پرسشگر می‌تواند توانایی های ادراکی و همچنین توانایی دستکاری اشیاء را هم مورد آزمون قرار دهد.
آزمون حداقل هوش سیگنالی: در این آزمون فقط سوال های با جواب درست/غلط یا بله/خیر پرسیده می‌شوند.
بسیاری از محققین آزمون تورینگ را مشکل دار میدانستند در نتیجه آزمون های دیگری را به جای آزمون تورینگ ارائه دادند.
آزمون مارکوس: در این آزمون کامپیوتر یک برنامه تلویزیونی را نگاه می‌کند و سپس از آن سوال هایی درباره برنامه ای که دیده می‌پرسند.
آزمون Lovelace: در این آزمون کامپیوتر باید یک اثر هنری بسازد.
آزمون Winograd Schema: در این آزمون کامپیوتر باید به سوال های چند گزینه ای پاسخ دهد.
