Berechenbarkeit der Umkehrfunktion

Neue Frage »

adminchen Auf diesen Beitrag antworten »
Berechenbarkeit der Umkehrfunktion
Hi ihrs !
Hab folgende Aufgabe zu lösen:

Sei X ein endliches Alphabet und eine bijektive, totale, berechenbare Funktion.
Zeigen Sie: Die Umkehrfunktion ist berechenbar.

Ehrlich gesagt geht es mir erstmal um das Verständnis der Aufgabe.
Also. ist ja berechenbar. Die Umkehrfunktion sieht aber ganz genauso aus und man soll zeigen, dass diese auch berechenbar ist.
Für meinen normalen VErstand steht die Lösung doch schon da, oder?
Also wenn die Umkehrfunktion gleich der Ausgangsfunktion ist (jetzt mal mathematisch gesehn, auch wenn das ne Aufgabe aus GdP, also Informatik, ist), dann ist doch auch die Umkehrfunktion berechenbar, oder?


Würde mich mal über einen Ansatz freuen.
adminchen Auf diesen Beitrag antworten »

Keiner ne Ahnung oder hab ich das einfach zu dämlich formuliert? Hilfe Hilfe
AD Auf diesen Beitrag antworten »

Zunächst mal müssen wir die Informatiker- in die Mathematiksprache überestzen. als endliches Alphabet ist einfach eine endliche Menge, aber was zum Teufel ist ?

Bleibt noch Berechenbarkeit, und das heißt ja wohl nur, dass man für jedes Argument nach endlich vielen Elementarschritten die Funktionsberechnung durchführen kann.
kurellajunior Auf diesen Beitrag antworten »

Wenn mich meine Erinnerung nicht trübt ist ein Sprache des Alphabets .

Nur dann macht die Aufgabenstellung auch Sinn..

Jan
AD Auf diesen Beitrag antworten »

Na dann übernimm mal. Augenzwinkern
kurellajunior Auf diesen Beitrag antworten »
RE: Berechenbarkeit der Umkehrfunktion
Na, da hab ich mir ja was angelacht...

also bijektiv heißt doch surjektiv und injektiv

also jedes Zielwort wird erreicht. (surjektiv)
Keine zwei Ausgangsworte zeigen auf das selbe Zielwort (injektiv)
Alle Ausgangsworte werden verwendet (total)

Nachgelesen bei Wiki:Bijektiv) Augenzwinkern

Hilft dir das weiter zum Überlegen der Formulierung für die Umkehrfunktionsbedingungen?

Zum Verständnis der Schreibweise steht für eine Menge der Worte einer Sprache aus dem Alphabet . Dabei ist nicht zwangsläufig gleich .

Bsp: Englisch und Latein haben das selbe Alphabet sind aber zwei verschiedene Sprachen . Alles klar?

Jan
 
 
Leopold Auf diesen Beitrag antworten »

Normalerweise steht für die Menge aller Wörter über dem Alphabet .

Die Wörter von können aufgezählt werden. Nach jedem Aufzählungsschritt wende man an und prüfe, ob mit dem vorgegebenen übereinstimmt. Man stoppe, sobald das eingetreten ist. (Wegen der Bijektivität muß das nach endlich vielen Schritten einmal passieren.) Da für den Aufzählungsprozeß und für ein Algorithmus existiert, existiert also auch insgesamt ein Algorithmus, der nach endlich vielen Schritten stoppt. Also ist auch berechenbar.

So würde ich naiv an die Sache herangehen. Ich hoffe, daß das dann auch stimmt. Die Fachleute sollen es dann mit Turing-Maschinen oder sonstwie präzisieren.
AD Auf diesen Beitrag antworten »

Zitat:
Original von kurellajunior
Dabei ist nicht zwangsläufig gleich .

Da ist man als Mathematiker ja schlichtweg begeistert! Big Laugh
Und ich hatte schon befürchtet verstanden zu haben, was ist. Na egal.
Leopold Auf diesen Beitrag antworten »

A ist halt niemals gleich B, zum Ausgleich ist dann auch A nicht gleich A ...
kurellajunior Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Da ist man als Mathematiker ja schlichtweg begeistert! Big Laugh
Und ich hatte schon befürchtet verstanden zu haben, was ist. Na egal.

Okok, ich guck heute Abend nochmal richtig nach und sag Bescheid, wenns bis dahin nicht einer richtiggestellt hat. verwirrt

Jan
adminchen Auf diesen Beitrag antworten »

Danke für die vielen Tipps. Mir war auch so, dass X* immer gleich X* ist.

Ihr bringt mich jetzt aber ins grübeln.

So wie Leopold ranging, hab ich es auch "gelöst", allerdings schien mir das etwas zu trivial.
kurellajunior Auf diesen Beitrag antworten »

mmh kann in meinen MMI Aufzeichnungen nichts dazu finden. Leo wird wohl recht haben, aber dann ist die Sache ziemlich, naja, billig? Sehr seltsam.

Jan
AD Auf diesen Beitrag antworten »

@Jan

Ist für das Problem hier nicht so wichtig, aber interessehalbe mal eine Frage zur "Sprache", kann man es so formulieren:

ist irgendeine, noch näher zu spezifizierende (z.B. durch Syntaxregeln) unendliche Teilmenge von ? Die Abzählbarkeit folgt ja dann unmittelbar aus der Endlichkeit des Alphabets .
kurellajunior Auf diesen Beitrag antworten »

So hatte ich es gelernt, jedoch ist die Einschränkung "unendlich" nicht notwendig, da nach meiner Ausbildung auch endliche Sprachen existieren können/dürfen, ohne das etwaige Gesetze verletzt werden.

Also eher so:
Zitat:
ist eine, durch eine Grammatik näher spezifizierte Teilmenge von
, ,
und ist die Menge der Produktionsvorschriften

*SelberDurchles* verwirrt

Das würde bedeuten, dass gleichbedeutend ist mit . Das ist sehr unwahrscheinlich...

Also wohl eher doch wie von Leopold vorgeschlagen
Zitat:
und


Langsam kommt die Erinnerung wieder. Ich würde den letzten Vorschlag als am sinnvollsten stehen lassen, wenn auch die ursprüngliche Aufgabe damit ziemlich seltsam für mich ist.

Jan
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »