Tesis na Church-Turing

Sa teoriya ng komputabilidad, ang tesis na Church-Turing (sa Ingles ay Church-Turing Thesis o Church–Turing conjecture, Church's thesis, Church's conjecture, at Turing's thesis) ay pinagsamang hipotesis (tesis) tungkol sa kalikasan ng mga punsiyon na ang mga halaga ay epektibong makukwenta o sa modernong termino, makakawenta ng algoritmo. Sa simpleng termino, ito ay nagsasaad na ang "lahat ng makukwenta ng isang algoritmo ay makukwenta ng makinang Turing."

Ang ilang pagtatangka ay isinagawa sa simulang kalahati ng ika-20 siglo upang isa-pormal ang nosyon ng komputabilidad:

• Ang Briton na matematikong si Alan Turing ay lumikha ng teoretikal na modelo para sa isang makina na tinatawag na pangkalahatang makinang Turing na makakapagsagawa ng mga kalkulasyon mula sa mga input,
• Si Alonzo Church kasama ang matematikong si Stepehn Kleene at lohisyanong si J.B.Rosser ay lumikha ng pormal na depinisyon ng klase ng mga punsiyon na ang ang mga halaga ay makukwenta sa pamamagitan ng rekursiyon.

Ang lahat ng mga prosesong komputasyonal na rekursiyon, kalkulong lambda at makinang Turing ay naipakitang magkatumbas—ang tatlong mga paraang ito ay naglalarawan ng parehong mga klase ng punsiyon. Ito ay nagtulak sa mga matematiko at siyentipiko ng kompyuter na maniwalang ang konsepto ng komputabilidad ay tiyak na mailalarawan ng tatlong magkakatumbas na mga prosesong ito. Sa inpormal na paglalarawan, ang tesis na Church-Turing ay nagsasaad na kung ang ilang paraan o algoritmo ay umiiral upang magsagawa ng kalkulasyon, kung gayon ang parehong kalkulasyon ay maisasagawa rin ng makinang Turing gayundin ng punsiyong mailalarawan ng rekursiyon at punsiyong kalkulong lambda.

Ang tesis na Church-Turing ang pahayag na naglalarawan ng kalikasan ng komputasyon (pagkukwenta) at hindi pormal na mapapatunayan. Bagaman ang tatlong mga prosesong nabanggit sa itaas ay magkatumbas, ang pundamental na premisa sa likod ng tesis na ito—ang nosyon ng kung ano ang kahulugan para sa isang punsiyon na maging epektibong makukwenta— ay kahit paano isang malabo sa intwitibo, kaya ang tesis na ito ay nanatiling hipotesis.

Bagaman ang tesis na ito ay hindi pormal na mapapatunayan, ang tesis na Church-Turing ay mayroong pangkalahatang pagtanggap sa kasalukuyan.

Ang lathalaing ito na tungkol sa Matematika ay isang usbong. Makatutulong ka sa Wikipedia sa pagpapalawig nito.