یادداشت امیرعلی ابراهیم زاده

        نظریه محاسبات بنیاد و اساس علوم کامپیوتر است، تئوری‌ترین درس کامپیوتر. این فیلد ریاضی-کامپیوتری با این دغدغه آغاز می‌شود که چه نوع کامپیوترهایی و چه مدل‌های محاسباتی‌ای، توان حل چه دسته از مسائلی را دارند. و در این فیلد محدودیت‌ها و توانایی‌های بنیادین کامپیوترها مورد مطالعه و اثبات قرار می‌گیرد، نشان داده می‌شود که برخی مسائل اساسا توسط هیچ کامپیوتری قابل حل نیستند، مستقل از تعداد ترانزیستورها و طراحی کامپیوتری که سعی در حل مسئله دارد. نظریه محاسبات به همین دلیل مهم است و با بسیاری از دیگر از فیلدها ارتباط پیدا می‌کند، مانند منطق، نظریه زبان‌های برنامه‌نویسی، طراحی کامپایلرها، الگوریتم و پیچیدگی محاسباتی و...

کتاب حاضر برای شروع دنیای نظریه محاسبات کتاب خوبی‌ست، گرچه می‌گویند کتاب مارتین هم مناسب و مفصل‌تر است که آن را نخوانده‌ام. سیپسر کتابش را بسیار ساده و خوش‌خوان و قابل فهم نوشته است و ترجمه کتاب نیز روان است، هرچند بعضی جاها به نظر نامناسب است و توضیحاتش ناکافی، در مجموع اما قابل قبول است. نثر انگلیسی کتاب نیز مناسب و ساده است و اگر مشکلی ندارید بهتر است نسخه انگلیسی آن را بخوانید. 

فصل صفرم کتاب شامل مقدمات ریاضی مبحث می‌شود. در فصل اول کتاب به زبان‌های منظم و ماشین‌های حالت متناهی پرداخته شده، فصل دوم شامل گرامرهای مستقل از متن و ماشین پشته‌ای می‌شود. فصل سوم درباره ماشین تورینگ است و فصل چهارم درباره تصمیم‌پذیری و فصل پنجم کاهش‌پذیری و در نهایت مباحث پیشرفته نظریه محاسبات گفته می‌شود. رویکرد کتاب کاملا رویکرد تورینگی و نظریه زبان محور است و کمتر به مدل‌های محاسباتی دیگر مانند حساب لمبدا چرچ و مدل‌های گودل و کلینی و یا نظریه پیچیدگی پرداخته می‌شود. از مزایای کتاب می‌توان به خودخوان بودن آن اشاره کرد، هرچند معمولا تکست‌بوک کلاس‌های معمول نظریه زبان و ماشین نیز همین کتاب سیپسر است و در سیرهای مطالعاتی، سیپسر معمولا گزینه اول است. سیپسر مقدمه‌ای بر دنیای زیبای نظریه محاسبات است، و حیف است که به این فیلد فلسفیِ علوم کامپیوتر پرداخته نشود.