Тезисът на Чърч (също като Тезис на Чърч-Тюринг Курсове , ФМИ, Софийски университет, линк от 16-01-2010 или Теза на Чърч-Тюринг Курс по Изкуствен Интелект , Технически университет - София, линк от 16-01-2010), по името на американския логик Алонсо Чърч и Тюринг, в теория на изчислимостта е комбинирана хипотеза („тезис“) за природата на ефективно изчислимите функции чрез рекурсия (тезис на Чърч), чрез механичен способ, еквивалентен на машина на Тюринг (тезис на Тюринг) или чрез употреба на ламбда-изчисление на Чърч.
Тезисът на Чърч по-конкретно твърди, че всички дефиниции на понятието формален метод (алгоритъм, ефективна процедура) са еквивалентни.
Нарича се тезис, защото не е аксиома, не е и математическа теорема, а подобно на физическите закони изразява експериментален опит – всяка нова конструкция на изчисляващо устройство се оказва еквивалентна на коя да е от известните схеми за изчисление (например на машина на Тюринг).
Източници
Външни препратки Изчерпателна информация за тезиса на Чърч от Станфордска философска енциклопедия
Категория:Теоретична информатика Категория:Езици за програмиране