Beispiele für Inverse Turingmachine |
26.04.2012, 14:36 | Auf diesen Beitrag antworten » |
thing | Beispiele für Inverse Turingmachine Meine Frage: Hallo ich suche zwei einfache Turingmachinen, die eine wandelt einen String 1 in den String 2 um, die Andere den String 2 in den String 1. a. Selbst inverse Lösung (Machine 1 == Machine 2) sind bevorzugt. b. Wenn möglich nicht über binäre operation. Meine Ideen: hab ich nicht :-) |
|
|
26.04.2012, 16:03 | Auf diesen Beitrag antworten » |
Karlito | Hallo, Allgemein kann es ein solches Paar TM nicht geben, da eine Abbildung von einem String auf einen anderen nicht zwangsläufig Bijektiv ist. D.h. Maschine 1 Bildet jeden String auf den String "a" ab. Es gibt für die Maschine 2 keine Möglichkeit den Ursprungsstring wiederherzustellen... VG, Karlito |
|