Systems of Logic Based on Ordinals

Systems of Logic Based on Ordinals was the PhD dissertation of the mathematician Alan Turing.[1][2]

Turing's thesis is not about a new type of formal logic, nor was he interested in so-called "ranked logic" systems derived from ordinal or relative numbering, in which comparisons can be made between truth-states on the basis of relative veracity. Instead, Turing investigated the possibility of resolving the Gödelian incompleteness condition using Cantor's method of infinites.

The thesis is an exploration of formal mathematical systems after Gödel's theorem. Gödel showed that for any formal system S powerful enough to represent arithmetic, there is a theorem G that is true but the system is unable to prove. G could be added as an additional axiom to the system in place of a proof. However this would create a new system S' with its own unprovable true theorem G', and so on. Turing's thesis looks at what happens if you simply iterate this process repeatedly, generating an infinite set of new axioms to add to the original theory, and even goes one step further in using transfinite recursion to go "past infinity", yielding a set of new theories Gα, one for each ordinal number α.

The thesis was completed at Princeton under Alonzo Church and was a classic work in mathematics that introduced the concept of ordinal logic.[3]

Martin Davis states that although Turing's use of a computing oracle is not a major focus of the dissertation, it has proven to be highly influential in theoretical computer science, e.g. in the polynomial-time hierarchy.[4]

References

  1. ^ Turing, Alan (1938). Systems of Logic Based on Ordinals (PhD thesis). Princeton University. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. ProQuest 301792588.
  2. ^ Turing, A. M. (1939). "Systems of Logic Based on Ordinals". 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 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
  4. ^ Martin Davis "Computability, Computation and the Real World", in Imagination and Rigor edited by Settimo Termini 2006 ISBN 88-470-0320-2 pages 63-66 [1]
Stub icon

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.

Stub icon

This article about a mathematical publication is a stub. You can help Wikipedia by expanding it.

Read other articles:

Larry Flynt - Oltre lo scandalo

Larry Flynt - Oltre lo scandaloLarry Flynt (Woody Harrelson) arringa la follaTitolo originaleThe People vs. Larry Flynt Paese di produzioneStati Uniti d'America Anno1996 Durata129 min Rapporto2,40:1 Generebiografico, commedia, drammatico RegiaMiloš Forman SceneggiaturaScott Alexander, Larry Karaszewski ProduttoreOliver Stone, Michael Hausman, Janet Yang FotografiaPhilippe Rousselot MontaggioChristopher Tellefsen Effetti specialiRodman Kiser MusicheThomas Newman ScenografiaPatrizia vo...

 

Hubur

Sungai dunia bawah. Hubur (ḪU.BUR, Hu-bur) adalah istilah dalam bahasa Sumeria yang berarti sungai, jalur air atau dunia bawah, ditulis secara ideografis dalam aksara paku 𒄷𒁓.[1][2][3] Biasanya merujuk kepada sungai dunia bawah.[4] Sungai memainkan peran tertentu dalam mitologi Mesopotamia dan agama Asiria-Babilonia, terkait dengan surga Sumeria serta para pahlawan dan dewa seperti Gilgamesh, Enlil, Enki dan Ninlil.[4] Hubur dikatakan berada di ...

 

Холокост на Украине

Часть серии статей о Холокосте Идеология и политика Расовая гигиена · Расовый антисемитизм · Нацистская расовая политика · Нюрнбергские расовые законы Шоа Лагеря смерти Белжец · Дахау · Майданек · Малый Тростенец · Маутхаузен ·&...

Gina Haspel

Gina Haspel Direktur Central Intelligence Agency ke-7Masa jabatan21 Mei 2018 – 20 Januari 2021PresidenDonald TrumpWakilVaughn Bishop PendahuluMike PompeoPenggantiDavid S. Cohen (Pelaksana tugas)William Joseph BurnsWakil DirekturCentral Intelligence Agency ke-6Masa jabatan2 Februari 2017 – 21 Mei 2018PresidenDonald Trump PendahuluDavid CohenPenggantiVaughn BishopPelaksana tugas DirekturNational Clandestine ServiceMasa jabatan28 Februari 2013 – 7 Mei 2013Preside...

 

2022 AFF Championship qualification

Football match2022 AFF Championship qualification Brunei Timor-Leste 6 3 First leg Brunei Timor-Leste 6 2 Date5 November 2022 (2022-11-05)VenueTrack & Field Sports Complex, Bandar Seri Begawan, BruneiRefereeWarintorn Sassadee (Thailand)Second leg Timor-Leste Brunei 1 0 Date8 November 2022 (2022-11-08)VenueTrack & Field Sports Complex, Bandar Seri Begawan, BruneiRefereeRazlan Joffri Ali (Malaysia)← 2018 2024 → The 2022 AFF Championship qualific...

 

Red mercury

Alleged chemical substance For other uses, see Red mercury (disambiguation). Crystals of mercury(II) sulfide and several other mercury compounds are deeply colored red, but have no publicly known use in nuclear weapons. Red mercury is a discredited substance, most likely a hoax perpetrated by con artists who sought to take advantage of gullible buyers on the black market for arms.[1] These con artists described it as a substance used in the creation of nuclear weapons; because of the ...

Eddie Haas

American baseball player and manager (born 1935) Baseball player Eddie HaasOutfielderBorn: (1935-05-26) May 26, 1935 (age 88)Paducah, Kentucky, U.S.Batted: LeftThrew: RightMLB debutSeptember 8, 1957, for the Chicago CubsLast MLB appearanceOctober 1, 1960, for the Milwaukee BravesMLB statisticsBatting average.243Hits17Runs batted in10 Teams As player Chicago Cubs (1957) Milwaukee Braves (1958, 1960) As manager Atlanta Braves (1985) George Edwin Haas (born May...

 

Northrop YB-35

American flying-wing bomber prototype YB-35 / XB-35 YB-35 prototype Role Strategic bomberType of aircraft Manufacturer Northrop Designer Jack Northrop First flight 25 June 1946 Retired 1948-1949 Status Canceled Primary user United States Air Force Number built 14 (Including 1 experimental version) Variants Northrop YB-49 The Northrop YB-35/XB-35, Northrop designation N-9[1] or NS-9,[2] were experimental heavy bomber aircraft developed by the Northrop Corporation for the U...

 

Let's Make a Deal

American game show Let's Make a DealAlso known asThe All New Let's Make a Deal (1984–86)Let's Make a Deal Primetime (2020–present)GenreComedyVariety showGame showMusical comedyCreated byStefan HatosMonty HallDirected byJoe Behar (1963–77, 1984–85)Geoff Theobald (1980–81)Hank Behar (1985–86)Barry Glazer (1990–91)James Marcione (1990–91)Morris Abraham (2003)Lenn Goodside (2009–present)Presented byMonty HallBob HiltonBilly BushWayne BradyStarringAssistant:Carol MerrillMaggie Br...

Mansfield Motor Speedway

Motorsport venue in the United States This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Mansfield Motor Speedway – news · newspapers · books · scholar · JSTOR (February 2017) (Learn how and when to remove this message) Mansfield Motor SpeedwayLocationMansfield, OhioTime zoneUTC−5 / −4 (DST)Coordinates40°4...

 

Annino (Moscow Metro)

Moscow Metro station AnninoАнниноMoscow Metro stationGeneral informationLocationChertanovo Yuzhnoye District, Southern Administrative OkrugMoscowRussiaCoordinates55°34′58″N 37°35′48″E / 55.5828°N 37.5966°E / 55.5828; 37.5966Owned byMoskovsky MetropolitenLine(s) Serpukhovsko-Timiryazevskaya linePlatforms1 island platformTracks2ConnectionsBus: 118, 249, 668, 819Trolleybus: 40ConstructionStructure typeShallow single-vaultDepth9Platform levels1Parkin...

 

Music Box (TV channel)

Former pan-European cable and satellite music television channel (1984–1987) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Music Box TV channel – news · newspapers · books · scholar · JSTOR (December 2019) (Learn how and when to remove this message) Television channel Music BoxCountryEuropeBroadcast...

Російсько-українська кібервійна

Ця стаття висвітлює поточну подію. Інформація може швидко змінюватися через розвиток подій, початкові відомості можуть виявитися ненадійними. Останні оновлення цієї статті можуть не відображати найсвіжішу інформацію. Російсько-українська кібервійна Російсько-україн...

 

Codici postali della Francia

Questa voce sugli argomenti filatelia e Francia è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Le aree dei codici postali francesi, contrassegnate dalle prime due cifre del codice postale intero. I codici postali della Francia sono composti da cinque cifre, di cui le prime due indicano il dipartimento in cui si trova il comune. Indice 1 Descrizione 2 Note 3 Voci correlate 4 Altri progetti Descrizione ...

 

Marshalsea

Marshalsea adalah sebuah penjara debitur paling terkenal di Inggris. Tempat tersebut merupakan wadah hukuman berlipat, yang makin menyengsarakan para pengutang. Deskripsi keji mengenai penjara ini mulai populer melalui pemaparan tulisan Charles Dickens, seorang novelis yang ayahnya mendekam di Marshalsea hanya karena tak mampu membayar utang ke tukang roti. Masuk ke Marshalsea berarti diperbudak hukum seumur hidup. Debitur yang sudah mendekam di Marshalsea, lazimnya sangat sulit untuk keluar...

Awaswas language

Extinct Ohlone language Not to be confused with Santa Cruz language. AwaswasSanta CruzNative toUnited StatesRegionCaliforniaExtinct(date missing)Language familyYok-Utian UtianOhloneNorthernAwaswasWriting systemLatinLanguage codesISO 639-3(included in Northern Ohlone [cst])Glottologsant1428 Chapel of the Mission Santa Cruz, reconstruction. Awaswas, or Santa Cruz, is one of eight Ohlone languages. It was historically spoken by the Awaswas people, an indigenous people of California. Linguis...

 

Joseph L. Hooper

American politician Joseph L. HooperFrontispiece of 1934's Joseph L. Hooper, Late a RepresentativeMember of the U.S. House of Representativesfrom Michigan's 3rd districtIn officeAugust 18, 1925 – February 22, 1934Preceded byArthur B. WilliamsSucceeded byHenry M. Kimball Personal detailsBorn(1877-12-22)December 22, 1877Cleveland, Ohio, U.S.DiedFebruary 22, 1934(1934-02-22) (aged 56)Washington, D.C., U.S.Political partyRepublican Joseph Lawrence Hooper (December 22, ...

 

Djarum

PT DjarumJenisKeluargaIndustriTembakauKonglomeratDidirikan21 April 1951; 73 tahun lalu (1951-04-21)PendiriOei Wie GwanKantorpusatKudus, IndonesiaTokohkunciRobert Budi HartonoMichael Bambang HartonoProdukKretekPerbankanRitelElektronikaProduk-produk perkebunanTeknologiLokapasarPariwisata dan layanan akomodasiMediaMakanan dan minumanPemilikRobert Budi Hartono Michael Bambang HartonoKaryawan75.000AnakusahaPT Sumber Cipta MultiniagaPT Stevania Ultras TobaccoPT Intertobacco Utama IndustryPT T...

Heworth Interchange

Tyne and Wear Metro and railway station in Gateshead HeworthTyne and Wear Metro stationGeneral informationLocationHeworth, GatesheadEnglandCoordinates54°57′05″N 1°33′21″W / 54.9515°N 1.5559°W / 54.9515; -1.5559Grid referenceNZ285619Transit authorityTyne and Wear PTEPlatforms2Tracks2Bus stands7ConstructionParking463 spacesBicycle facilities 4 cycle lockers 25 cycle racks AccessibleStep-free access to platformOther informationStation codeHEWFare zoneBHistory...

 

Associateship of King's College

Qualification awarded by King's College AwardAssociateship of King's CollegeLocationLondonCountryUnited KingdomPresented byKing's College LondonEligibilityKing's College London students, alumni and staffPost-nominalsAKCReward(s)Honorific post-nominals, right to wear the AKC epitoge with King's College London's academic dress on graduation.StatusCurrently awardedEstablished1834; 190 years ago (1834)First awarded1835 The Associateship of King's College (AKC) award was the degr...