Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Alltägliche Beispiele für (nicht-) Rekursiv Aufzählbare Sprachen und Probleme.
Für Entscheidbarkeit sind Beispiele Trivial: “Sind zwei Eingaben gleich”, “Ist Eingabe die größte Zahl”, “enthält die Binärdarstellung einer Eingegebenen Zahl 128 1’er”, …
Ebenso für nicht-Entscheidbarkeit: “Konvergiert eine Reihe ohne die Formel zu kennen”, …
Aber ich suche immer noch, um mein Verständnis zu verbessern, triviale, alltägliche oder absurde Beispiele für (nicht) Rekursive Abzählbarkeit. Dh. nicht einfach Probleme wie “das Halteproblem” oder was man hier so findet: https://en.wikipedia.org/wiki/List_of_undecidable_problems
Kann jemand ein paar Beispiele dafür geben?
Die Frage “Bist du wach?” ist rekursiv aufzählbar. Es kommt entweder die Antwort ja, oder garkeine Antwort, bis irgendwann die Antwort ja kommt.
Dual dazu “Schläfst du?”.
Anderes Beispiel:
“Ist da jemand?”
3 „Gefällt mir“
Typechecking ist in vielen Sprachen nicht entscheidbar. Das liegt einerseits daran, dass in vielen Sprachen turingvollständiges Metaprogramming möglich ist (etwa C++, LaTeX*, …). Andererseits kann es auch einfach am Typsystem einiger Sprachen liegen, die an sich gar kein Metaprogramming besitzen, etwa System F (Lambda-Kalkül + Typen) oder diverse dependently-typed Sprachen. Wenn dir das Lambda-Kalkül immer noch zu theoretisch ist: eine gewisse dependently-typed Sprache wird an der KWARC Professur benutzt, um Mathematik oder Wissen allgemein zu formalisieren.
Die Sprachen sind natürlich alle rekursiv aufzählbar, sonst hätte es keinen Sinn, diese Sprachen als Programmiersprachen zu haben 
Du kannst deren Komplimente nehmen, um nicht rekursiv aufzählbare Sprachen zu erhalten. (Denn wäre L rek. aufzählbar, aber unentscheidbar und complement(L) auch rek. aufzählbar, so auch L entscheidbar.)
*) habe ich gerade echt LaTeX in einem Satz mit Typechecking erwähnt? 
[quote=Marcel[Inf]]
[…]Du kannst deren Komplimente nehmen[…]
[/quote]
Das is aber nicht nett. Verdien’ dir deine eigenen Komplimente.
Klingeln ist auch rekursiv Aufzählbar. Warum geht man nach einer Minute einfach? Weil niemand da ist? Vielleicht ist die Person noch beschäftigt und öffnet gleich die Tür, man kann sich nie sicher sein, außer man wird reingelassen, dann is jemand daheim.
2 „Gefällt mir“