La tesi Church-Turing fa referència al concepte d'un mètode eficient, sistemàtic o mecànic en lògica, matemàtiques i informàtica. Es formula com una descripció del concepte intuïtiu de computabilitat i, en relació a les funcions recursives generals, s'anomena més sovint tesi de Church. També fa referència a la teoria de les funcions computables per ordinador. La tesi va aparèixer a la dècada de 1930, quan els ordinadors encara no existien. Més tard va rebre el nom del matemàtic nord-americà Alonso Church i el seu col·lega britànic Alan Turing.
Eficiència del mètode per aconseguir el resultat
El primer dispositiu que s'assemblava a un ordinador modern va ser el Bombie, una màquina creada pel matemàtic anglès Alan Turing. Es va utilitzar per desxifrar missatges alemanys durant la Segona Guerra Mundial. Però per a la seva tesi i formalització del concepte d'algorisme, va utilitzar màquines abstractes, més tard anomenades màquines de Turing. Presenta la tesiinterès tant per als matemàtics com per als programadors, ja que aquesta idea va inspirar els creadors dels primers ordinadors.
En la teoria de la computabilitat, la tesi Church-Turing també es coneix com la conjectura sobre la naturalesa de les funcions computables. Afirma que per a qualsevol funció algorítmicament computable sobre nombres naturals, hi ha una màquina de Turing capaç de calcular-la. O, en altres paraules, hi ha un algorisme adequat per a això. Un exemple conegut de l'eficàcia d'aquest mètode és la prova de la taula de veritat per provar tautologia.
Una manera d'aconseguir qualsevol resultat desitjat s'anomena "eficaç", "sistemàtica" o "mecànica" si:
- El mètode s'especifica en termes d'un nombre finit d'instruccions exactes, cada instrucció s'expressa mitjançant un nombre finit de caràcters.
- S'executarà sense errors, produirà el resultat desitjat en un nombre determinat de passos.
- El mètode pot ser realitzat per un humà sense ajuda amb qualsevol equip que no sigui paper i llapis
- No requereix comprensió, intuïció o enginy per part de la persona que realitza l'acció
A l'inici de les matemàtiques, el terme informal "eficaçment computable" s'utilitzava per referir-se a funcions que es poden calcular amb llapis i paper. Però la mateixa noció de computabilitat algorítmica era més intuïtiva que qualsevol cosa concreta. Ara es caracteritzava per una funció amb un argument natural, per a la qual hi ha un algorisme de càlcul. Un dels èxits d'Alan Turing va serrepresentació d'un predicat formalment exacte, amb l'ajuda del qual seria possible substituir l'informal, si s'utilitza la condició d'eficiència del mètode. L'església va fer el mateix descobriment.
Conceptes bàsics de funcions recursives
El canvi de predicats de Turing, a primera vista, semblava diferent del proposat pel seu col·lega. Però com a resultat, van resultar ser equivalents, en el sentit que cadascun d'ells selecciona el mateix conjunt de funcions matemàtiques. La tesi Church-Turing és l'afirmació que aquest conjunt conté totes les funcions els valors de la qual es poden obtenir mitjançant un mètode que compleixi les condicions d'eficiència. Hi havia una altra diferència entre els dos descobriments. Va ser que Church només va considerar exemples de nombres enters positius, mentre que Turing va descriure el seu treball com que cobria funcions computables amb una variable integral o real.
Funcions recursives habituals
La formulació original de Church estableix que el càlcul es pot fer mitjançant el càlcul λ. Això equival a utilitzar funcions recursives genèriques. La tesi Church-Turing cobreix més tipus de càlcul del que es pensava originalment. Per exemple, relacionat amb autòmats cel·lulars, combinadors, màquines de registre i sistemes de substitució. El 1933, els matemàtics Kurt Gödel i Jacques Herbrand van crear una definició formal d'una classe anomenada funcions recursives generals. Utilitza funcions on més d'un argument és possible.
Crear un mètodeCàlcul λ
El 1936, Alonso Church va crear un mètode de determinació anomenat càlcul λ. Estava associat amb els nombres naturals. Dins del càlcul λ, el científic va determinar la seva codificació. Com a resultat, s'anomenen números de l'Església. Una funció basada en nombres naturals es va anomenar λ-computable. Hi havia una altra definició. La funció de la tesi de Church s'anomena λ-computable sota dues condicions. El primer sonava així: si es calculava sobre elements de l'Església, i la segona condició era la possibilitat de ser representat per un membre del càlcul λ.
També l'any 1936, abans d'estudiar el treball del seu col·lega, Turing va crear un model teòric per a les màquines abstractes que ara porten el seu nom. Podrien realitzar càlculs manipulant els personatges de la cinta. Això també s'aplica a altres activitats matemàtiques que es troben en la informàtica teòrica, com ara la computació probabilística quàntica. La funció de la tesi de Church només es va comprovar més tard mitjançant una màquina de Turing. Inicialment, es basaven en el càlcul λ.
Computabilitat de la funció
Quan els nombres naturals es codifiquen adequadament com a seqüències de caràcters, es diu que una funció sobre nombres naturals és computable per Turing si la màquina abstracta troba l'algorisme requerit i imprimeix aquesta funció en cinta. Un dispositiu d'aquest tipus, que no existia a la dècada de 1930, es consideraria en el futur un ordinador. La màquina abstracta de Turing i la tesi de Church van anunciar una era de desenvolupamentdispositius informàtics. Es va demostrar que les classes de funcions definides formalment per tots dos científics coincideixen. Per tant, com a resultat, ambdues declaracions es van combinar en una sola. Les funcions computacionals i la tesi de Church també van tenir una forta influència en el concepte de computabilitat. També es van convertir en una eina important per a la lògica matemàtica i la teoria de la demostració.
Justificació i problemes del mètode
Hi ha opinions contradictòries sobre la tesi. Es van recollir nombroses proves per a la "hipòtesi de treball" proposada per Church i Turing el 1936. Però tots els mètodes o operacions coneguts per descobrir noves funcions efectivament computables a partir d'unes donades estaven connectats amb mètodes de construcció de màquines, que llavors no existien. Per demostrar la tesi Church-Turing, es parteix del fet que cada model realista de càlcul és equivalent.
A causa de la varietat d'anàlisis diferents, generalment es considera que és una evidència especialment forta. Tots els intents de definir amb més precisió la noció intuïtiva d'una funció efectivament computable van resultar ser equivalents. Cada anàlisi que s'ha proposat ha demostrat que destaquen la mateixa classe de funcions, és a dir, aquelles que són computables per les màquines de Turing. Però alguns models computacionals van resultar ser més eficients pel que fa al temps i l'ús de la memòria per a diferents tasques. Més tard es va observar que els conceptes bàsics de les funcions recursives i la tesi de Church són més aviat hipotètiques.
Tesi M
És important distingir entre la tesi de Turing i l'afirmació que qualsevol cosa que es pugui calcular amb un dispositiu informàtic pot ser calculat per la seva màquina. La segona opció té la seva pròpia definició. Gandhi anomena la segona frase "Tesi M". Va així: "Tot allò que es pot calcular per un dispositiu pot ser calculat per una màquina de Turing". En el sentit estricte de la tesi, és una proposició empírica el valor de veritat de la qual és desconegut. La tesi de Turing i la "tesi M" de vegades es confonen. La segona versió és generalment incorrecta. S'han descrit diverses màquines condicionals que poden calcular funcions que no són computables de Turing. És important tenir en compte que la primera tesi no implica la segona, però és coherent amb la seva falsedat.
Implicació inversa de la tesi
En la teoria de la computabilitat, la tesi de Church s'utilitza com a descripció de la noció de computabilitat per una classe de funcions recursives generals. El nord-americà Stephen Kleene va donar una formulació més general. Va anomenar parcialment recursives totes les funcions parcials computables per algorismes.
La implicació inversa es coneix habitualment com la tesi inversa de l'Església. Rau en el fet que cada funció recursiva de nombres enters positius s'avalua de manera eficient. En un sentit estricte, una tesi simplement denota aquesta possibilitat. I, en un sentit més ampli, fa abstracció de la qüestió de si aquesta màquina condicional hi pot existir.
ordinadors quàntics
Els conceptes de funcions computables i la tesi de Church es van convertir en un descobriment important per a les matemàtiques, la teoria de les màquines i moltes altres ciències. Però la tecnologia ha canviat molt i segueix millorant. Se suposa que els ordinadors quàntics poden realitzar moltes tasques habituals amb menys temps que els moderns. Però queden preguntes, com ara el problema de l'aturada. Un ordinador quàntic no ho pot respondre. I, segons la tesi Church-Turing, tampoc cap altre dispositiu informàtic.
