imported>Alfrejg: BKL Wortproblem ersetzt

2021-07-17T13:03:58Z

BKL Wortproblem ersetzt

Neue Seite

In der [[Theoretische Informatik|theoretischen Informatik]] heißt eine [[formale Sprache]] <math>L</math> über einem [[Alphabet (Informatik)|Alphabet]] <math>\Sigma</math> '''rekursiv''' (entscheidbar), wenn eine [[Turingmaschine]] M existiert, die auf allen Eingaben <math>w \in \Sigma^*</math> hält und jede Eingabe <math>w \in \Sigma^*</math> genau dann akzeptiert, wenn <math>w \in L</math> ist. Der Unterschied zu den [[rekursiv aufzählbare Sprache|rekursiv aufzählbaren Sprachen]] ist definitionsgemäß, dass eine Turingmaschine für eine rekursive Sprache immer halten muss, während eine für eine rekursiv aufzählbare Sprache nur halten muss, wenn das Wort in der Sprache liegt.

Die Menge der rekursiven Sprachen stimmt mit allen bisher vorgeschlagenen [[Berechenbarkeit]]smodellen überein. Hierzu gehören insbesondere die [[Goto-Berechenbarkeit]] und die [[While-Berechenbarkeit]], welche aus den gängigsten Programmierkonstrukten am Computer hervorgehen. Diese Übereinstimmungen sind Ausgangspunkt für die [[Churchsche These]]. 

(Beachte: Die durch [[primitive Rekursion]] erzeugten Sprachen bilden nur eine echte Teilmenge der rekursiven Sprachen; man kann zeigen, dass dies dann die gleichen Sprachen sind, die auch durch die [[Loop-Berechenbarkeit]] erzeugt werden.)

Die Menge der rekursiven Sprachen ist echte Teilmenge der Chomsky-Typ-0-Sprachen (rekursiv aufzählbare Sprachen) und echte Obermenge der Chomsky-Typ-1-Sprachen ([[Kontextsensitive Sprache|kontextsensitive Sprachen]]):

* Das [[Halteproblem]] ist rekursiv aufzählbar (Typ 0), aber nicht rekursiv
* Es gibt Sprachen, die rekursiv, aber nicht kontextsensitiv (Typ 1) sind.

Wenn es keine Turingmaschine gibt, die ein solches [[Entscheidungsproblem]] löst, so gibt es nach der Churchschen These überhaupt keinen Algorithmus für das Problem.
Man beschränkt sich bei dieser Definition auf Entscheidungsprobleme, also auf Probleme, deren Antwort nur ''Ja'' oder ''Nein'' sein kann. Es stellt sich aber heraus, dass sie trotz dieser Einschränkung meist ausreichend ist, da die zu Entscheidungsproblemen gehörenden [[Komplexitätstheorie#Berechnungsprobleme_als_Abbildungen|Berechnungsprobleme]] meist nicht schwieriger zu lösen sind.

Der Vorteil ist, dass man alle Entscheidungsprobleme auf Sprachen zurückführen kann; diese können u. a. durch ([[Noam Chomsky|Chomsky]]-)Grammatiken beschrieben werden: Eine Eingabe w ist für ein Entscheidungsproblem P genau dann eine Lösung, wenn w in der zu P gehörigen Sprache L liegt ([[Wortproblem (Berechenbarkeitstheorie)|Wortproblem]]).
Somit besteht eine Brücke zwischen dem ''erzeugenden'' [[Grammatik]]-Modell und dem ''akzeptierenden'' Automaten-Modell. In der Tat kann man zu jeder Chomsky-Grammatik-Klasse eine Automatenklasse finden, die genau die Sprachen der jeweiligen Klasse akzeptiert und umgekehrt ([[Chomsky-Hierarchie]]).

Die Nicht-Rekursivität einer Sprache kann man mittels des [[Satz von Rice|Satzes von Rice]] nachweisen.

[[Kategorie:Compilerbau]]
[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Sprachtyp]]

Rekursive Sprache - Versionsgeschichte

imported>Alfrejg: BKL Wortproblem ersetzt