Hilbert, Gödel, and Turing
In the 1920s, David Hilbert (left) wanted to put mathematics on firmer foundations. Kurt Gödel (center) and Alan Turing later showed that Hilbert’s dream was impossible.
The impact of Gödel's and Turing's breakthroughs in the 1930s is best understood against the background of the mathematical ambitions definitively expressed by David Hilbert in the 1920s (though foreshadowed in a famous address that he gave in 1900). Hilbert – founder of the "formalist" approach in Philosophy of Mathematics – advocated in 1921 that researchers' primary aim should be to establish mathematics on a solid and provably consistent foundation of axioms, from which, in principle, all mathematical truths could be deduced (by the standard methods of first order or "predicate" logic). Then in 1928 he formulated his Entscheidungsproblem or "decision problem": could an effective procedure be devised which would demonstrate – in a finite time – whether any given mathematical proposition was, or was not, provable from a given set of axioms?
Consistency, Completeness, and Decidability
Here we can see three distinguishable concerns. First, consistency: the set of axioms should be consistent, and provably so. Secondly, completeness: all mathematical truths should – in principle – be deducible from those axioms. Thirdly, decidability: there should be a clearly formulated procedure which is such that, given any statement of mathematics, it can definitively establish within a finite time whether or not that statement follows from the given axioms.
In formal treatments of these notions, they are standardly interpreted syntactically (i.e. in terms of the structural relationships between formulae) rather than semantically (i.e. in terms of truth and meaning). Thus understood, a consistent system is one in which it is never possible to prove both a proposition P and its negation not(P). And a complete system is one in which it is always possible to prove either P or not(P), for any proposition P that is expressible within the system. So consistency and completeness are closely related, and can be understood quite independently of the issue of whether or not the axioms are true and the rules valid (i.e. truth-preserving). If, however, we were able to achieve a consistent and complete system of arithmetic, with true axioms and valid rules, then any arithmetical proposition would be provable if, and only if, it is true. A major part of Hilbert's dream would thus be realised.
Gödel's Incompleteness Theorems
(This outline is very simplified – for more detail, see the Mind-Crafts introduction to Gödel's Theorem or the Apronus outline of Gödel's Theorem, or Ernest Nagel and James R. Newman's classic book Gödel's Proof.)
In a famous paper published in 1931, Gödel proved that in any true (and hence consistent) axiomatic theory sufficiently rich to enable the expression and proof of basic arithmetic propositions, it will be possible to construct an arithmetical proposition G such that neither G, nor its negation, is provable from the given axioms. Hence the system must be incomplete. This is known as Gödel's First Incompleteness Theorem. Moreover it follows from Gödel's reasoning that G must, in fact, be a true statement of arithmetic.
Gödel's proof ingeniously shows how statements about mathematical relationships (e.g. that a particular sequence of propositions provides a proof of some proposition P) can be encoded as statements within arithmetic. This encoding, moreover, is truth-preserving, so that the encoded "meta-mathematical" statement will be true if, and only if, the encoding statement of arithmetic is true. He then cleverly derives an arithmetical proposition G which encodes the statement that G itself is unprovable within the system. Now if G were false, then it would follow (from this encoding) that it was not unprovable: hence it would have to be provable within the system. But then, given the conditions of the encoding, its negation not(G) – which encodes the statement that G is provable – would itself have to be true and hence provable if the system is complete. It follows that if the system is complete, it cannot be consistent, since both G and not(G) would then be provable within it. Hence no system that is complete can also be consistent. QED.
Recall, now, that the system of axioms is in fact consistent: as we have just seen, it follows that the system cannot be complete, since neither G nor not(G) will be provable within it. But then it follows from the conditions of the encoding that G, which encodes the proposition that G is not provable, must after all be true!
Gödel's Second Incompleteness Theorem, also published in the same article, follows from the first. It states – in effect – that no consistent axiomatic theory sufficiently rich to enable the expression and proof of basic arithmetic propositions (and of basic results about formal provability) can prove its own consistency.
In outline, the Second Incompleteness Theorem follows from the first as follows, though making all this precise is deep and complex, requiring the rigorous formalisation of sophisticated informal notions. Suppose that a system were able to prove its own consistency. Then since statement G follows from the system's consistency, statement G must itself be provable within the system. But since G encodes the statement that G is unprovable within the system, we have a contradiction. It follows that the system cannot after all prove its own consistency.
Turing's Theorem
Gödel's incompleteness theorems left the Entscheidungsproblem as unfinished business. Although he had shown that any consistent axiomatic system of arithmetic would leave some arithmetical truths unprovable, this did not in itself rule out the existence of some "effectively computable" decision procedure which would infallibly, and in a finite time, reveal whether or not any given proposition P was, or was not, provable. Turing's landmark contribution, in his paper of 1936 "On Computable Numbers, with an Application to the Entscheidungsproblem", was to devise a rigorous notion of effective computability based on the "Turing Machine". He then showed that there exist problems – notably the famous "Halting Problem" for Turing Machines – that cannot be effectively computed by this means. That is, he proved the impossibility of devising a Turing Machine program that can determine infallibly (and within a finite time) whether or not a given Turing Machine T will eventually halt given some arbitrary input I.
Hence Turing proved that Hilbert's Entscheidungsproblem was unsolvable. Hilbert's dream was shattered: any consistent axiomatic theory sufficiently rich to enable the expression and proof of basic arithmetic propositions could be neither complete (as Gödel had shown) nor effectively decidable.
Hilbert, Gödel, dan Turing
Pada tahun 1920-an, David Hilbert (kiri) ingin menempatkan matematika pada dasar yang lebih kuat. Kurt Gödel (tengah) dan Alan Turing kemudian menunjukkan bahwa mimpi Hilbert tidak mungkin.
Dampak dari terobosan Gödel dan Turing di tahun 1930-an paling baik dipahami dengan latar belakang ambisi matematika yang dinyatakan secara definitif oleh David Hilbert di tahun 1920-an (meskipun dibayangi dalam pidato terkenal yang ia berikan pada tahun 1900). Hilbert - pendiri pendekatan "formalis" dalam filsafat matematika - menganjurkan pada tahun 1921, bahwa tujuan utama para peneliti adalah untuk membangun matematika di atas dasar aksioma yang solid dan konsisten, dari mana, pada prinsip, semua kebenaran matematika dapat diringkaskan (dengan metode standar urutan pertama atau logika "Prediksi").
Kemudian pada tahun 1928 ia merumuskan masalah Entscheidungs atau "masalah keputusan" nya: dapatkah sebuah prosedur efektif dirancang yang akan menunjukkan - dalam waktu yang terbatas - apakah ada dalil matematika yang diberikan, atau tidak, dapat dibuktikan dari seperangkat aksioma tertentu?
Konsistensi, Kelengkapan, dan Ketepatan
Di sini kita dapat melihat tiga kekhawatiran yang dapat dibedakan. Pertama, konsistensi: seperangkat aksioma harus konsisten, dan terbukti demikian. Kedua, kelengkapan: semua kebenaran matematika harus – pada dasarnya – dapat dideduksi dari aksioma-aksioma tersebut. Ketiga, penentuan: harus ada prosedur yang dirumuskan dengan jelas yang sedemikian rupa sehingga, mengingat pernyataan matematika apa pun, secara definitif dapat menetapkan dalam waktu yang terbatas apakah pernyataan itu mengikuti aksioma yang diberikan atau tidak.
Dalam perlakuan formal dari gagasan-gagasan ini, mereka secara standar ditafsirkan secara sintetis (yaitu dalam hal hubungan struktural antara rumus) daripada secara semantis (yaitu dalam hal kebenaran dan makna). Dengan demikian dipahami, sistem yang konsisten adalah sistem yang tidak pernah mungkin untuk membuktikan kedua dalil P dan negasinya bukan (P). Dan sistem yang lengkap adalah sistem yang selalu memungkinkan untuk membuktikan P atau tidak (P), untuk setiap proposal P yang dapat diungkapkan dalam sistem. Jadi konsistensi dan kelengkapan berhubungan erat, dan dapat dipahami secara terpisah dari masalah apakah aksioma benar atau tidak dan aturannya valid (yaitu menjaga kebenaran). Namun, jika kita mampu mencapai sistem aritmetika yang konsisten dan lengkap, dengan aksioma yang benar dan aturan yang valid, maka setiap proposal aritmetika akan dapat dibuktikan jika, dan hanya jika, itu benar. Sebagian besar mimpi Hilbert akan terwujud.
Teori Ketidaklengkapan Gödel
(garis besar ini sangat sederhana – untuk lebih detail, lihat pengenalan Pikiran-Crafts pada Teori Gödel atau garis besar Apronus dari Teori Gödel, atau Ernest Nagel dan James R. Buku klasik Newman, Gödel's Proof. )
Dalam sebuah makalah terkenal yang diterbitkan pada tahun 1933 Gödel membuktikan bahwa dalam setiap teori aksiomatik yang benar (dan karenanya konsisten) cukup kaya untuk memungkinkan ekspresi dan bukti dari dalil aritmetika dasar, akan memungkinkan untuk membangun sebuah dalil aritmetika G sehingga G, maupun negasinya, tidak dapat dibuktikan dari aksioma yang diberikan. Oleh karena itu sistemnya harus tidak lengkap. Ini dikenal sebagai Teori Ketidaklengkapan Pertama Gödel. Selain itu, ini mengikuti dari alasan Gödel bahwa G sebenarnya harus menjadi pernyataan aritmatika yang benar.
Bukti Gödel dengan cerdik menunjukkan bagaimana pernyataan tentang hubungan matematika (misalnya bahwa urutan tertentu dari proposal memberikan bukti dari beberapa proposal P) dapat dikode sebagai pernyataan dalam aritmatika. Penyandian ini, apalagi, memelihara kebenaran, sehingga pernyataan "metematik" yang disandi akan benar jika, dan hanya jika, pernyataan encoding aritmatika benar. Dia kemudian dengan cerdik memperoleh sebuah dalil aritmetika G yang mengkode pernyataan bahwa G itu sendiri tidak dapat dibuktikan dalam sistem. Sekarang jika G palsu, maka akan mengikuti (dari encoding ini) bahwa itu tidak dapat dibuktikan: karenanya harus dibuktikan dalam sistem. Tetapi kemudian, mengingat kondisi encoding, negasinya bukan (G) – yang mengkode pernyataan bahwa G dapat dibuktikan – itu sendiri harus benar dan karenanya dapat dibuktikan jika sistemnya selesai. Akibatnya, jika sistem selesai, tidak dapat konsisten, karena baik G dan tidak (G) akan dapat dibuktikan di dalamnya. Oleh karena itu tidak ada sistem yang lengkap juga yang bisa konsisten. QED.
Ingat, sekarang, bahwa sistem aksioma sebenarnya konsisten: seperti yang baru saja kita lihat, sistem ini tidak dapat lengkap, karena G atau tidak (G) tidak akan dapat dibuktikan di dalamnya. Tetapi kemudian mengikuti dari kondisi encoding yang G, yang mengkode dalil bahwa G tidak dapat dibuktikan, pasti benar!
Teori Ketidaklengkapan Kedua Gödel, juga diterbitkan dalam artikel yang sama, mengikuti dari yang pertama. Ini menyatakan – pada dasarnya – bahwa tidak ada teori aksiomatik yang konsisten yang cukup kaya untuk memungkinkan ekspresi dan bukti dari dalil aritmatika dasar (dan hasil dasar tentang provabilitas formal) dapat membuktikan konsistensi sendiri.
Secara garis besar, Teori Ketidaklengkapan Kedua mengikuti dari yang pertama sebagai berikut, meskipun membuat semua ini akurat adalah mendalam dan kompleks, membutuhkan formalisasi yang ketat dari gagasan informal yang canggih. Andaikan sebuah sistem mampu membuktikan konsistensi sendiri. Kemudian karena pernyataan G mengikuti dari konsistensi sistem, pernyataan G sendiri harus dibuktikan dalam sistem. Tetapi karena G mengkode pernyataan bahwa G tidak dapat dibuktikan dalam sistem, kita memiliki sebuah kontradiksi. Akibatnya, sistem tidak dapat membuktikan konsistensi sendiri.
Teori Turing
Teori ketidaklengkapan Gödel meninggalkan masalah Entscheidungs sebagai urusan yang belum selesai. Meskipun ia telah menunjukkan bahwa setiap sistem aksiomatik konsisten aritmetika akan meninggalkan beberapa kebenaran aritmetika yang tidak dapat dibuktikan, ini tidak dengan sendirinya menutup adanya beberapa prosedur keputusan yang "dapat dihitung secara efektif" yang akan secara sempurna, dan dalam waktu yang terbatas, mengungkapkan apakah ada dalil P yang diberikan atau tidak. Tidak, dapat dibuktikan. kontribusi tengara Turing, dalam makalahnya tahun 1933 "On Computable Numbers, with an Application to the Entscheidungsproblem", adalah untuk merancang gagasan yang ketat tentang komputabilitas efektif berdasarkan "Mesin Turing". Dia kemudian menunjukkan bahwa ada masalah - terutama "Masalah Halting" yang terkenal untuk Mesin Turing - yang tidak dapat dihitung secara efektif dengan cara ini. Artinya, ia membuktikan ketidakmungkinan merancang program Mesin Turing yang dapat menentukan secara infalibel (dan dalam waktu yang terbatas) apakah Mesin Turing T yang diberikan pada akhirnya akan berhenti mengingat beberapa masukan sewenang-wenang I.
Oleh karena itu Turing membuktikan bahwa masalah Entscheidungs Hilbert tidak dapat diselesaikan. Mimpi Hilbert hancur: setiap teori aksiomatik yang konsisten cukup kaya untuk memungkinkan ekspresi dan bukti dari dalil aritmetika dasar tidak bisa lengkap (seperti yang telah ditunjukkan oleh Gödel) atau secara efektif diputuskan.