BjBot
Grünschnabel
Dabei seit: 30.01.2008
Beiträge: 2
 |
|
| Raum und Zeitkonstruierbarkeit |
     |
Hallo zusammen =)
Ich würde gerne wissen wie man am besten nachweist, ob eine bestimmte Funktion f raum bzw zeitkonstruierbar ist.
Was ich weiss ist, dass man hier mit Turingmaschinen argumentieren muss, diese doch sehr allgemeine Definition ist mir allerdings noch nicht ganz geheuer und ich bin deshalb auf der Suche nach eine paar charakteristischen Strategieansätzen zur Lösung dieses Problems.
Wahrscheinlich ist das von Funktion zu Funktion eh anders und ich kann auch später noch mit Beispielen ankommen.
Jedoch gibt es doch bestimmt bei der Lösung dieses Aufgabentyps bestimmte allgemeingültige Fragen, die ich mir da stellen muss - sprich, wie ich denn auf eine solche spezielle Turingmaschine komme, die exakt die Laufzeit meiner gegebenen Funktion für jede Länge n des akzeptierten Wortes wiederspiegelt (falls ich das richtig verstehe).
Wäre schön wenn mir jemand ein paar Kniffe bzw Denkweisen vermitteln könnte.
Gruß Björn
|
|
