SAYILAMAZ SONSUZLUK, KARAR VERİLEMEZLİK VE GÖDEL’İN EKSİKLİK TEOREMİ

Öz

Bu makalede 19. ve 20. yüzyılda matematiğin felsefesi/temelleri üzerine yapılan çalışmalardan, mantığın ve biçimselleştirmenin getirdiği sonuçlardan, hesaplanabilirlik kuramının tarihinden, ve teorik bilgisayar biliminin oluşumuna neden olan matematik dünyasındaki çalışmalardan bahsedilmiştir. Özetle, Cantor’un sonsuz kümeler kuramı, kendine referans veren paradokslar, Gödel’in eksiklik kuramı, karar verilemezlik ve teorik bilgisayar bilimi literatüründe bilinen durma problemine değinilmiştir. Son olarak kümeler kuramında bir problem olarak bilinen süreklilik hipotezinin biçimsel dillerle olan ilişkisinden ve hesaplanabilirlik kuramında doğabilecek potansiyel bir krizden bahsedilmiştir.

Anahtar Kelimeler

• Sayılamaz
• Sonsuzluk
• Karar Verilemezlik
• Gödel
• Eksiklik Teoremi.

UNCOUNTABLE INFİ NİTY UNDECİDABİLİTY AND GÖDEL’S INCOMPLETENESS THEOREM

Öz

In this paper, we survey the topics that were studied in the 19th and 20th century on the philosophy/foundations of mathematics, and discuss the impacts of mathematical logic and formalism, history of computability theory, and studies in mathematics that lead to the creation of the foundations of theoretical computer science. Briefly, we discuss Cantor’s theory of infinite sets, self-referential paradoxes, Gödel’s incompleteness theorems, undecidability, and the halting problem. Finally, we discuss the relationship between formal language theory and a problem in set theory, called the continuum hypothesis. We then point out a possible crisis, that may occur in computability theory, in relation to the continuum hypothesis.

Anahtar Kelimeler

• Uncountable
• Infinity
• Undecidability
• Gödel
• Incompleteness Theorem.

Kaynakça

1. A.A.Fraenkel, Bar-Hillel: Foundations of Set Theory. Amsterdam, pp. x+415 (1958)
2. A.Church: An unsolvable problem of elementary number theory. American Journal of Mathematics, 58:345-363 (1936)
3. A.M.Turing: On Computable Numbers with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Ser.2, Vol.42 (1937)
4. A.Syropoulos, Hypercomputation Computing Beyond The Church-Turing Barrier, Springer Sceience+Business Media (2008).
5. B.Russell: Mathematical Logic as based on the theory of types. American Journal of Mathematics, 30, pp. 222-262 (1908)
6. E.Zermelo: Untersuchungen über die Grunlagen der Mengenlehre. Math. Ann. 65, pp.261-281 (1908)
7. G.Frege: Die Grundlagen der Arithmetik: Eine logisch-mathematische Untersuchung über den Begriff der Zahl (1884)
8. G.J.Chaitin: The Limits of Mathematics, A Course on Information Theory and the Limits of Formal Reasoning, Springer-Verlag, London (2003)

9. G.Peano: 1889. The Principles of Arithmetic; van Heijenoort, pp. 85-97 (1968)
10. J.E.Hopcroft, R.Motwani, J.D.Ullman: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd Ed. (2001)
11. K.Gödel: Über die Vollständigkeit des Logikkalküls, Doctoral Dissertation, University of Vienna (1929)
12. K.Gödel: Über formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I. Monatsh. Math. und Phys. 38, pp. 173-198 (1931)
13. K.Gödel: Consistency proof for the Generalized Continuum Hypothesis. Proc. Nat. Acad. Sci. USA 25 pp. 220-224 (1939)
14. P.J.Cohen: A Minimal Model for Set Theory. Bull. Amer. Math. Soc. 69, pp.537-540 (1963)
15. P.J.Cohen: The Independence of the Continuum Hypothesis, I, II. Proc. Nat. Acad. Sci. USA 50 pp.1143-1148 (1964)
16. P.Smith: An Introduction to Gödel’s Theorems. Cambridge University Press (2007)