Teoria obliczeń dzieli się na trzy główne części: teorię automatów, teorię obliczalności oraz teorię złożoności. Teoria automatów zajmuje się definicjami i własnościami modeli obliczeń, matematycznymi modelami maszyn liczących. W uproszczeniu zajmuje się ona odpowiedzią na pytanie czym jest komputer, teoria obliczalności zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a teoria złożoności – odpowiedzią na pytanie jak szybko da się to zrobić. Przykładowymi zagadnieniami są Maszyna Turinga czy Hipoteza Churcha-Turinga. Języki formalne stanowią podstawę badań nad językami komputerowymi, jak i naturalnymi w lingwistyce. Systemy formalne są tworzone i badane zarówno jako samodzielne abstrakcyjne twory, jak i systemy opisu rzeczywistości. 130px 96px 120px 96px Teoria automatów Język formalny Teoria obliczalności Teoria złożoności obliczeniowej Automat komórkowy

Teoria informacji i kodowania