Izračunljiva funkcija

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Funkcija f : \mathbb{N}^k \to \mathbb{N} je izračunljiva, če obstaja Turingov stroj, ki jo računa. V praksi to pomeni, da lahko sestavimo program ali podamo algoritem, ki računa vrednosti funkcije. Definicijsko območje določajo argumenti, pri katerih se Turingov stroj ustavi. Če je funkcija f delna, pravimo, da je izračunljiva delna funkcija. Če želimo poudariti, da je izračunljiva funkcija povsod definirana, ji rečemo popolnoma izračunljiva.

Osebna orodja