You are not logged in.

Artemis

Trainee

  • "Artemis" is male
  • "Artemis" started this thread

Posts: 52

Date of registration: Oct 6th 2003

Location: Milchstraße

Occupation: um Millionaer zu werden

1

Friday, December 12th 2003, 11:03am

Theo Inf 8.Übung

hallo ich hab mal ein paar fragen.

1) Ist es egal wieviele Bänder die TM in Aufgabe 2 hat?
2) Ist n in Form von n aufeinanderfolgenden 1en beschrieben, oder in binaerdarstellung?

und generell: mehrband-tms sind deterministisch, richtig?

schoenen gruß, artemis
he who runs away, lives to fight another day

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Friday, December 12th 2003, 11:56am

RE: Theo Inf 8.Übung

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. :)
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Artemis

Trainee

  • "Artemis" is male
  • "Artemis" started this thread

Posts: 52

Date of registration: Oct 6th 2003

Location: Milchstraße

Occupation: um Millionaer zu werden

3

Friday, December 12th 2003, 4:13pm

RE: Theo Inf 8.Übung

Quoted

Original von Joachim

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.


ist klar, dass es mit einem Band geht, deswegen frag ich ja nach ;)
he who runs away, lives to fight another day

maguitou1

Zuhörer

  • "maguitou1" is male

Posts: 3

Date of registration: May 19th 2003

Location: camer

4

Friday, December 12th 2003, 10:26pm

RE: Theo Inf 8.Übung

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).
" Zufall ist nur der Ausdruck unserer unfähigkeit, den Dingen auf den Grund zu kommen. "

maguitou1

Zuhörer

  • "maguitou1" is male

Posts: 3

Date of registration: May 19th 2003

Location: camer

5

Friday, December 12th 2003, 10:36pm

RE: Theo Inf 8.Übung

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?
" Zufall ist nur der Ausdruck unserer unfähigkeit, den Dingen auf den Grund zu kommen. "

Artemis

Trainee

  • "Artemis" is male
  • "Artemis" started this thread

Posts: 52

Date of registration: Oct 6th 2003

Location: Milchstraße

Occupation: um Millionaer zu werden

6

Saturday, December 13th 2003, 11:08am

aehm also ich denke es ist die binaere darstellung gemeint, da wir in der vorlesung immer in dieser bin(x) schreibweise gearbeitet haben.


also ich multipliziere eine binaerzahl mit 2 in meiner loesung und das geht auch ganz fein.
he who runs away, lives to fight another day

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

7

Saturday, December 13th 2003, 1:41pm

RE: Theo Inf 8.Übung

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

maguitou1

Zuhörer

  • "maguitou1" is male

Posts: 3

Date of registration: May 19th 2003

Location: camer

8

Saturday, December 13th 2003, 2:54pm

RE: Theo Inf 8.Übung

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.
" Zufall ist nur der Ausdruck unserer unfähigkeit, den Dingen auf den Grund zu kommen. "