هدف از این درس ارائه‌ی دقیق انواع مدل‌های ریاضی ارایه‌شده در تعریف مفهوم محاسبه و محاسبه‌پذیری و نتایج حاصل از آن‌ها با فرض تسلط دانشجویان بر نظریه‌ی زبان‌ها و ماشین‌ها و نظریه‌ی محاسبات مقدماتی است.

1. مروری بر نظریه‌ی ماشین‌های تورینگ، ماشین‌های تورینگ چندنواری و غیرقطعی، تز تورینگ-چرچ، مسایل و زبان‌های بازگشتی و به‌طور بازگشتی شمارا. مروری بر مسایل تصمیم ناپذیر، مساله‌ی توقف و انواع آن، قضیه‌ی رایس. مروری بر کلاس‌های پیچیدگی الگوریتم‌ها.
2. ماشین‌های تورینگ تناوبی (Alternating TM) و ماشین‌های تورینگ پیشگو (Oracle TM) و قضایای مربوط به آن‌ها.
3. نظریه‌ی توابع بازگشتی و تز چرچ. حساب لامبدا و قضایای تمامیت آن، توابع بازگشتی جزیی و عددگذاری گدلی.
4. خودارجاعی (Self-Reference)، قضیه Knaster-Tarski و به‌کارگیری آن در نظریه‌ی خودکارها و منطق‌های نقطه‌ی ثابت، مفاهیم منطقی اثبات (Provability Logic).
5. مقدمه‌ای بر نظری آتوماتای متناهی بر رشته‌های نامتناهی، منطق مرتبه‌ی دوم Monadic و نتایج بوخی و رابین در ارتباط آتوماتای بر رشته‌های نامتناهی با منطق‌های مرتبه‌ی دوم.
6. قضیه‌ی تناظر Post و سیستم‌های Post.
7. سیستم‌های محاسباتی منصف (Fair Systems) و قضیه Harel. انواع تعاریف انصاف و قضایای مرتبط.
8. قضیه‌ی کلینی (Kleene Theorem) و نتایج آن، مروری بر انواع جبرهای کلینی (Kleene Algebras).
9. مروری بر نظریه‌ی انواع چرچ (Church's Type Theory) و نظریه‌ی انواع ساختی مارتین-لاف (Lof's Constructive Type Theory).

• تمرین: شش سری تمرین مسئله مدار و پژوهش مدار (۲۰٪ کل نمره)
• پروژه پژوهشی: شامل گزارش پژوهشی و سمینار (۲۰٪ کل نمره)
• آزمون: آزمون‌های میان‌ترم و پایان‌ترم (۶۰٪ کل نمره)