מודלים חישוביים

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

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