Teoria obliczeń

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Artystyczna reprezentacja Maszyny Turinga, jednego z modeli obliczeń.

Teoria obliczeń – dział informatyki teoretycznej i matematyki stosowanej. Dzieli się on na trzy główne części: teorię automatów i języków formalnych, teorię obliczalności oraz teorię złożności. Teoria automatów zajmuje definicjami i własnościami modeli obliczeń. W uproszczeniu zajmuje się ona odpowiedzią na pytanie czym jest komputer, teoria obliczalności odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a teoria złożoności – odpowiedzą na pytanie jak szybko da się to zrobić[1].

Modele obliczeń odgrywają ważną rolę także w wielu stosowanych obszarach - przykładowo jeden z tych modeli nazywany automatem skończonym jest wykorzystywany w architekturze komputerów, budowie kompilatorów, czy przetwarzaniu tekstu (przetwarzanie języka naturalnego, synteza mowy). Inny model nazywany gramatyką bezkontekstową, jest używany przy projektowaniu jezyków programowania i sztucznej inteligencji[1].

Kolejnym często używanym modelem jest maszyna Turinga. Taką maszynę można w uproszczeniu rozumieć jako komputer o nieograniczonych zasobach pamięci. Inne używane modele, takie jak: rachunek lambda, rachunek kombinatorów, algorytmy Markowa, funkcje rekurencyjne są sobie równoważne w tym sensie, że wszystko co jest obliczalne na jednym z nich, da się też obliczyć na maszynie Turinga. Rozważa się również węższe modele tzn. takie, które nie pozwalają na wyrażenie dowolnej funkcji obliczalnej, np. funkcje pierwotnie rekurencyjne. O niektórych problemach związanych z modelami obliczeń wiadomo, że są nierozstrzygalne. Na przykład nie istnieje algorytm, który rozstrzyga czy dwa λ-wyrażenia są równoważne lub czy maszyna Turinga dla danego wejścia się zatrzyma (zob. problem stopu). Podstawowym obiektem badań teorii obliczalności są funkcje obliczalne.

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. a b Michael Sipser, Wprowadzenie do teorii obliczeń.