Introduction to computability theory and Turing degrees

Year 2012, Issue: 1, 1 - 20, 01.03.2012

Ahmet Çevik

Abstract

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.

Keywords

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

Hesaplanabilirlik kuramı ve Turing derecelerine giriş

Abstract

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.

Keywords

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