Тезис на Чърч

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Тезисът на Чърч (също като Тезис на Чърч-Тюринг [1] или Теза на Чърч-Тюринг [2]), по името на американският логик Алонсо Чърч и Тюринг, в теория на изчислимостта е комбинирана хипотеза („тезис“) за природата на ефективно изчислимите функции чрез рекурсия (тезис на Чърч), чрез механичен способ, еквивалентен на машина на Тюринг (тезис на Тюринг) или чрез употреба на ламбда-изчисление на Чърч.

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

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

Източници[редактиране | edit source]

  1. Курсове, ФМИ, Софийски университет, линк от 16-01-2010
  2. Курс по Изкуствен Интелект, Технически университет - София, линк от 16-01-2010

Външни препратки[редактиране | edit source]