Introduction to computability theory and Turing degrees

Yıl 2012, Sayı: 1, 1 - 20, 01.03.2012

Ahmet Çevik

Öz

Computability (Recursion) Theory is a branch of mathematical logic which
was begun with Gödel’s incompleteness theorem, later formalized by Alan
Turing, and succeeded by Emil Post and Stephen Kleene’s work. In this survey
paper, we introduce the reader recursion theory and give some of the
known results in the theory of Turing degrees.

Anahtar Kelimeler

Mathematical logic, computability, recursion theory, Turing degrees, undecidability

Hesaplanabilirlik kuramı ve Turing derecelerine giriş

Öz

Hesaplanabilirlik ( Özyineleme) kuramı Gödel'in eksiklik teoremiyle başlamış, Alan Turing'in Turing makineleriyle biçimsel bir hale getirilmiş, Emil Post ve Stephen Kleene ile devam etmiş bir matematiksel mantık dalıdır. Bu makalede hesaplanabilirlik kuramına giriş yapaca¸gız ve Turing dereceleriyle ilgili literatürde bilinen sonuçları vereceğiz.

Anahtar Kelimeler

Matematiksel mantık, hesaplanabilirlik, Özyineleme kuramı, Turing dereceleri, karar verilemezlik