Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Automatentheorie (http://www.informatikerboard.de/board/board.php?boardid=13)
----- Beispiele für Inverse Turingmachine (http://www.informatikerboard.de/board/thread.php?threadid=1199)
Geschrieben von thing am 26.04.2012 um 14:36:
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 :-)
Geschrieben von Karlito am 26.04.2012 um 16:03:
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
Forensoftware: Burning Board, entwickelt von WoltLab GmbH