Turinggrad

In der Berechenbarkeitstheorie und der mathematischen Logik misst der Turinggrad (auch Grad der Unlösbarkeit) einer Menge natürlicher Zahlen die algorithmische Unlösbarkeit der Menge. Das Konzept des Turinggrades ist fundamental in der Berechenbarkeitstheorie, wo Mengen natürlicher Zahlen oft als Entscheidungsprobleme angesehen werden; der Turinggrad einer Menge gibt an, wie schwer das Entscheidungsproblem für die Menge ist.

Zwei Mengen sind Turing-äquivalent, wenn sie den gleichen Grad der Unlösbarkeit haben; jeder Turinggrad ist eine Menge Turing-äquivalenter Mengen, sodass zwei Mengen genau dann in unterschiedlichen Turinggraden liegen, wenn sie nicht Turing-äquivalent sind. Außerdem sind die Turinggrade im folgenden Sinne partiell geordnet: Wenn der Turinggrad einer Menge ${\displaystyle X}$ kleiner als der Turinggrad einer Menge ${\displaystyle Y}$ ist, dann kann jede (unberechenbare) Prozedur, die korrekt entscheidet, ob Zahlen in ${\displaystyle Y}$ liegen, berechenbar in eine Prozedur umgewandelt werden, die korrekt entscheidet, ob Zahlen in ${\displaystyle X}$ liegen. In diesem Sinne korrespondiert der Turinggrad einer Menge mit dem Grad ihrer algorithmischen Unlösbarkeit.

Die Turinggrade wurden 1944 von Emil Leon Post eingeführt, und viele grundlegende Resultate wurden 1954 von Stephen Cole Kleene und Post bewiesen. Die Turinggrade sind bis heute Gegenstand intensiver Forschung. Viele Beweise in diesem Gebiet benutzen eine Beweistechnik, die als Prioritätsmethode bekannt ist.