Systems of Logic Based on Ordinals

Systems of Logic Based on Ordinals va ser la tesi doctoral del matemàtic Alan Turing.^[1]^[2]

La tesi de Turing no tracta d'un nou tipus de lògica formal, ni tampoc estava interessat en els sistemes anomenats "lògics classificats" derivats de la numeració ordinal o relativa, en què es poden fer comparacions entre estats de veritat sobre la base de la veracitat relativa. En canvi, Turing va investigar la possibilitat de resoldre la condició d'incompletezza de Godel usant el mètode dels infinits de Cantor. Aquesta condició es pot afirmar així: en tots els sistemes amb conjunts finits d'axiomes, una condició exclusiva o s'aplica al poder expressiu i a la demostrabilitat; és a dir, es pot tenir poder i cap prova, o prova i no poder, però no tots dos.

La tesi és una exploració dels sistemes matemàtics formals després del teorema de Gödel. Gödel va demostrar que per a qualsevol sistema formal S prou potent per representar l'aritmètica, hi ha un teorema G que és cert però el sistema no és capaç de demostrar-ho. Es podria afegir G com a axioma addicional al sistema en lloc d'una demostració. Tanmateix, això crearia un nou sistema S' amb el seu propi teorema veritable no demostrable G', i així successivament. La tesi de Turing analitza què passa si simplement itereu aquest procés repetidament, generant un conjunt infinit de nous axiomes per afegir a la teoria original, i fins i tot fa un pas més enllà en l'ús de la recursivitat transfinita per anar "més enllà de l'infinit", produint un conjunt de nous axiomes. teories G _n, una per cada nombre ordinal n.

La tesi es va completar a Princeton sota Alonzo Church, va ser publicada el 1939 esdevenint un treball clàssic de les matemàtiques que va introduir el concepte de lògica ordinal.^[3]

Martin Davis afirma que tot i que l'ús de Turing d'un oracle informàtic no és un focus important de la tesi, ha demostrat ser molt influent en la informàtica teòrica, per exemple, en la jerarquia de temps polinomial.

Referències

↑ {{{títol}}} (tesi). PhD, 1938. DOI 10.1112/plms/s2-45.1.161.
↑ Turing, A. M. Proceedings of the London Mathematical Society, 1939, pàg. 161–228. DOI: 10.1112/plms/s2-45.1.161.
↑ Solomon Feferman, Turing in the Land of O(z) in "The universal Turing machine: a half-century survey" by Rolf Herken 1995 ISBN 3-211-82637-8 page 111

Enllaços externs

[turingphd-1] {{{títol}}} (tesi). PhD, 1938. DOI 10.1112/plms/s2-45.1.161.

[2] Turing, A. M. Proceedings of the London Mathematical Society, 1939, pàg. 161–228. DOI: 10.1112/plms/s2-45.1.161.

[3] Solomon Feferman, Turing in the Land of O(z) in "The universal Turing machine: a half-century survey" by Rolf Herken 1995 ISBN 3-211-82637-8 page 111

[1]

[2]

[3]