[ Inhalt ]

Index

-Operator

-Operator

unbeschränkter

-Operator

eingeschränkter

-rekursive Funktion

-rekursives Prädikat

absolut entscheidbar

Abu Jaf'ar Mohammed ibn Mûsâ al-Khowârizm

abzählbar

Abzählbarkeit

Ackermann

Ackermann-Funktion ,

Addition ,

akzeptieren

Akzeptor

Alan Turing

Algorithmus , , ,

Alphabet

Alternative

Anfangszustand

aufzählbar

aufzählbare Menge

Aufzählbarkeit ,

Aufzählverfahren ,

Automat

endlicher ,

Band

Bandalphabet ,

Bandinschrift

Basisfunktionen

berechenbar ,

berechenbare Funktion ,

Berechenbarkeit

bijektiv

Binäre Suche

busy beaver Problem

charakteristische Funktion ,

Church-Turing-These ,

Cook

Satz von

Cook, Steven

Davis

DEA

Einfärbung

Eingabealphabet ,

Einsetzung

endlicher Automat ,

endscheidbar

Endzustände

Enigma

entscheidbar ,

Entscheidbarkeit ,

Entscheidungsverfahren

Erfüllbarkeits-Entscheidungsproblem

Erfüllbarkeitsproblem

Erfüllungs-Entscheidungsproblem

Euklidischer Algorithmus

Exponentiation

exponentiell

Felder

Finalkonfiguration ,

fleißiger Biber

Funktion

-rekursive

berechenbare ,

charakteristische

ggt

Green, M.W.

Groß-O-Notation

große Linksmaschine

große Rechtsmaschine

Gödel, Kurt

Gödelisierung

Gödelnummer , ,

Halteproblem ,

Hamilton Zyklus

Initialkonfiguration

Kellerautomat ,

Kitab al-jabr w'al-muqabala

Komplexität

Komplexitätsklassen

Konfiguration

Konjunktion

konstante Funktion

kontexsensitiv

Kontrolleinheit

Kopiermaschine

lexikographische Ordnung

lineare Bandbeschränkung

Links-Suchmaschine

Linksmaschine ,

Lösung

Matrixmultiplikation

Menge

aufzählbare

Multiplikation ,

Nachfolgerfunktion , ,

Negation

Nichtentscheidbarkeit

NP-vollständig

NP-Vollständigkeit

O

Péter

Pfeildiagramm

Polynome

polynomial

primitive Rekursion

primitiv rekursiv

primitiv rekursives Prädikat

Problemausprägungen

Problemklasse

Prodekan

Projektionsfunktion

Prädikat

Prädikat

mu-rekursives

primitiv rekursives

Putnam

Quicksort

Rado

Rado, Tibor

Rechts-Suchmaschine

Rechtsmaschine ,

Rekursion

Rucksackproblem

SAT

Schreib/Lesekopf

Sequentielle Suche

simulieren

Speicherplatzverhalten

Sprache

Startmaschine

Stundenplanung

Suchmaschine

Summenproduktausdruck

terminieren

Translationsmaschine

Travelling Salesman ,

Turing, Alan

Turing-aufzählbar

Turing-berechenbar

Turing-berechenbare Funktionen

Turing-Berechenbarkeit

Turing-entscheidbar

Turing-Maschine ,

Turing-Tafel

Typ-0

Typ-0-Grammatik ,

Typ-1

Typ-2

Universelle Turing-Maschine

UTM

verifizieren

Verschiebemaschine

Vorgängerfunktion

Zeichenmaschine

Zeichenmaschinen

Zeitbedarf

Zeitverhalten

Zustandsmenge

Überführungsfunktion

Übergangsrelation

überabzählbar