Tesis na Church-Turing

Mula sa Wikipediang Tagalog, ang malayang ensiklopedya
Tumalon sa: nabigasyon, hanapin

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 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.