Hier sind ja auch einige hauptberufliche/studierte Informatiker vertreten und daher dachte ich mir, vielleicht weiss ja einer von euch Rat.
Wir haben eine Hausaufgabe (siehe Anhang), bei der ich nicht wirklich weiter komme. Eine 1-Band DTM (deterministische Turingmaschine) zur Bestimmung von Palindromen ist mit einer Laufzeit von O(n²) ja trivial. Auch wenn es in der Aufgabenstellung nicht steht, wird n hier die Eingabenlänge sein.
Jedoch finde ich keinen Weg, eine DTM zu bauen, die das ganze in der vorgegeben Laufzeit bestimmt. Ausserdem verwirrt mich das, mit dem beliebig kleinen Epsilon etwas. Ja, mir ist das Prinzip aus zB der Analysis bekannt, aber dadurch wird das n² ja extrem klein und irgendwie fast schon unnötig. Da ein Teil der Laufzeit O(n) ist, habe ich mir schon einige Verfahren überlegt, bei dem die DTM einmal(oder halt linear wachsend) über die Eingabe gehen muss und danach in sehr kleiner Zeit (epsilon*n²) bestimmen kann, ob es ein Palindrom ist oder nicht, aber alle Überlegungen liefen ins Leere. Wobei ich denke, dass es so im Prinzip laufen muss.
Die Sache mit den Zuständen und der Zustandsmenge ist sicherlich ein Tipp, welcher sich mir aber nicht wirklich erschliesst. Da wir idR ein binäres Alphabet für die Eingabe haben(sehr doof, dass es hier nicht genau spezifiziert ist), könnte man natürlich jede mögliche Kombination an Eingaben als Zustände codieren, aber dann wäre die Zustandsmenge ja auch irgendwie unendlich und das ist ja nicht möglich.
Kann mir hier vielleicht jemand mit Tipps weiterhelfen? Also das ist die Aufgabenstellung, mehr steht da nicht. Solltet ihr noch andere Definitonen oder so brauchen, einfach sagen
Schonmal danke für jeden, der versucht mir zu helfen
ERROR