Hipoteza Churcha-Turinga

Hipoteza Churcha-Turinga (zwana również Tezą Churcha-Turinga) jest hipotezą określającą możliwości komputerów i innych maszyn obliczeniowych. Mówi ona, że każdy problem, dla którego przy nieograniczonej pamięci oraz zasobach istnieje efektywny algorytm jego rozwiązywania, da się rozwiązać na maszynie Turinga. Hipoteza jest niemożliwa do sprawdzenia matematycznie, ponieważ łączy w sobie zarówno ścisłe, jak i nieprecyzyjne sformułowania, których interpretacja może zależeć od konkretnej osoby. Dlatego traktowana jest bardziej jako aksjomat lub swoiste prawo.

Mniej formalnie, hipoteza pozwala dokładniej sformułować pojęcie samego algorytmu, mówiąc jednocześnie, że komputery są w stanie go wykonać. Co więcej, wszystkie komputery mają jednakowe możliwości, jeśli chodzi o zdolność do ich wykonywania, a nie dostępne zasoby oraz że nie jest możliwe zbudowanie komputera o zdolności do rozwiązywania większej liczby problemów, niż najprostsza maszyna Turinga.

Hipotezę zaproponował po raz pierwszy Stephen Cole Kleene w 1943 roku, lecz została ona nazwana od Alonzo Churcha i Alana Turinga.