Die Berechenbarkeit Klasse, die ich nehme, erklärt mehrere Sprachen, die in RE sind - REC (rekursiv aufzählbar aber nicht rekursiv, das heißt auflösbar durch eine Turing-Maschine Nicht-Halten). Es zeigt zuerst, wie einer von ihnen (L_d, Sprache der Turingmaschinen, die nicht ihre eigene Kodierung akzeptieren) nicht in RE ist und beweist, dass sein Komplement in RE - REC ist. Es beweist dann, dass es auf die universelle Sprache reduzierbar ist (L_u, die Menge aller binären Kodierungen von Turing-Maschinen, verkettet mit einer Zeichenfolge, die sie akzeptiert). Es zeigt dann, wie L_u RE-Hard ist, reduziert es dann auf L_PCP (Post Correspondence Problem) und reduziert dieses dann auf kontextfreie Grammatik-Ambiguität. Gibt es irgendwelche Probleme in RE, aber nicht in RE-Hard? Weil für jedes Problem, das unser Professor in RE - REC erklärt hat, er bewiesen hat, dass sie auf einander reduziert werden können.Gibt es rekursiv aufzählbare Probleme, die nicht RE-hart sind?
Antwort
Die Antwort auf Ihre Frage ist ja, denn auch endliche Sprachen RE sind. Aber sie sind keineswegs schwer in dem Sinne, den du meinst.
Vielleicht ist Ihre Frage wirklich "Gibt es rekursiv Enumerierbare Probleme, die nicht RE-hart aber nicht rekursiv sind?" Hier hängt die Antwort von Ihrem Konzept der Reduktion ab. Wahrscheinlich benutzt Ihr Professor vielfache Reduktionen; dann ist die Antwort wahrscheinlich, ja (ich bin mir nicht ganz sicher). Für schwächere Reduktionen ist die Antwort NEIN.
Das Problem, das Sie erwähnen (mit der Klärung von Peter Leupold, das sollte in die Frage integriert werden), ist als Post-Problem bekannt. Die Antwort ist positiv: Insbesondere sind alle sogenannten "einfachen" Mengen RE-Mengen, die nicht viele Eins sind.
Ein einfaches Set ist ein RE-Set, dessen Komplementär "immun" ist. Eine Immunmenge ist eine Menge, die keine unendliche RE-Menge enthält. Dies reicht aus, um zu beweisen, dass eine einfache Menge nicht vollständig sein kann, da die Ergänzung einer vollständigen Menge produktiv ist und jede produktive Menge eine unendliche RE-Teilmenge enthält, die durch ihre eigene Produktionsfunktion erzeugt wird.
Ein paar einfachen Sätze sind bekannt. Mein Lieblingsbeispiel ist die Menge der nicht-zufälligen Zahlen, entsprechend der Kolmogorov-Komplexität, dh die Menge aller Zahlen, die kompakter ausgedrückt werden kann als der Index eines Programms, das sie generiert (auf Eingabe 0). Der Beweis, dass eine solche Menge einfach ist, ist nicht schwierig und kann in jedem guten Text zur Berechenbarkeit gefunden werden.