Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

MaxKoch

Trainee

  • "MaxKoch" started this thread

Posts: 85

Date of registration: Oct 3rd 2008

1

Tuesday, August 31st 2010, 12:56pm

GThI Turingmaschine

Hey Leute,

ich hab da eine kleine Frage zu Turinmaschinen, speziell das Beispiel im Skript 7.2. Dort ist für jeden Fall, in dem das Wort nicht akzeptiert wird eine Regel eingebaut, die die TM in eine Endlosschleife versetzt. Ist das wirklich notwendig? Eigentlich dachte ich es reicht aus, wenn die TM einfach nicht mehr weiterarbeiten kann, falls es keine passende Regel gibt.

gruß max
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

2

Tuesday, August 31st 2010, 1:50pm

Ich habe das Beispiel gerade nicht parat, aber ich denke das folgende sollte Dir dennoch helfen. Wenn ich die Übergänge eine TM definiere und gewisse Übergänge wegfallen lasse, dann muss ich ja im Endeffekt (zwecks der Vollständigkeit und damit man argumentieren kann, was in solchen Fällen passiert) sagen, was für diese Fälle nun gilt. Wenn Du nun dazu schreibst, dass für alle nicht definierten Übergänge kein Endzustand angenommen wird und der Kopf sich nicht mehr bewegt, sind das im Endeffekt alles Endlosschleifen in diesen Situationen, die nicht zur Akzeptanz führen. Dieses von dir angesprochene Weiterarbeiten ist genau diese Endlosschleife.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message