Тезис на Чърч

от Уикипедия, свободната енциклопедия

Тезисът на Чърч, по името на американският логик Алонсо Чърч, твърди, че всички дефиниции на понятието формален метод (алгоритъм, ефективна процедура) са еквивалентни.

Нарича се тезис, защото не е аксиома, не е и математическа теорема, а подобно на физическите закони изразява експериментален опит - всяка нова конструкция на изчисляващо устройство се оказва еквивалентна на коя да е от известните схеми за изчисление (примерно на Машина на Тюринг).