Logické systémy založené na ordinálech - Systems of Logic Based on Ordinals

Logické systémy založené na ordinálech byla disertační práce matematik Alan Turing.[1][2]

Turingova teze není o novém typu formální logiky, ani se nezajímal o takzvané systémy „ranked logic“ odvozené od pořadového nebo relativního číslování, ve kterých lze provádět srovnání mezi stavy pravdy na základě relativní věrohodnosti. Místo toho Turing zkoumal možnost vyřešení stavu Godelianovy neúplnosti pomocí Cantorovy metody nekonečen. Tuto podmínku lze konstatovat - ve všech systémech s konečnými množinami axiomů platí pro expresivní sílu a prokazatelnost podmínka exkluzivní - nebo; tj. jeden může mít moc a žádný důkaz, nebo důkaz a žádnou moc, ale ne obojí.

Tato práce je zkoumáním formálních matematických systémů po Gödelova věta. Gödel ukázal, že jakýkoli formální systém S dostatečně silný na to, aby reprezentoval aritmetiku, existuje věta G, která je pravdivá, ale systém není schopen dokázat. G mohl být přidán jako další axiom do systému namísto důkazu. To by však vytvořilo nový systém S 's jeho vlastní neprokazatelnou pravdivou větou G' atd. Turingova práce zvažuje iteraci procesu do nekonečna a vytvoření systému s nekonečnou sadou axiomů.

Práce byla dokončena v Princetonu pod Alonzo Church a byla to klasická práce v matematice, která zavedla koncept ordinální logika.[3]

Martin Davis uvádí, že ačkoli Turingovo použití a výpočetní věštec není hlavním zaměřením disertační práce, ukázalo se, že má velký vliv teoretická informatika, např. v polynomiální časová hierarchie.[4]

Reference

  1. ^ Turing, Alan (1938). Logické systémy založené na ordinálech (Disertační práce). Univerzita Princeton. doi:10.1112 / plms / s2-45.1.161. hdl:21.11116 / 0000-0001-91CE-3. ProQuest  301792588.
  2. ^ Turing, A. M. (1939). "Logické systémy založené na ordinálech". Proceedings of the London Mathematical Society: 161–228. doi:10.1112 / plms / s2-45.1.161. hdl:21.11116 / 0000-0001-91CE-3.
  3. ^ Solomon Feferman, Turing v zemi O (z) v „Univerzálním Turingově stroji: průzkum za půl století“ od Rolfa Herkena 1995 ISBN  3-211-82637-8 strana 111
  4. ^ Martin Davis "Vyčíslitelnost, výpočet a skutečný svět", v Představivost a přísnost editoval Settimo Termini 2006 ISBN  88-470-0320-2 stránky 63-66 [1]

externí odkazy