Sobre la relevancia de la tesis de Turing

Aldana D’Andrea

Resumen


En este artículo intentamos dar cuenta de la relevancia de la tesis de Turing sobre el concepto de cálculo efectivo en relación con la tesis de Church sobre el mismo tema. Si bien ambas tesis son extensionalmente equivalentes y proporcionan, por lo tanto, una misma solución al Entscheidungsproblem de Hilbert, hay una especie de acuerdo en considerar que la formulación de Turing es la más satisfactoria o la más convincente. La pregunta es por qué se da tal acuerdo. En respuesta a esta pregunta destacamos la complejidad del Entscheidungsproblem e indagamos en qué medida las propuestas de Church y Turing captan dicha complejidad.


Palabras clave


tesis de Turing; cálculo efectivo; Entscheidungsproblem

Texto completo:

PDF

Enlaces refback

  • No hay ningún enlace refback.


 

EDUNTREF – Editorial de la Universidad Nacional de Tres de Febrero. Centro Cultural Borges, Viamonte esq. San Martín 3p. (C1053ABK) Ciudad de Buenos Aires, Argentina.

Editorial de la Universidad Nacional de Quilmes. Roque Sáenz Peña 352, (B1876BXD) Bernal, Provincia de Buenos Aires, Argentina.

www.metatheoria.com.ar. ISSN 1853-2322 (Impresa), ISSN 1853-2330 (En línea).