Hi!
Ich hab mal ein paar Fragen gesammelt die beim Lernen für F3/F4 so aufgekommen sind:

1. Wie genau ist das mit dem Anhalten und dem Akzeptieren einer TM? So wie ich das verstanden habe kann es doch sein, dass eine TM eine Eingabe akzeptiert aber trotzdem nicht anhält. Oder akzeptiert sie nur, wenn sie auf einem Endzustand anhält? Und was genau heisst überhaupt anhalten? Heisst das nur dass der letzte Zustand aufgrund der Übergangsfunktion und der aktuellen Eingabe nicht mehr verlassen werden kann, oder gibt's das auch "formaler"? Wirklich genau steht das im Skript alles nicht, nicht dass ich wüsste.

2. Im Skript S. 147, direkt unter Definition 8.4, steht:
"… die für jedes n element N nach (ceiling von n) Schritten anhält…"
Das ergibt doch kaum Sinn, wenn n aus N ist ist die ceiling Funktion doch völlig überflüssig. Soll es vielleicht statt ceiling von n heissen ceiling von t(n)?

3. Wie war noch gleich das Infimum definiert? (Asche auf mein vergessliches Haupt, M2/3 kommt später…)

4. S. 151 Definition 8.7:
Wo ist der Unterschied von t(n) bzw s(n) und p(n)? Wenn p(n) einfach ein Polynom ist ist t(n) bzw s(n) beliebige Funktionen (laut Definition 8.4 der Platz- und Zeitbeschränkung) dann kann doch z.B. p(n) = t(n) sein, und demnach P eine Teilmenge von DTime ? Ist aber nicht so?

5. S. 152:
Warum ist DTime Teilmenge von DSpace (und NTime Teilmenge von NSpace)?

[img]http://www.fb18.de/gfx/3.gif[/img]

1. Wie genau ist das mit dem Anhalten und dem Akzeptieren einer TM? So wie ich das verstanden habe kann es doch sein, dass eine TM eine Eingabe akzeptiert aber trotzdem nicht anhält. Oder akzeptiert sie nur, wenn sie auf einem Endzustand anhält? Und was genau heisst überhaupt anhalten? Heisst das nur dass der letzte Zustand aufgrund der Übergangsfunktion und der aktuellen Eingabe nicht mehr verlassen werden kann, oder gibt's das auch "formaler"? Wirklich genau steht das im Skript alles nicht, nicht dass ich wüsste.

ja die Frage find ich auch immer gemein ;),
hoffentlich sagt da jemand anders was richtiges zu

2. Im Skript S. 147, direkt unter Definition 8.4, steht:
"… die für jedes n element N nach (ceiling von n) Schritten anhält…"
Das ergibt doch kaum Sinn, wenn n aus N ist ist die ceiling Funktion doch völlig überflüssig. Soll es vielleicht statt ceiling von n heissen ceiling von t(n)?

also in meinem Skript heißt der Satz
"… die für jedes n element R nach (ceiling von n) Schritten anhält…"
und s, t sind in 8.4 als R -> R definiert,

ceiling von t(n) könnte aber mehr Sinn machen in solchen Satz..,
muss auch jemand anders beantworten

4. S. 151 Definition 8.7:
Wo ist der Unterschied von t(n) bzw s(n) und p(n)? Wenn p(n) einfach ein Polynom ist ist t(n) bzw s(n) beliebige Funktionen (laut Definition 8.4 der Platz- und Zeitbeschränkung) dann kann doch z.B. p(n) = t(n) sein, und demnach P eine Teilmenge von DTime ? Ist aber nicht so?

bei mir stehen da ein paar Unterscheidungsmerkmale (nicht bei 8.4 sondern direkt bei 8.7):
s,t: N -> R, für t gilt: t(n) >= n+1, für s dagegen: s(n) >= 1

soll vielleicht ausdrücken dass man mindestens n+1 Schritte braucht um ein Wort der Länge n zu lesen und mindestens einen Platz,

s und t sind sonst beliebige Funktionen, richtig, p ein Polynom


was verstehst du unter DTime? ich seh da nur DTime(f) definiert,
es ist aber richtig, dass P eine Teilmenge der Menge aller DTime(f) von allen Funktionen f ist,

genauer gilt: P = Vereinigung DTime(n^i) für alle i >= 1
(steht ja da, bei mir zumindest)

wobei man sich natürlich fragen kann
ob für das Polynom p(n) = n die Forderung 'für t gilt: t(n) >= n+1' erfüllt ist ;)

5. S. 152:
Warum ist DTime Teilmenge von DSpace (und NTime Teilmenge von NSpace)?

das ist was einfaches und wichtiges:
eine Turingmaschine die nach n^2 Schritten das Ergebnis ausgibt kann in diesen n^2 Schritten nur maximal n^2 Speicherplätze belegen (in jedem Schritt ein Platz),

also ist eine Zeitbeschränkung immer auch eine Platzbeschränkung

(Frage: auch umgekehrt?)

Prima, danke so weit erst mal… das die Definition übder die Vereinigung auch impliziert, dass die DTime-Funktionen auch Teilmengen von P sind ist mir garnicht so aufgefallen, aber jetzt wo du's sagst…

Deine Antwort zu Punkt 2 ist ja interessant, sowohl im Skript von 02 als auch von 03 steht n aus N, nicht aus R… ich vermute mal du hast das aktuellste Skript von 04 da?

Da fällt mir gerade noch was ein:

6. nach Theorem 8.5 (S. 148) ist es ja theoretisch möglich, jede TM auf nur eine einzige Zelle ihres Arbeitsbandes zu komprimieren, da das c ja eine beliebige klleine positive Zahl aus R sein darf, und man also für jedes s(n) ein c findet, so dass c*s(n) eben nur noch 1 ist. Wie soll das denn praktisch aussehen? Kann ich mir irgendwie nicht wirklich vorstellen…

aktuelles Skript, ja,

sei n=17 und s(n) = 100,
also man brauchte 100 Plätze zum berechnen und hatte 10 verschiedene Zeichen (die Zahlen 0-9) zur Verfügung,

nun nimmt man einfach ein Alphabet mit 100^10 Zeichen und kann jeden Zustand mit einem Zeichen beschreiben,
dafür braucht man nur noch einen Platz

Da fällt mir gerade noch was ein:

6. nach Theorem 8.5 (S. 148) ist es ja theoretisch möglich, jede TM auf nur eine einzige Zelle ihres Arbeitsbandes zu komprimieren, da das c ja eine beliebige klleine positive Zahl aus R sein darf, und man also für jedes s(n) ein c findet, so dass c*s(n) eben nur noch 1 ist. Wie soll das denn praktisch aussehen? Kann ich mir irgendwie nicht wirklich vorstellen…

Achtung, du musst beachten, dass das c eine Konstante ist, die
nicht von n abhängt. Die neue Zeitbeschränkung c*s(n) kann also
zwar bewirken, dass für ein bestimmtes n gilt s(n)=1, aber
*nicht*, dass plötzlich jede Eingabe unter Verwendung von
einer einzigen Stelle auf dem Band verarbeitet werden kann.

Beispiel: Wenn s(n) unbeschränkt ist (z.B. s(n)=n),
dann wird c*s(n) immernoch unbeschränkt sein. Man kann nämlich
nach der Bandkompression das n immernoch so groß wählen, dass
c*s(n) beliebig groß wird.

3. Wie war noch gleich das Infimum definiert? (Asche auf mein vergessliches Haupt, M2/3 kommt später…)

Das Infimum einer nach unten beschränken Menge ist die größte
untere Schranke, d.h. eine Zahl x, die untere Schranke für M
ist so, dass es keine untere Schranke s für M gibt mit s>x.
Dazu sollte man wissen, dass es in den reellen Zahlen ein
Infimum zu jeder nach unten beschränkten Menge reeller Zahlen
gibt.

Edit: Mir fällt gerade auf: Deine Frage bezieht sich
wahrscheinlich auf Theorem 8.6 (lineare Beschleunigung).
Dort wird als Voraussetzung angegeben, dass
"[img]http://mokrates.de/cgi-bin/texstring?%5Cinf_%7Bn%5Crightarrow%5Cinfty%7D%20(%5Cfrac%7Bt(n)%7D%7Bn%7D)%3D%5Cinfty[/img]".

Wenn ich das richtig sehe, sollte es hier aber heißen
"[img]http://mokrates.de/cgi-bin/texstring?%5Clim_%7Bn%5Crightarrow%5Cinfty%7D%20(%5Cfrac%7Bt(n)%7D%7Bn%7D)%3D%5Cinfty[/img]"
(lim statt inf, falls Latex immernoch nicht zu lesen ist).
Und diese Voraussetzung soll nur sicherstellen, dass t(n) nicht
gerade linear verläuft, denn sonst würde Satz sagen, dass man
den Zeitverbrauch auf unter n schrauben kann, was aber die lineare
Beschleunigung nicht leisten kann, denn dabei wird der
Eingabestring immer erst komprimiert (d.h. man braucht mindestens
n Schritte).

Nebenbei: Kann es sein, dass mokrates.de nicht erreichbar ist?
Der Latex-Code funktioniert im Moment nicht.

das die Definition übder die Vereinigung auch impliziert, dass die DTime-Funktionen auch Teilmengen von P sind ist mir garnicht so aufgefallen, aber jetzt wo du's sagst…

Vielleicht hast du das richtige gemeint, aber nur um
sicherzustellen, dass du's nicht falsch verstanden hast:
Die Menge DTime(f) ist nur dann eine Teilmenge von P, wenn
f durch ein Polynom beschränkt ist.

DTime(2^n) ist z.B. nicht in P enthalten
(weil jedes Polynom irgendwann von 2^n
überstiegen wird)!

1. Wie genau ist das mit dem Anhalten und dem Akzeptieren einer TM? So wie ich das verstanden habe kann es doch sein, dass eine TM eine Eingabe akzeptiert aber trotzdem nicht anhält. Oder akzeptiert sie nur, wenn sie auf einem Endzustand anhält? Und was genau heisst überhaupt anhalten? Heisst das nur dass der letzte Zustand aufgrund der Übergangsfunktion und der aktuellen Eingabe nicht mehr verlassen werden kann, oder gibt's das auch "formaler"? Wirklich genau steht das im Skript alles nicht, nicht dass ich wüsste.

Eine gute Frage. Während ich versucht hab, die Antwort rauszufinden,
hab ich mich auch gewundert. Aber der Reihe nach.

Zunächst "hält" eine TM in einer Konfiguration k, wenn es keine
andere Konfiguration k' gibt so, dass [img]http://mokrates.de/cgi-bin/texstring?k%5Cvdash%20k'[/img].
(zumindest würde ich es so beschreiben und im Skript habe ich
keine "richtige" Definition für anhalten gefunden).

Interessant ist jetzt die Sache mit den Endzuständen (und dem Akzeptieren). Ich habe in drei Büchern nachgesehen (Komplexitätstheorie von Reischuk, Hopcroft/Ullmann und dem F2/F3-
Schöning) und überall war aus dem Text um die Definitionen herum
erkennbar, dass jede TM von einer Endkonfiguration aus keinen
Konfigurationswechsel mehr vornimmt. In Bezug auf unser F3-Skript
bin ich etwas unsicher, denn eine explizite Bemerkung habe ich nicht
dazu gefunden (deswegen habe ich mich gewundert), aber im Beweis von
2.18 wird davon gesprochen, dass ein Simulator wartet, bis eine
simulierte Maschine hält. Wenn eine TM nach einen Endzustand
weiterrechnen könnte, wäre es an dieser Stelle nötig, zu warten,
dass die simulierte in einen Endzustand kommt. Ich würde also davon
ausgehen, dass es auch hier so gemeint ist, dass Turing-Maschinen
aus einer Endkonfiguration heraus nichtmehr weiterrechnen.

Es ist aber so, dass man sich NTMen so vorstellen kann, dass alle
möglichen Rechnungen parallel ausgeführt werden. So gesehen kann
es natürlich sein, dass eine Rechnung, die parallel zu einer
Erfolgsrechnung läuft, nach dem Akzeptieren immer weiter läuft.

Slater:

also ist eine Zeitbeschränkung immer auch eine Platzbeschränkung

(Frage: auch umgekehrt?)

Ich würde das so sehen: im Prinzip nicht, denn die TM kann
innerhalb eines bestimmten Bandbereiches beliebig lange laufen.

Interessanterweise gibt es aber einen etwas anderen Zusammenhang:
Wenn man eine Platzbeschränkung kennt, kann man in Abhängigkeit von
der Eingabelänge abschätzen, wieviele mögliche Konfigurationen es
geben kann, denn die TM hat endlich viele Zustände und nur endlich
viele Möglichkeiten für den Bandinhalt und die Kopfposition.
Und wenn man weiss, dass es nur k Konfigurationen gibt, weiss man,
dass die TM nach spätestens k+1 Schritten einen Zustand zum zweiten
Mal betritt, d.h. sie gerät in eine Endlosschleife und wird nicht
halten.

Das heisst: man kann zwar aus einer Platzbeschränkung keine Zeit-
beschänkung ableiten, aber man kann zu vorgegebenem n sagen, wann
die TM (spätestens) in eine Endlosschleife gerät. Insbesondere
kann man, für die TMen, zu denen man eine Platzbeschränkung
berechnen kann, das Halteproblem entscheiden.

mir war das eigentlich egal und ich wollte nur auf die mögliche Folgefrage in Prüfungen hinweisen,
aber interessante Antwort [img]http://www.fb18.de/gfx/14.gif[/img]

Und hier sind wieder ein paar Backfrische Fragen aus der Prüfungsvorbereitung:

7. Was genau ist / macht Mü-Rekursion? Was ist dieses k was man berechent, was ändert das an einer Primitiv-Rekursiven Funktion? Und wie kann man begründen, dass beispielsweise die Ackermann-Funktion dann Mü-Rekursiv ist? Im Skript steht nur ein Literatur-Hinweis, daher vermute ich mal dass der Beweis nicht ganz einfach ist…

8. Skript S. 77: Zur Berechnung der Akzeptanz eines Wortes w wird w1, w2, … wk in den Feldern des Eingabebandes gespeichert, wi als die Zahl wi^(k) im i-ten Feld, im (k+1)-ten Feld wird eine 0 als Endmarkierung gespeichert.
Was genau ist denn nun wi^(k)? Wird das nie 0, oder warum ist die 0 die Endmarkierung?

7.
wichtig ist auf jeden Fall, dass man mit der my-Rekursion die Mänchtigkeit von while-Schleifen hat
while (x > 0) do ..

während die primitiv rekursiven Funktionen nur einer Programmierung mit for-Schleifen entsprechen
(Anzahl der Durchläufe vorher festgelegt),

alles andere zu diesem Thema ist wohl etwas zu hoch fürs einfache lernen,

die Suchfunktion in dieser Area (http://3773.rapidforum.com/?area=16) hilft zumindest etwas weiter

8.
die Definition von wi^(k) steht doch direkt davor,
wi^(k) ist immer größer 0,

wenn ein Alphabet aus 12 Zeichen besteht,
dann wird dem ersten Zeichen w1 die Zahl w1^(k) = 1, dem 12. Zeichen w12 die Zahl w12^(k) = 12 zugeteilt,

Und weiter gehts [img]http://www.fb18.de/gfx/23.gif[/img]

Dieses mal zu F4:

Auf S 18 im F4 Skript ist ein Schema zu PA-Ausdrücken angegeben, was genau soll das tun? Und wie lässt sich die Frage bewerten, ob alle Rekursionen damit beschreibbar sind? Fällt mir leider garnichts zu ein…
Die letzte Skizze auf der Seite kommt mir besonders seltsam vor, speziell die Kante die von TSp mit y wieder zurück zum Startzustand geht, wo sieht man diesen Übergang im PA-Ausdruck?