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

Year 2011, Issue: 53, 253 - 270, 15.07.2011

Ahmet Çevik

Abstract

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.

Keywords

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

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

Abstract

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.

Keywords

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

References

• A.A.Fraenkel, Bar-Hillel: Foundations of Set Theory. Amsterdam, pp. x+415 (1958)
• A.Church: An unsolvable problem of elementary number theory. American Journal of Mathematics, 58:345-363 (1936)
• A.M.Turing: On Computable Numbers with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Ser.2, Vol.42 (1937)
• A.Syropoulos, Hypercomputation Computing Beyond The Church-Turing Barrier, Springer Sceience+Business Media (2008).
• B.Russell: Mathematical Logic as based on the theory of types. American Journal of Mathematics, 30, pp. 222-262 (1908)
• E.Zermelo: Untersuchungen über die Grunlagen der Mengenlehre. Math. Ann. 65, pp.261-281 (1908)
• G.Frege: Die Grundlagen der Arithmetik: Eine logisch-mathematische Untersuchung über den Begriff der Zahl (1884)
• G.J.Chaitin: The Limits of Mathematics, A Course on Information Theory and the Limits of Formal Reasoning, Springer-Verlag, London (2003)
• G.Peano: 1889. The Principles of Arithmetic; van Heijenoort, pp. 85-97 (1968)
• J.E.Hopcroft, R.Motwani, J.D.Ullman: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd Ed. (2001)
• K.Gödel: Über die Vollständigkeit des Logikkalküls, Doctoral Dissertation, University of Vienna (1929)
• K.Gödel: Über formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I. Monatsh. Math. und Phys. 38, pp. 173-198 (1931)
• K.Gödel: Consistency proof for the Generalized Continuum Hypothesis. Proc. Nat. Acad. Sci. USA 25 pp. 220-224 (1939)
• P.J.Cohen: A Minimal Model for Set Theory. Bull. Amer. Math. Soc. 69, pp.537-540 (1963)
• P.J.Cohen: The Independence of the Continuum Hypothesis, I, II. Proc. Nat. Acad. Sci. USA 50 pp.1143-1148 (1964)
• P.Smith: An Introduction to Gödel’s Theorems. Cambridge University Press (2007)