Sie sind nicht angemeldet.

Lieber Besucher, herzlich willkommen bei: cloudshare.in - Forum. Falls dies Ihr erster Besuch auf dieser Seite ist, lesen Sie sich bitte die Hilfe durch. Dort wird Ihnen die Bedienung dieser Seite näher erläutert. Darüber hinaus sollten Sie sich registrieren, um alle Funktionen dieser Seite nutzen zu können. Benutzen Sie das Registrierungsformular, um sich zu registrieren oder informieren Sie sich ausführlich über den Registrierungsvorgang. Falls Sie sich bereits zu einem früheren Zeitpunkt registriert haben, können Sie sich hier anmelden.

CeXti0n

Amateur Spammer

  • »CeXti0n« ist der Autor dieses Themas

Beiträge: 60

Registrierungsdatum: 29. August 2012

Danksagungen: 25

  • Nachricht senden

1

Donnerstag, 11. Dezember 2014, 18:19

[H] Persistente Turingmaschine

Hey
Also ich muss für die Schule (13. Klasse) ein Referat über die Persistente Turingmaschine machen.
In diesem Referat enthalten sein soll folgendes:
Was ist es?
Unterschiede zur normalen Turingmaschine?
Wie funktioniert die persistente Turingmaschine?
Erklärung an einem Beispiel.
Habe in Google gewühlt und jegliche erdenkliche Kombination an Suchbergriffen durchprobiert. Das einzige was ich fand:
- nichtdeterministische 3-Band Turingmaschine (input, work, output)
- Erklärung was Persistenz in dem Zusammenhang heißt
- hat ein "Gedächtnis"
Da ich damit wohl kaum den Anspruch eines 20 Minuten Referates erfüllen kann habe ich meinen Leher angesprochen, dem mein Problem offenkundig egal gewesen zu sein scheint und mich lediglich auf englischsprachige PDF Dateien die auch bei google zu finden sind verwies. Er fügte noch hinzu, dass der Mathematische Aspekt nicht so wichtig sei und dass wir wenn es zu Mathematisch wird uns nicht damit rumschlagen müssen.
Das Problem ist, dass es in den PDF's entweder zu Mathematisch wird und ich nichts verstehe, ich im allgemeinen nichts verstehe oder die Informationen genau so karg wie im Deutschen sind.
Hat vielleicht zufällig jemand genau die selbe Aufgabe gehabt und das Referat noch irgendwo rumliegen oder kann mir wer mit Informationen weiterhelfen?

lg

blubb

I know it's only Rock'n'Roll but I like it

Beiträge: 93

Registrierungsdatum: 27. Januar 2010

Danksagungen: 116

  • Nachricht senden

2

Freitag, 12. Dezember 2014, 05:09

Wenn ihr Vorträge zu solchen Themen halten sollt, gehe ich davon aus, dass ihr vorher gelernt habt, was eine Turingmaschine und Persistenz im Allgemeinen ist.

Falls dies nicht der Fall ist: rausfinden, ohne das gehts nicht!

Ich versuche hier mal ganz kurz zu umreissen, was eine TM ist, was sie kann und wie sie funktioniert und versuche dann den Schritt zur PTM zu machen. Ich hab mir das auch grad nur im Paper in dem es zum ersten mal veröffentlicht wurde rausgesucht aber ich hab etwas erfahrung mit TMs und kann damit vielleicht ein wenig Licht in die Sache bringen.

Link zum Paper: Klick eventuell muss etwas runtergescrollt werden bis zum Paper "Persistent Turing Machines as a Model of Interactive Computation"

Eine TM ist ein sehr mächtiges rechenmodell.

Sie kann verstanden werden als die Kombination aus einem (nicht-)deterministischen Automaten
und einem endlos langem Bandspeicher mit einem Schreib-/Lesekopf.

Die eigentliche TM wird nun durch Programmcode definiert.
In jedem Rechenschritt liesst die TM das Zeichen an der aktuellen Bandposition und entscheidet anhand des gelesenen Zeichens
und des aktuellen Zustands des Automaten was zu tun ist.
Das kann sein:
1. schreibe ein Zeichen an aktuelle Kopfposition
und / oder
2. wechsel in einen anderen Zustand des Automaten
und / oder
3. eine Bewegung des S/L-Kopfes um eine Position nach Links oder Rechts oder keine Bewegung

Ein Turingprogramm ist also eine Menge von 5-Tupeln folgender Form:
(gelesenes Zeichen, aktueller Zustand, zu schreibendes Zeichen, neuer Zustand, Kopfbewegung)
oder äquivalent eine Funktion F: A x B -> A x B x D, wobei A das Bandalphabet, B die Menge der Zustände des Automaten und D die Menge der möglichen Kopfbewegungen (links, rechts, keine)

Nun lassen sich TMs auf verschiedene Arten erweitern, zum Beispiel durch das hinzufügen von weiteren Bändern.
Grundsätzlich wird das Modell der Turingmaschine durch das Hinzufügen von weiteren Bändern gleich dem normalen Band nicht stärker (Beweise hierzu finden sich in der Literatur).

Für die Persistenten TMs fügen wir nun ein weiteres Spezielles Band hinzu. Wir haben von Aussen keinerlei Zugriff auf dieses Band und können es nicht einsehen. Dieses neue Band wird von der TM intern verwaltet und beschrieben. Für einen Rechenschritt auf der PTM wird auch dieses persistente Band neben dem Automaten und dem gelesenen Zeichen einbezogen. Somit bekommt die TM ein Gedächtnis (persistenten Speicher). Bei der normalen TM war die Anzahl der Stati noch durch das endliche Bandalphabet und die endliche Zustandsmenge des Automaten begrenzt. Dadurch, dass wir keinen Einfluss auf das persistente Band haben erhalten wir zusätlich einen Faktor beliebiger (potentiell unendlicher) Länge. Somit ist auch die Anzahl der möglichen Maschinenzustände unendlich und es ergibt sich ein erweitertes Rechenmodell als das der normalen TM.


So viel erstmal zum Grundverständnis. Ich hoffe damit geholfen zu haben.

Ein einfaches Beispiel ist im oben verlinkten Paper in Abschnitt 2 zu finden.

Ja ich weis, das verlinkte Paper ist englisch, aber da du dich schon in der schule mit Turingmaschinenen auseinandersetzen darfst schliesse ich auf einen erweiterten Informatik oder Mathematikkurs und damit ein gewisses interesse auch mal auf diesem Gebiet zu studieren? In diesem Fall: gewöhn dich dran ;) Gleiches gilt für die meisten anderen Wissenschaften auch. Ich weis, wissenschaftliche Paper auf englisch können recht anstrengend sein, aber wenn mans einmal gemacht hat gehts einem leichter von der Hand. Und der mathematische Anteil in dem Paper ist auch wirklich überschaubar :)

It's not simple being cool, but it's cool being simple.
~ Simon Swaford ~

Did I listen to pop music because I was miserable?
Or was I miserable because I listened to pop music?
~ Rob Gordon/Flemming ~

Es haben sich bereits 3 registrierte Benutzer bedankt.

Benutzer, die sich für diesen Beitrag bedankt haben:

redox (12.12.2014), CeXti0n (12.12.2014), revO (12.12.2014)

CeXti0n

Amateur Spammer

  • »CeXti0n« ist der Autor dieses Themas

Beiträge: 60

Registrierungsdatum: 29. August 2012

Danksagungen: 25

  • Nachricht senden

3

Freitag, 12. Dezember 2014, 14:20

Vielen Dank! Hast mir sehr geholfen, ich habe wirklich lange gesucht aber genau das was du verlinkt hast nicht gefunden o.O
Es ist für nen Informatikgrundkurs und wir haben nicht wirklich irgendwas dazu gemacht im Vorfeld.
Klar war mir klar, dass es im Studium sehr englischlastig sein wird aber ich war echt extrem erschlagen von dem ganzen :D
Danke nochmal, so krieg ich das hin. .)

Es hat sich bereits 1 registrierter Benutzer bedankt.

Benutzer, die sich für diesen Beitrag bedankt haben:

blubb (25.12.2014)