Sistemas de lógica basados en ordinales -Systems of Logic Based on Ordinals
Systems of Logic Based on Ordinals fue la tesis doctoral del matemático Alan Turing .
La tesis de Turing no trata sobre un nuevo tipo de lógica formal, ni estaba interesado en los llamados sistemas de "lógica clasificada" derivados de la numeración ordinal o relativa, en los que se pueden hacer comparaciones entre estados de verdad sobre la base de la veracidad relativa. En cambio, Turing investigó la posibilidad de resolver la condición de incompletitud godeliana utilizando el método de infinitos de Cantor . Esta condición puede enunciarse así: en todos los sistemas con conjuntos finitos de axiomas, se aplica una condición exclusiva o al poder expresivo y la demostrabilidad; es decir, uno puede tener poder y ninguna prueba, o prueba y no poder, pero no ambos.
La tesis es una exploración de sistemas matemáticos formales según el teorema de Gödel . Gödel demostró que cualquier sistema formal S lo suficientemente poderoso como para representar aritmética, existe un teorema G que es cierto pero el sistema no puede probarlo. G podría agregarse como un axioma adicional al sistema en lugar de una prueba. Sin embargo, esto crearía un nuevo sistema S 'con su propio teorema verdadero G' no demostrable, y así sucesivamente. La tesis de Turing analiza lo que sucede si simplemente iteras este proceso repetidamente, generando un conjunto infinito de nuevos axiomas para agregar a la teoría original, e incluso va un paso más allá en el uso de la recursividad transfinita para ir "más allá del infinito", produciendo un conjunto de nuevos teorías G n , una por cada número ordinal n.
La tesis se completó en Princeton bajo Alonzo Church y fue un trabajo clásico en matemáticas que introdujo el concepto de lógica ordinal .
Martin Davis afirma que aunque el uso de Turing de un oráculo de computación no es un enfoque principal de la disertación, ha demostrado ser muy influyente en la informática teórica , por ejemplo, en la jerarquía de tiempo polinomial .
Referencias
enlaces externos
- https://rauterberg.employee.id.tue.nl/lecturenotes/DDM110%20CAS/Turing/Turing-1939%20Sysyems%20of%20logic%20based%20on%20ordinals.pdf
- https://www.dcc.fc.up.pt/~acm/turing-phd.pdf
- https://web.archive.org/web/20121023103503/https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf
- "Tesis de Princeton de Turing" . Prensa de la Universidad de Princeton . Consultado el 10 de enero de 2012 .
- Solomon Feferman (noviembre de 2006), "Turing's Thesis" (PDF) , Avisos de la AMS , 53 (10)
 |
Este artículo relacionado con la lógica matemática es un fragmento . Puedes ayudar a Wikipedia expandiéndolo . |
 |
Este artículo sobre una publicación matemática es un fragmento . Puedes ayudar a Wikipedia expandiéndolo . |