Fachgebiet! turing-maschine

25.11.2008, 13:30

wanoek

turing-maschine

hey leute ... vielleicht kennt sich ja jemand aus

hab hier eine turingmaschine zu bauen die aus der eingabe der wortes

$\begin{eqnarray*} a_0a_1a_2\cdots a_n \end{eqnarray*}$

das wort

$\begin{eqnarray*} a_0'a_0'a_1a_1a_2a_2\cdots a_na_n \end{eqnarray*}$

auf das band schreibt.

meine frage ist jetzt ob ich diese maschine genau angeben kann .. unabhängig von der anzahl der unterschiedlichen a's ...
ich dachte an eine maschine, die die zeichen liest und dann ans ende des wortes geht und da jeweils zwei von diesen schreibt, wieder an den anfang und die gleiche prozedur nochmal, allerdings müsste man die prozedur des "ans ende gehens" für jedes zeichen extra angeben ... gibt es eine andere möglichkeit ?

25.11.2008, 13:32

therisen

Auf diesen Beitrag antworten »

Hast du absichtlich $\begin{eqnarray*} a_0' \end{eqnarray*}$ geschrieben?

25.11.2008, 13:40

wanoek

Auf diesen Beitrag antworten »

ja ... soll so sein

25.11.2008, 13:48

wanoek

Auf diesen Beitrag antworten »

$\begin{eqnarray*} a_0' \end{eqnarray*}$ soll irgendwie nicht in dem alphabet sein, aus dem das wort $\begin{eqnarray*} a_0a_1a_2\cdots a_n \end{eqnarray*}$ besteht ...

25.11.2008, 18:32

wanoek

Auf diesen Beitrag antworten »

ja ... genau so steh ich auch da ... Tanzen

26.11.2008, 16:06

Reksilat

Auf diesen Beitrag antworten »

Touringmaschine ist lange her, aber ein wenig weiß ich vielleicht noch

Zitat:

allerdings müsste man die prozedur des "ans ende gehens" für jedes zeichen extra angeben

Ist eigentlich kein Aufwand, es gibt doch verschiedene Zustände und Du legst dann allgemein fest, dass er, wenn er $\begin{eqnarray*} a_i \end{eqnarray*}$ liest in den Zustand $\begin{eqnarray*} t_i \end{eqnarray*}$ wechselt und im Zustand $\begin{eqnarray*} t_i \end{eqnarray*}$ geht er eben ans Ende und schreibt zwei mal $\begin{eqnarray*} a_i \end{eqnarray*}$ . (Benötigt im Endeffekt natürlich noch mehr Zustände, da er ja zählen muss, wie oft er $\begin{eqnarray*} a_i \end{eqnarray*}$ schreibt)

Eine Frage: Was soll die doofe Maschine denn machen, wenn in der Eingabe schon alle Buchstaben des Alphabets vorkommen?

PS: Es gibt hier einen Editierknopf und der letzte Beitrag wenig hilfreich, dafür äußerst verwirrend.

26.11.2008, 18:21

wanoek

Auf diesen Beitrag antworten »

hm ... ja, davon bin ich ausgegangen, ich dachte es gibt eine ... "elegantere" lösung. übrigens soll die maschine es etwas anders machen, die soll sowas aufs band schreiben:

$\begin{eqnarray*} a_0a_0'a_1a_1'a_2a_2\cdots a_na_n' \end{eqnarray*}$

aber die vorgehensweise ist ja die gleiche

26.11.2008, 18:53

Reksilat

Auf diesen Beitrag antworten »

Verstehe ich nicht ganz. Ist jetzt einfach nur $\begin{eqnarray*} a_0\neq a_0' \end{eqnarray*}$ oder ist $\begin{eqnarray*} a_0'\not\in \{a_0,\ldots,a_n\} \end{eqnarray*}$ . Im ersten Fall würden ja zwei mögliche Belegungen für sämtliche $\begin{eqnarray*} a_i' \end{eqnarray*}$ ausreichen, im zweiten Fall benötigte man nur ein einziges "globales" $\begin{eqnarray*} a' \end{eqnarray*}$ .
Es wäre schon günstig, die genaue Aufgabenstellung zu kennen.

26.11.2008, 19:03

wanoek

Auf diesen Beitrag antworten »

ähm ... genaue aufgabenstellung .. sofort

sei $\begin{eqnarray*} \Sigma \end{eqnarray*}$ ein alphabet. konstruiere eine turing-maschine, die bei eingabe des wortes
$\begin{eqnarray*} a_0a_1a_2\cdots a_n \end{eqnarray*}$ aus $\begin{eqnarray*} \Sigma^* \end{eqnarray*}$
das wort
$\begin{eqnarray*} a_0a_0'a_1a_1'a_2a_2'\cdots a_na_n' \end{eqnarray*}$
auf das band schreibt und terminiert. für jedes symbol $\begin{eqnarray*} a \end{eqnarray*}$ aus $\begin{eqnarray*} \Sigma \end{eqnarray*}$ sei hierbei $\begin{eqnarray*} a' \end{eqnarray*}$ ein neues symbol das nicht in $\begin{eqnarray*} \Sigma \end{eqnarray*}$ vorkommt.

26.11.2008, 19:40

Reksilat

Auf diesen Beitrag antworten »

OK also sind die $\begin{eqnarray*} a_i' \end{eqnarray*}$ nicht aus $\begin{eqnarray*} \Sigma \end{eqnarray*}$ .

Ich verstehe aber nicht, was die $\begin{eqnarray*} a_i' \end{eqnarray*}$ mit den $\begin{eqnarray*} a_i \end{eqnarray*}$ zu tun haben. Wenn alle $\begin{eqnarray*} a_i' \end{eqnarray*}$ gleich sind, ist die Notation irreführend und wenn, wie Du ja auch schreibst, jedesmal ein neues $\begin{eqnarray*} a_i' \end{eqnarray*}$ gefunden werden muss, dann kann ich mit der Eingabe genügend großer Wörter so weit kommen, dass keine neuen Buchstaben mehr zur Verfügung stehen.

Ich bin erst mal weg, vielleicht findet sich ja jemand, der das besser versteht.
(btw.: Es gibt auch Informatikforen)

03.12.2008, 14:06

wanoek

Auf diesen Beitrag antworten »

so alles klar. man kann die maschine "explizit" nicht angeben, man braucht für jedes zeichen einen eigenen zustand, mit dem die maschine nach ganz rechts läuft und das entsprechende zeichen auf das band schreibt.

03.12.2008, 19:19

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von Reksilat
(btw.: Es gibt auch Informatikforen)

Korrekt. ----> http://www.informatikerboard.de/index_start.php

*geschlossen*

Neue Frage »

Antworten »

Fachgebiet! turing-maschine

Verwandte Themen