Algorithmen und Berechenbarkeit

Begriffe vorab

• Algorithmus: Eindeutige Folge von Schritten, die ein Problem löst.
• Turing-Maschine: Abstraktes Rechenmodell von Alan Turing.
• Berechenbar: Eine Funktion, für die ein Algorithmus existiert.
• Entscheidungsproblem: Frage, ob es ein mechanisches Verfahren gibt, das jede mathematische Aussage entscheidet.
• Komplexität: Wie Zeit- und Speicherbedarf mit der Eingabegröße wachsen.

Was ein Algorithmus ist

Ein Algorithmus ist eine endliche, eindeutige Anleitung aus Einzelschritten, die für jede zulässige Eingabe zu einem Ergebnis führt. Ein Rezept ist keiner (es lässt Spielraum), das schriftliche Addieren schon. Die Informatik fragt nicht nur, wie man ein Problem löst, sondern auch, ob und wie schnell.

Turing 1936

Alan Turing veröffentlichte 1936 den Aufsatz „On Computable Numbers, with an Application to the Entscheidungsproblem“. Er beschrieb eine idealisierte Rechenmaschine, die Turing-Maschine, als Modell dafür, was ein Mensch mit einem exakt vorgegebenen Verfahren ausrechnen kann. Mit diesem Modell zeigte er, dass es keinen mechanischen Prozess geben kann, der alle mathematischen Fragen entscheidet. Die Church-Turing-These besagt, dass jede Funktion, die sich mechanisch berechnen lässt, von einer Turing-Maschine berechnet werden kann. Sie ist eine These und kein beweisbarer Satz, weil „mechanisch berechenbar“ kein formal definierter Begriff ist.

Warum das für die Praxis zählt

• Es gibt Probleme, für die kein Algorithmus existieren kann (Unentscheidbarkeit).
• Es gibt Probleme, die lösbar, aber in der Praxis zu langsam sind.
• Jede Programmiersprache kann im Prinzip dasselbe berechnen; Unterschiede liegen in Komfort und Geschwindigkeit, nicht in der Berechenbarkeit.

Ein einfaches Beispiel: Suchen

Gesucht wird ein Name in einer Liste mit n Einträgen. Die lineare Suche prüft Eintrag für Eintrag – im schlechtesten Fall n Schritte. Ist die Liste sortiert, halbiert die binäre Suche den Suchbereich in jedem Schritt: Bei 1.000.000 Einträgen genügen etwa 20 Schritte (2²⁰ ≈ 1.048.576).

def binaere_suche(liste, ziel):
    unten, oben = 0, len(liste) - 1
    while unten <= oben:
        mitte = (unten + oben) // 2
        if liste[mitte] == ziel:
            return mitte
        if liste[mitte] < ziel:
            unten = mitte + 1
        else:
            oben = mitte - 1
    return -1

Der Unterschied zwischen n und etwa log₂ n Schritten ist das, was man mit „Komplexität“ meint.

Frage bei jedem Problem zwei Dinge: Gibt es einen Algorithmus – und wie wächst sein Aufwand mit der Eingabe?

Zum Selbermachen

1. Führe die binäre Suche von Hand für die Liste 2, 5, 8, 12, 16, 23, 38 und das Ziel 23 durch.
2. Schätze, wie viele Schritte eine lineare Suche bei 1.000.000 Einträgen im schlechtesten Fall braucht.

Verwandte Themen

Rechner → „Von-Neumann-Architektur“. KI → Maschinelles Lernen erzeugt Verfahren aus Daten, bleibt aber an dieselben Grenzen der Berechenbarkeit gebunden.

Prüfstatus: Belegt (Stand 1. Oktober 2026): Turings Aufsatz von 1936, die Idee der Turing-Maschine, das Ergebnis zum Entscheidungsproblem und die Formulierung der Church-Turing-These wurden gegen Fachquellen (u. a. Stanford Encyclopedia of Philosophy) geprüft. Nicht einzeln belegt: die Rechnung zur binären Suche (nachrechenbar), das Codebeispiel (konstruiert, nicht ausgeführt) und die Aussage zur Gleichwertigkeit von Programmiersprachen (verbreitete Lehrmeinung).

Quellen

• Alan M. Turing – „On Computable Numbers, with an Application to the Entscheidungsproblem“ (Proceedings of the London Mathematical Society, 1936)
• Stanford Encyclopedia of Philosophy – „The Church-Turing Thesis“