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

"Teil 1\n\nEs 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.\nSomit gilt:\n\n´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}´\n\n\n**Teil 2**\n\n´w = "aabbba"´:\n\n- 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).\n- Übereinstimmung des ersten und letzten Buchstabens (´1´ Schritt).\n- Übereinstimmung des vorletzten und letzten Buchstaben nicht gegeben (´1´ Schritt).\n\nFolglich gilt:\n\n- ´t_M("aabbba") = 14 + 1 + 1 = 16´\n- ´s_M ("aabbba") = 6 + 1 = 7´\n\n\n´w = "abaaba"´:\n\n- 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).\n- Ü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).\n- ´\*\*´ 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).\n\nFolglich gilt:\n\n- ´t_M("abaaba") = 14 + 6 + 1 = 21´\n- ´s_M("abaaba") = 6 + 1 + 1 = 8´\n\n\n**Teil 3**\n\nIst ´w´ das Leerwort, wird beim Lesen des ´\*\*´ sofort in den nichtakzeptierenden Zustand gegangen.\nSomit gilt:\n\n- ´t_M(lambda) = t_M(0) = 1´\n- ´s_M(lambda) = s_M(0) = 0´\n\n(Das tatenlose Stehen über dem Arbeitsband zählt als 0, obwohl man über einer Zelle steht.)\n\nIst ´n >= 1´ ungerade, so kopiert die Maschine das Wort auf das Band und stoppt, wenn die Zelle dahinter erreicht ist.\nDamit gilt für ungerades n:\n\n- ´t_M(n) = n + 1´\n- ´s_M(n) = n + 1´\n\nEs 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)´.\nDann 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).\n\nIst ´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´.\nDie maximalen Werte werden also im letzten Fall angenommen, woraus für gerades ´n´ resultiert:\n\n- ´t_M(n) = 3n + 3´\n- ´s_M(n) = n + 2´"