Für ´n >= 2´ gilt ´sum\_(r = 1)^(n - 1) r2^(n − r − 1) = 2^n - n - 1´

Teil 1

Es werden weder das Leerwort noch Wörter ungerader Länge akzeptiert. Hat das Wort ´x_1 x_2 … x_n´ gerade Länge, so wird überprüft, ob ´x_i = x_(n−i+1)´ für ´1 <= i <= n´ gilt. Gilt für alle ´i´ die Gleichheit, so wird akzeptiert, anderenfalls abgelehnt. Somit gilt:

´T(M) = {x_1 x_2 … x_n | n " gerade ", x_i = x_(n−i+1) " für " 1 <= i <= n} = {w {:|:} |w| " gerade ", w = w^R}´

Teil 2

´w = "aabbba"´:

• Die Maschine läuft über das Wort und kopiert es auf das Arbeitsband und läuft auf dem Arbeitsband zurück zum Wortanfang: ´((2n + 2) = 14´ Schritte und ´n = 6´ Zellen werden beschrieben und eine Zelle dahinter betreten).
• Übereinstimmung des ersten und letzten Buchstabens (´1´ Schritt).
• Übereinstimmung des vorletzten und letzten Buchstaben nicht gegeben (´1´ Schritt).

Folglich gilt:

• ´t_M("aabbba") = 14 + 1 + 1 = 16´
• ´s_M ("aabbba") = 6 + 1 = 7´

´w = "abaaba"´:

• Die Maschine läuft über das Wort und kopiert es auf das Arbeitsband und läuft auf dem Arbeitsband zurück zum Wortanfang: ´((2n + 2) = 14´ Schritte und ´n = 6´ Zellen werden beschrieben und eine Zelle dahinter betreten).
• Übereinstimmung des ersten und letzten Buchstabens, des zweiten und zweitletzten, dritten und drittletzten usw. wird überprüft und jeweils festgestellt (´n´-mal, also ´6´-mal je ´1´ Schritt; insgesamt ´n = 6´ Schritte).
• ´**´ hinter dem Wort auf dem Eingabeband und vor dem Wort auf dem Arbeitsband werden gelesen, und ´M´ akzeptiert (´1´ Schritt und eine zusätzliche Zelle betreten).

Folglich gilt:

• ´t_M("abaaba") = 14 + 6 + 1 = 21´
• ´s_M("abaaba") = 6 + 1 + 1 = 8´

Teil 3

Ist ´w´ das Leerwort, wird beim Lesen des ´**´ sofort in den nichtakzeptierenden Zustand gegangen. Somit gilt:

• ´t_M(lambda) = t_M(0) = 1´
• ´s_M(lambda) = s_M(0) = 0´

(Das tatenlose Stehen über dem Arbeitsband zählt als 0, obwohl man über einer Zelle steht.)

Ist ´n >= 1´ ungerade, so kopiert die Maschine das Wort auf das Band und stoppt, wenn die Zelle dahinter erreicht ist. Damit gilt für ungerades n:

• ´t_M(n) = n + 1´
• ´s_M(n) = n + 1´

Es seien ´n´ gerade und ´w = x_1 x_2 … x_n´. Außerdem gelte ´x_i = x_(n−i+1)´ für ´1 <= i < k <= n´ und ´x_k != x_(n−k+1)´. Dann gilt nach den Schritten aus 2. ´t_M(w) = 2n + 2 + k´ und ´s_M(w) = n + 1´ (man beachte, dass natürlich ´k <= n/2´ gilt, da bei Gleichheit der ersten ´n/2´ Buchstaben auch die der letzten folgt).

Ist ´n´ gerade und ´w = wR´ ergibt sich wie in 2. ´t_M(w) = 2n + 2 + n + 1 = 3n + 3´ und ´s_M(w) = n + 2´. Die maximalen Werte werden also im letzten Fall angenommen, woraus für gerades ´n´ resultiert:

• ´t_M(n) = 3n + 3´
• ´s_M(n) = n + 2´