Fachrat Informatik - Forum

Quoted

Original von Artemis
1) Ist es egal wieviele Bänder die TM in Aufgabe 2 hat?

Im Prinzip schon, aber da die Eingabe in Binärdarstellung vorliegt, kommt man mit einem Band locker aus.

Quoted

2) Ist n in Form von n aufeinanderfolgenden 1en beschrieben, oder in binaerdarstellung?

Siehe oben.

Quoted

und generell: mehrband-tms sind deterministisch, richtig?

Generell nicht, aber in dieser Vorlesung schon.

Ich glaube:
1. n ist eine narürliche Zahl. Es wurde auch deutlich in der Aufgabe präzisiert(f: IN--->IN).
2. Ob du nur mit 1-Band TM oder mit 2-Band TM arbeitest kommst du meiner Meinung nach ganz locker am Ziel. Wobei ich sagen muss,1-Band TM(TM) ist hier gefragt. Sollten wir mit K-Bänder TM arbeiten dann müßte schon den Wert von k (k natürliche Zahl) klar sein.
Übrigens, für die Aufgabe muss du eingentlich nur wissen daß bei einige Ziffern, einen Übertrag vorkommt(1 natürlich).

Wieso ist die Eingabe binäre? f: IN----->IN.
Ich dachte IN = {0,1,2,3,.................}
Man könnte das ganze auch so definieren um Binäredarstellung zu bekommen. f: {0,1}*---->{0,1}*.
Was glaubst du?

Quoted

Original von maguitou1
Wieso ist die Eingabe binäre? f: IN----->IN.
Ich dachte IN = {0,1,2,3,.................}
Man könnte das ganze auch so definieren um Binäredarstellung zu bekommen. f: {0,1}*---->{0,1}*.
Was glaubst du?

Nochmal zur Klärung:

Immer wenn es (in dieser Vorlesung) darum geht, eine Funktion
f: N^k -> N
mit einer Turingmaschine zu berechnen, gehen wir davon aus, daß sowohl die Eingabe zu Beginn als auch die Ausgabe nach der Berechnung in Binärdarstellung auf dem (ersten) Arbeitsband steht.

Das steht auch so in der Definition von "Turing-Berechenbarkeit" aus der Vorlesung.

Die Binärdarstellung wählt man hier übrigens, weil es für spätere Anwendungen in der Komplexitätstheorie sinnvoller ist. Auf diese Weise lassen sich benötigter Speicherplatz und Laufzeit verringern.

Danke Joachim!
Übrigens, mit {0,1,......9} als Eingabealphabet habe ich noch viel erklären müßen. Mit {0,1} ist das ganze sehr leicht. Ich werde mir mal diese bin(x) Definition genau anschauen.
MFG.