این عقیده وجود دارد که اگر یک مسئله بتواند توسط یک الگوریتم حل شود، ماشین تورینگی وجود دارد که می‌تواند آن را حل کند (آلونزو چرچ[3]، 1952 میلادی). آن چه تا کنون ثابت شده این است که هر مسئله‌ای که بتواند بر روی مدل‌های محاسباتی دیگری که تاکنون برای ما شناخته شده است، همچون ماشین RAM، بازی زندگی[4] کانوِی [5] (1970میلادی)، ماشین خودکار سلولی[6] یا هر زبان برنامه‌نویسی محاسبه شود؛ می‌تواند بر روی ماشین تورینگ نيز محاسبه شود. از آن جایی که تحلیل ریاضی ماشین‌های تورینگ آسان است و به اندازه‌‌ی هر مدل محاسباتی دیگری قدرتمند هستند، این ماشین‌ها رایج‌ترین مدل‌هايی هستند که در نظریه‌ی پیچیدگی مورد استفاده قرار می‌گیرند.

برای تعیین کلاس‌های پیچیدگي، انواع مختلفی از ماشین‌های تورینگ همچون ماشین‌های تورینگ قطعی[7]، ماشین‌های تورینگ احتمالی[8]، ماشین‌های تورینگ غیر قطعی[9]، ماشین‌های تورینگ کوانتومی[10]، ماشین‌های تورینگ متقارن[11] و ماشین‌های تورینگ متناوب[12] به کار می‌روند. به طور کلی همه‌ی آن‌ها به یک اندازه قدرتمند هستند اما زمانی که منابع (مثل زمان و فضا) محدود باشند، برخی از آن‌ها ممکن است قدرتمندتر از بقیه عمل کنند.

یک ماشین تورینگ قطعی ابتدایی‌ترین نوع ماشین تورینگ است که برای تعیین رفتارهای آینده‌اش از مجموعه‌ی ثابتی از قوانین استفاده می‌کند. یک ماشین تورینگ احتمالی یک ماشین تورینگ قطعی با منابع اضافی از بیت‌های تصادفی است. توانایی تصمیم‌گیری‌های احتمالاتی بیشتر اوقات به الگوریتم در حل کارآمد مسئله کمک می‌کند. الگوریتم‌هایی که از بیت‌های تصادفی استفاده می‌کنند، الگوریتم‌های تصادفی[13] نام دارند. یک ماشین تورینگ غیر قطعی یک ماشین تورینگ قطعی است که به آن ویژگی غیر قطعی بودن نیز اضافه شده است؛ در نتیجه، می‌تواند، برای رفتن از یک وضعیت معین، چندین رفتار ممکن پیش روی خود داشته باشد.


[1]. Turing Machine

[2] . Manipulate

[3]. Alonzo Church

[4] . Game of Life

[5]. John Conway (ریاضی‌دان انگلیسی)

[6]. Cellular Automata

[7]. Deterministic Turing Machine

[8] . Probabilistic Turing Machine

[9] . Non-Deterministic Turing Machine

[10] . Quantum Turing Machine

[11] . SymmetricTuring Machine

[12] . AlternativeTuring Machine

[13]. Randomized Algorithm