Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Permutation nicht rekursiv aufzählbarer Sprache
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Permutation nicht rekursiv aufzählbarer Sprache
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-06-17


Hallo,
ich hätte folgende Frage: für eine Sprache L über einer Menge mit zwei Elementen, ist die Permutation Perm(L) dieser Sprache als Vereinigung aller Permutationen Perm(w) aller Wörter dieser Sprache definiert. Ich versuche zu beweisen dass es ein L gibt, für das Perm(L) nicht rekursiv aufzählbar ist.
Meine Idee bis jetzt war, dass man möglicherweise für ein nicht rekursiv aufzählbares L ein solches Perm(L) erhält, aber irgendwie habe ich nicht die richtige Beweisidee. Könnte man evtl. wenn man L als Menge aller Gödelnummern von berechenbaren Funktionen wählt, die Aussage beweisen?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2025
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-06-17


Hallo AutoNier, und herzlich willkommen auf dem Matheplaneten! 😃

Mein Vorschlag wäre, L so zu wählen, dass alle Wörter in L nur aus a bestehen (wenn man annimmt, dass das Alphabet {a, b} ist). Dann gilt ja automatisch Perm(L) = L. Du musst also nur eine Sprache L über einem Zeichen finden, die nicht rekursiv aufzählbar ist. Hast Du dafür eine Idee?

Viele Grüße
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-06-17


Oh, das klingt nach einer eleganten Idee, leider fällt mir da keine Sprache ein, könntest du mir einen Tipp geben? fed-Code einblenden

fed-Code einblenden



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2025
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-06-17


Hallo AutoNier,

nimm einfach eine beliebige nicht rekursiv aufzählbare Sprache L' von natürlichen Zahlen und definiere dann <math>L= \{a^n : n \in L"\}</math>.

Viele Grüße
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]