4. Regeln, um einen Turing-Automat zu vereinfachen

Regeln, um einen Turing-Automat zu vereinfachen

  • O
    Banned

    Hallo Leute, hab in theoretischer Informatik nicht ganz so gut aufgepasst...

    Gibt es Regeln, um die Zustände (und Übergänge) eines Turing-Automats automatisch zu vereinfachen?

    Beispielweise:

    //-------CONFIGURATION
name: Finde die erste 1 und schiebe alle Weiteren weiter nach rechts, bis zur nächsten 0
init: q0
accept: q5

q0,0
q0,0,>

q0,1
q1,1,>

// End state
q0,_
q5,_,-

q1,1
q1,1,>

q1,0
q2,0,<

// End state
q1,_
q5,_,-

q2,1
q2,1,<

q2,0
q3,0,>

q2,_
q3,_,>

q3,0
q3,0,>

q3,1
q4,0,>

q4,1
q4,1,>

// End state
q4,0
q5,1,-

    wobei q5 ein akzeptierender Endzustand ist.

    ChatGPT hab ich noch nicht gefragt.

    0
  • P

    stellt man dazu nicht auch einfach diese wahrheitstabellen auf und optimiert diese dann mittels boolescher algebra bzw. kv-diagrammen?

    also ohne jetzt genau zu verstehen, was du da genau vorhast, würde ich bei "Finde die erste 1 und schiebe alle Weiteren weiter nach rechts, bis zur nächsten 0" genau so vorgehen.

    1
  • S

    Meine theoretische Informatik Vorlesungen sind jetzt schon ein paar Jahre her und an direkte Regeln kann ich mich nicht erinnern.

    Ich würde, wenn möglich, mir den Automaten aufmalen und und scharf drauf gucken 😉

    Ich weiß jetzt nicht, wie weit man mit den Regeln zum vereinfachen endlicher Automaten kommt.

    1 1 Reply
  • P

    also ich behaupte jetzt einfach mal, dass man aufgrund der tatsache, dass "echte" schaltungen (meistens) nur mit NAND umgesetzt werden, ziemlich weit kommt.

    0

  • @Schlangenmensch
    Ehrlich gesagt verstehe ich den Begriff Turing-Automat nicht ganz.

    Ich kenne nur Turing Maschinen und dies sind theoretische Konstrukte. Jede Turing Maschine hat ein unendlich langes Band unterteilt in Zellen, ein Schreibkopf kann die Zelle beschreiben (1) oder löschen (0) und einen Motor zum Bewegen des Bandes um eine Zelle.

    Ein Automat dagegen ist ein durchaus in der Praxis bekannt (siehe Zustandsdiagramm) und leicht verständlich. Und da bin ich ganz deiner Meinung, aufzeichnen, scharf ansehen und vereinfachen.

    Und nun kommt @Peter-Viehweger und meint das obige Programm stelle eine boolsche Formel dar.

    Und nun bin ich verwirrt. Was stellt das obige Programm nun dar? Die Syntax kenne ich nicht.

    0
    S
    O
    P
     3 Replies
  • S

    @Quiche-Lorraine Ich hatte in dem Fall Maschine und Automaten gleichgesetzt. Man kann ja schon Turing Maschinen konstruieren, die bestimmte Probleme abarbeiten und die Zustandsübergänge visuell darstellen, entweder als Graph, oder als Zustandsübergangstabelle (siehe z.B. https://de.wikipedia.org/wiki/Fleißiger_Biber)

    Mir ist die Syntax oben aber auch unbekannt.

    0 1 Reply
  • O
    Banned

    @Quiche-Lorraine

    Ich denke, eine Turing-Maschine ist ein formales Konzept, und ein Turing-Automat ist eine Umsetzung ebenjenes.

    Btw., ihr könntet den Code oben hier ausprobieren https://turingmachinesimulator.com/

    Sinnvolle Eingaben wären beispielsweise:
    0
    1
    00
    01
    10
    11
    usw.

    (wobei natürlich nur mit der Eingabe 10 etwas nach rechts geschoben werden kann... (denke ich))

    0
  • P

    @Quiche-Lorraine sagte in Regeln, um einen Turing-Automat zu vereinfachen:

    Und nun kommt @Peter-Viehweger und meint das obige Programm stelle eine boolsche Formel dar.

    im grunde lässt sich doch alles durch boolesche formeln ausdrücken: die cpu deines rechners, dieses forum, die zubereitung des abendessens.....

    0

  • @Schlangenmensch
    Ah danke für die Info, ich verstehe es nun.

    0
Log in to reply