חישוביות – הבדלי גרסאות

תורת החישוביות החלה להתפתח בתחילת [[המאה העשרים]], במחקרים [[מתמטיקה|מתמטיים]] שעסקו בשאלה איזה בעיות מתמטיות ניתנות לפתרון בדרכים פשוטות. ראשית היה צריך לקבוע מהי "דרך פשוטה", ולשם כך היה צורך במודל של חישוב. אחד המודלים הראשונים שנוצרו הוא [[מכונת טיורינג]], שנקראת על שם ממציאה [[אלן טיורינג]], אשר מהווה אבן דרך בתורת החישוביות כולה, בשל פשטותו ודמיונו ל[[מחשב]] (שטרם הומצא בעת יצירת מודל זה). מודל אחר הוא זה של [[תחשיב למדא]]. הוכח ששני מודלים אלה, ומודלים רבים נוספים אחרים שהוצעו (כגון [[דקדוק בלתי מוגבל|דקדוקים בלתי מוגבלים]]), שקולים זה לזה בכוחם החישובי - חישוב שניתן לבצע באחד מהמודלים ניתן לבצע גם באחרים. מודלים אלה שקולים גם ל[[מחשב]], אם נניח קיומו של [[זיכרון מחשב|זיכרון]] בלתי מוגבל בגודלו. [[תזת צ'רץ'-טיורינג]] משערת שכל פורמליזציה סבירה של מושג ה[[אלגוריתם]] תהיה שקולה למכונת טיורינג.