Frage zu Palindrom in KA

Question

Mit dem Risiko, dass sowas schon mal gefragt wurde.

 

Bei einem nicht deterministischen KA, zum Beispiel bei einem Palindrom, wo der KA die Mitte richtig "abschätzen" muss. Bei langen Wörtern ist es sehr unwahrscheinlich, dass der Keller richtig "schätzt". Bedeutet das, dass der Keller also meistens das Wort nicht akzeptieren würde und man deshalb den Automaten sehr oft mit dem Wort durchgehen müsste bis er zumindest einmal erkannt wird. Und wenn es ja einmal akzeptiert wird von mehreren Versuchen reicht es ja? Ist das so richtig?

 

Was aber wenn ich nun ein Palindrom mit Milliarden Stellen habe, lasse den KA ein paar Millionen mal laufen und es wurde immer falsch geschätzt und das Wort wurde durch das falsche "schätzen" kein mal erkannt. Dann geht man fälschlicherweise davon aus, dass das Wort nicht korrekt ist, obwohl es das aber doch ist, richtig?

 

Answer 1

Woher kommen denn diese (nicht ganz korrekten) Formulierungen? Ein KA kann nicht schätzen.

Bei einem nichtdet. KA sprechen wir davon, dass er "raten" kann - das ist allerdings etwas salopp formuliert und bedeutet nicht schätzen! Ein nichtdet. Automat (also sowohl KA als auch EA, TM, ...) kann beliebig viele Konfigurationen auf einmal betrachten, weil er ja aus einem Zustand in beliebig viele Folgezustände übergehen kann. Er kann also in n Berechnungsschritten alle nach n Schritten erreichbaren Konfigurationen betrachten. Das bedeutet, dass er aus den viele möglichen Konfigurationsfolgen, die vom Startzustand aus existieren, die richtige (also die, die zu einer akzeptierenden Konfiguration führt) aussuchen kann. In diesem Sinn kann er "raten" - er rät aber immer richtig, solange es eine akzeptierende Konfigurationsfolge gibt. Auf diese Weise kann ein nichtdet. KA diejenige Konfigurationenfolge erraten, die gerade die Mitte eines potentiellen Palindorms trifft (und zwar für Palindrome beliebiger Länge!). (Es ist natürlich zu beachten, das Nichtdeterminismus ein mathematisches Konstrukt ist - so einen ratenden Automaten können wir in Wirklichkeit nicht bauen; in der Wirklichkeit sind wir immer deterministisch.)

Ein det. KA kann die Mitte eines Palindorms nicht finden und auch nicht "abschätzen".

Viele Grüße

Lukas König