Carnegie Mellon Üniversitesi'ndeki CS251 dersi, evrenimizin, toplumlarımızın, yeni teknolojilerin ve hatta zihinlerimizin temel bir bileşeni olan hesaplamanın titizlikle incelenmesine odaklanır. Ders, hesaplamayı anlamak için doğru dil ve araçlara sahip olmanın önemini vurgulayarak, hesaplamanın doğasıyla ilgili merkezi sonuçları ve soruları keşfetmeyi amaçlar. İlk bölümde, hesaplama ve algoritmalarla ilgili önemli kavramlar matematiksel ve biçimsel bir temelde inşa edilir; bu süreç, verilerin nasıl resmi olarak temsil edileceği ve bir hesaplama probleminin nasıl tanımlanacağı ile başlar.
Ders, hesaplama modellerini kademeli olarak tanıtır. İlk olarak, basit ancak önemli bir hesaplama modeli olan Deterministik Sonlu Otomata (DFA) ele alınır. DFA'lar, kendi başlarına ilgi çekici uygulamalara sahip olsalar da, asıl amaç, algoritmaların tam genelliğiyle resmi tanımına giden bir basamak görevi görmeleridir. Bu model aracılığıyla öğrenciler, bir hesaplama modelinin nasıl resmi olarak tanımlandığına ve bu modellerle ilgili teoremlerin nasıl kanıtlandığına aşina olurlar, aynı zamanda daha sofistike matematiksel gösterimlerle rahat etmeye başlarlar.
Daha sonra, herhangi bir hesaplama cihazı için standart matematiksel model olan Turing makinesi tanıtılır. Bu tanım son derece temeldir ve fiziksel Church-Turing tezi, herhangi bir fiziksel cihazın veya fenomenin, bir Turing makinesi tarafından simüle edilebileceğini iddia eder. Turing makinelerini incelemek, sadece bilgisayarlarımızın ne yapıp ne yapamayacağı hakkında değil, aynı zamanda evrenin hesaplama açısından ne yapıp ne yapamayacağı hakkında da içgörüler sunar. Ders, hesaplanabilir problemlerin örnekleriyle başlar ve ardından çoğu problemin çözülemez olduğunu kanıtlamak için diyagonalizasyon ve indirgeme gibi temel teknikleri kullanarak hesaplamanın sınırlamalarını keşfeder.
Teorik bilgisayar bilimi, hesaplamanın temel doğasını ve sınırlarını anlayarak modern teknolojiden evrenin işleyişine kadar geniş bir yelpazede derin içgörüler sunar.