Turingmaschine, die nach n^2 Schritten hält

28.11.2022, 20:37

Malcang

Turingmaschine, die nach n^2 Schritten hält

Guten Abend zusammen!

Ich möchte zeigen, dass die Funktion $\begin{eqnarray*} f: \mathbb N \rightarrow \mathbb N, n\mapsto n^2 \end{eqnarray*}$ zeitkonstuierbar ist. Ich muss also eine Turinmaschine finden, die nach genau $\begin{eqnarray*} n^2 \end{eqnarray*}$ Schritten hält. Dabei ist $\begin{eqnarray*} n \end{eqnarray*}$ die Länge der Eingabe.
Bisher bin ich aber nicht dahintergekommen verwirrt

Ich dachte schon an die Summe der ungeraden Zahlen oder die Summe aller Zahlen n. Ich lande ja jeweils im Bereich des Quadrates. Aber das wollte mir nicht so recht glücken. Hat jemand einen Hinweis für mich?

29.11.2022, 08:42

Elvis

Auf diesen Beitrag antworten »

(bei Wikipedia?) habe ich eine unaere zweibaendige Turingmaschine gefunden, die n als n Einsen n mal von einem Band auf das andere übertraegt. Das sind n^2 Operationen (oder nicht?).

29.11.2022, 12:14

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
(bei Wikipedia?) habe ich eine unaere zweibaendige Turingmaschine gefunden, die n als n Einsen n mal von einem Band auf das andere übertraegt. Das sind n^2 Operationen (oder nicht?).

Hi Elvis, danke für deine Zeit.
Ich schaue gleich mal, ob ich den Wikiartikel vielleicht finde. Ich hatte auch schon an so etwas gedacht, aber ich tue mir sehr schwer. Ich muss ja auch immer überprüfen, ob die Eingabe zuende ist. Dazu muss ich ja dann über das n-te Element hinausgehen verwirrt

29.11.2022, 12:45

Elvis

Auf diesen Beitrag antworten »

Wenn drei =||| auf einem Band steht, und der Lesekopf steht auf dem ersten | , dann schreibt der Schreibkopf ||||||||| auf das zweite Band und stoppt bei erreichen der ersten leeren Lesezelle. Genau neun Lese-/Schreib-/Bewegung-Vorgänge.

29.11.2022, 12:59

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Wenn drei =||| auf einem Band steht, und der Lesekopf steht auf dem ersten | , dann schreibt der Schreibkopf ||||||||| auf das zweite Band und stoppt bei erreichen der ersten leeren Lesezelle. Genau neun Lese-/Schreib-/Bewegung-Vorgänge.

Aber der Schreibkopf muss doch "wissen" dass er jetzt drei mal III hinschreiben soll. Aber dafür muss ich ja auch schon alleine mit dem Lesekopf einmal das gesamte Band einlesen. Dann habe ich ja schon drei Schirtte gemacht, noch bevor das erste I auf das zweite Band geschrieben wurde.

29.11.2022, 14:27

Elvis

Auf diesen Beitrag antworten »

Stimmt. Ist $\begin{eqnarray*} n^2 +n \end{eqnarray*}$ ~ $\begin{eqnarray*} n^2 \end{eqnarray*}$ nicht zeitkonstruierbar? Jedenfalls nah dran.

29.11.2022, 17:21

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Ist $\begin{eqnarray*} n^2 +n \end{eqnarray*}$ ~ $\begin{eqnarray*} n^2 \end{eqnarray*}$ nicht zeitkonstruierbar?

Laut allen Büchern ist Addition und Multiplikation zeitkonstruierbarer Funktionen wieder zeitkonstruierbar.
Aber nehme ich doch mal $\begin{eqnarray*} f(n) = n \end{eqnarray*}$ und die Eingabe $\begin{eqnarray*} 1 \end{eqnarray*}$ . Dann brauche ich ja sogar zwei Schritte um festzustellen, dass es nur diese Eins ist.

Neue Frage »

Antworten »

Turingmaschine, die nach n^2 Schritten hält

Verwandte Themen