Teoria obliczeń

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić.

Rozważania tego typu nie są możliwe bez formalnego, matematycznego modelu komputera. Najczęściej 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).

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).

Zobacz też[edytuj | edytuj kod]