funkcja obliczalna

funkcja obliczalna,

mat. funkcja o argumentach i wartościach w zbiorze liczb naturalnych (lub w zbiorze tekstów), dla której można podać algorytm znajdujący wartość funkcji na podstawie danego argumentu;

w ścisłym sensie, intuicyjne pojęcie algorytmu zastępuje się modelem mat., np. maszyną Turinga (Churcha–Turinga teza); teoretycznie każdy problem obliczeniowy opisany przez f.o. można rozwiązać za pomocą komputera, jednak w praktyce barierą nie do przekroczenia może być złożoność obliczeniowa algorytmu; z drugiej strony, nie każde zagadnienie mat. można sprowadzić do f.o.; np. nie istnieje f.o., która dla dowolnego równania arytmetycznego znajduje jego (pewne) rozwiązanie w liczbach naturalnych lub daje odpowiedź „nie ma”, jeśli rozwiązanie nie istnieje.