תורת החישוביות

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

ספר זה מבוסס על הקורס המתאים בטכניון, אך אינו נאמן למקור ומכיל נושאים נוספים (וכן משמיט מספר נושאים מתקדמים).

תוכן עניינים

מבוא מכונת טיורינג שקילות מודלי חישוב מכונת טיורינג אוניברסלית מודל לבעיות הכרעה כריעות שפות קיום שפות שאינן כריעות רדוקציה חישובית משפט רייס אי-הפרדתיות רקורסיבית משפט הרקורסיה סיבוכיות קולמוגורוב יישומי אי-דחיסות הסתברות אוניברסאלית בעיות זיהוי ובעיות חיפוש

לקריאה נוספת

• Michael Sipser, "Introduction to the Theory of Computation", (2nd Ed.) 2006, ISBN 0-534-95097-3
• John Hopcroft, Rajeev Motwani, Jeffrey Ullman, "Introduction to Automata Theory, Languages, and Computation", 2nd Edition, 2000, ISBN 0-201-44124-1
• Christos H. Papadimitriou, "Computational Complexity", 1994, ISBN 0-201-53082-1

• עודד גולדרייך, "מבוא לתורת החישוביות"