Berechenbarkeit #04 - Turing-Maschinen (Beispiele)

[@maxwellenhofer7150]

Wichtigster Take Away aus diesem Video: "Irgendwann wird es dazu kommen, dass der Döner den Menschen ersetzen wird." :D

[@ogonkishi6403]

Der beste KZbinr für Theoretische Informatik!

[@updatedotexe]

Agreed

[@WindowsSchmindows]

Alle in der Bib dachten das ich durchdreh. @ 19:55 Vielen dank für diese tollen Videos!

[@christinaaigner3244]

Schön, dass es irgendwann dazu kommen wird, dass der Döner den Menschen ersetzen wird haha @19:55

[@peterweinzierl2307]

Danke, ich dachte schon ... :)

[@Felitsius]

Irgendwann wird es dazu kommen.. DAS DER DÖNNER DEN MENSCHEN ERSETZEN WIRD ich konnt nicht mehr XD Danke für die Videoserie!

[@arrayindexoutofboundsexcep1088]

Super Videos! Danke dafür! "Irgendwann wird es Mal dazu kommen, dass der Döner den Menschen ersetzen wird" :DD

[@damy2251]

Vielen Dank für deine tollen Videos, die sind echt super verständlich und auch ausführlich erklärt, so dass das Ganze sogar richtig interessant wird, plötzlich verstehe ich auch die Zusammenhänge und was das Ganze soll... Du ersparst vielen Menschen bestimmt viel Zeit und sehr viel Frustration beim durchgehen der Skripte. Ausserdem ist deine Stimme so schön beruhigend :D du wärst bestimmt ein toller Prof. =)

[@NLogSpace]

Vielen Dank für das Lob! Das freut mich riesig das zu lesen! :)

[@sergkapitan2578]

Mindblowing----so einfach erklärt !!!!

[@TheKurama9]

Tolles video. Ohne deine Erkärungen würde ich in diesem Fach komplett versagen. Vielen Dank dafür!

[@christianaza9443]

sehr gut erklärt , vielen Dank , dieses Video hat mir echt viel geholfen

[@nidalalsheikhali9217]

Vielen Dank für deine Bemühung 🌷🌷🌷

[@mquadrat9390]

Danke für das Video! War sehr hilfreich!

[@dmitrymezinov1696]

Super tolles video, hat mir die Hausarbeit gerettet :)

[@chrisaes3235]

6:20 Könnte man auf das Preprocessing (wo wir abchecken, dass erst a’s, dann b’s, dann c’s kommen) eigentlich auch verzichten? Besten Dank!! :)

[@florianbe5550]

super Video. Vielen Dank!

[@Sebastian-lz5ue]

@19:53 so trocken mit der kurzen Pause und dem Zeiger auf der Eingabe / dem Automat, als würdest du irgendetwas zeigen haha PS: Auch wenn uns, wie du meintest, erst einmal nicht interessiert, wie viele Zustände oder welche Strategie die DTM verwendet, dennoch eine Frage. Wie wichtig ist denn dann pre-processing überhaupt - könnte ich beim zweiten Beispiel nicht z.B. auch erst testen, ob beide Wörter vor und hinter # gleich lang sind? Und wie würde man Effizienz in Bezug auf Turingmaschinen überhaupt definieren? - In der Anzahl der Zustände oder der Arbeitsschritte?

[@NLogSpace]

Effizienz kann man auf verschiedene Arten messen. In der Komplexitätstheorie, zu der auch bald Videos kommen, geht es genau um solche Fragen nach der Effizienz von Algorithmen. Am meisten interessiert man sich für Zeitkomplexität und Platzkomplexität. Bei der Turing-Maschine wäre Zeitkomplexität, wie viele Arbeitsschritte sie macht und Platzkomplexität, wie viele Felder auf dem Arbeitsband benötigt werden. Für die Anzahl der Zustände interessiert man sich eher weniger, da die Größe eines Computerprogramms (=Größe des Quelltextes) normalerweise nicht so relevant ist wie die Ausführungszeit (=Zeitkomplexität) oder der Speicherverbrauch (=Platzkomplexität). Dass die Länge der Worte auf beiden Seiten der Raute gleich sein muss, das folgt aus dem späteren Teil der Maschine: Falls das Wort links und rechts der Raute ungleich lang ist, dann wird die Maschine in einem der Zustände mit einer X/X/r-Schleife stecken bleiben. Allerdings: Wenn ich die Maschine nochmal ansehe habe ich das Gefühl, das pre-processing war gar nicht notwendig. Ich wollte mit dem pre-processing nur erst mal alle Wörter ausschließen, die nicht genau eine Raute haben. Aber die werden auch später dadurch ausgeschlossen, dass man am Ende nur über genau eine Raute laufen kann, um zum Endzustand zu kommen. Aber wie gesagt, effizient ist jetzt erst mal egal. :D

[@Sebastian-lz5ue]

Gut, man könnte das pre-processing vielleicht als eine Art von Fehler-Abfang sehen. Eher als Umsetzung eines Computerprogramms, sodass z.B. der user darauf hingewiesen wird, einen richtigen input zu geben (wie sinnvoll das ist, ist fraglich^^ aber ist eine ähnliche Parallele wie die equals-Methode in einer Programmiersprache. Zeigt vielleicht, dass man auch solche Konstrukte mit einer TM umsetzten kann). Ein anderer Nutze fällt mir im Moment nicht ein. Denn wenn sich die Ausführungszeit / Zeitkomplexität am worst-case orientiert, ist es ja letztendlich egal ob ich sofort einige Eingaben entscheiden kann oder nicht.

[@larsthedestroyer7485]

19:53 "und irgendwann, wird es mal dazu kommen, dass der Döner den Menschen ersetzen wird"

[@iksel9166]

da habe ich wirklich erstmal angehalten, die stelle wiederholt und geschaut ob jemand kommentiert hat, weil das mehr nach einem Streich ausschaut als geplant

[@Blizzalord]

Müssen Turingmaschinen an den Anfang zurück für das Ergebnis, oder kann ich wenn ich als Input abc habe einfach einmal das Band durchlaufen, und sagen wenn ich ein Blank sehe gehe ich auf den Akzeptierten Endzustand?

[@_n_bl_3998]

wie würde eine Turingmaschine aussehen, bei der vorgegeben ist, wie nachher das Band auszusehen hat? Beispielsweise wie bei: a^n1a^m nach a^(n*m). Eingabealphabet ist {0,1,a}

[@simon-wt]

Hi, erst einmal vielen Dank für deine Videos. Super simpel erklärt und leicht verständlich. Ein Professor mit deinem Erklärstil wäre absolut wünschenswert :D. Kurze Frage zum 2. Beispiel: Erlaubt die Sprache auch leere Wörter? Glaube, dass {a,b}* auch das leere Element abbilden kann. Somit müsste man den Automaten noch ein wenig erweitern oder? MfG Edit: Ok habe gerade mal "#" in deinen Automaten bei dem Turingmachinesimulator gesteckt und da erkennt es das Wort doch. Dann habe ich wohl einen Denkfehler, konnte ich aus dem Automaten im Video nicht rauslesen. Edit2: Fehlt da nicht eigentlich im 4. Zustand ein #,#,n Übergang auf den akzeptierenden Übergang?

[@NLogSpace]

Ich denke da fehlt kein (#,#,n)-Übergang: Man nimmt stattdessen den (#,#,r) in den nächsten Zustand und kann von dort in den Endzustand, oder?

[@simon-wt]

@@NLogSpace Ach ups, als ich mir das überlegt habe, bin ich nochmal zurück im Video gegangen und habe dann den nicht vollendeten Automaten angeschaut und somit falsch interpretiert. Mein Fehler. Passt, dankeschön.

[@alvaro1379]

Von dem ersten Beispiel. Ist der erste Teil wenn man nach rechts geht bis zum Ende nicht unnötig? Können wir nicht nach dem ersten Zustand schon anfangen X's zu schreiben? Weil wir gehen einmal komplett nach rechts und dann nach links wieder bis zum Anfang... Wir können auch einfach ein Blank nach dem ersten Zustand lesen indem wir nach links gehen und dann nach rechts gehen und wo die Buchstaben sind X's schreiben. Oder irre ich mich? Danke für das Video.

[@Ozay1998]

Sehe nur das Beispiel für (a^n b^n) aber was wäre bei a^n, b^m, c^n, d^m? Haben es als Hausaufgabe und mir fällt einfach nicht ein wie man das definieren könnte in einer einzigen Maschine

[@lupinholmes6167]

Ich weiß, das kommt sehr spät, aber ich würde für a/c und b/d zwei Durchgänge machen. Zuerst markiert man die a's und c's, so wie im Video, danach geht man an den Anfang zurück und markiert die b's und d's.

[@michaelperkins1119]

Dann ist "der Gerät" ja eigentlich auch eine Turing-Maschine 😅 19:55

[@perkaholicx154]

Was muss man machen wenn man 0^n 1^k 0^n gegeben hat, und es soll bei der Ausgabe 0^n 1^2k 0^n rauskommen?

[@ruhrpott1268]

aabbbccc wird aber von dieser Turingmaschine nicht akzeptiert, oder? deine Turingmaschine also die erste ist nur für Sprachen berechenbar, wo n bei allen Eingabesymbolen gleich ist. aaabbbccc kommt in den Endzustand aber aabbbbccc z.B nicht. Edit: okay, ich hatte nicht weitergeschaut gehabt.

[@gigi19994]

Warum genau müssen wir nochmal markieren? Wenn ich z. B. für das Wort I^2 eine 2-Band TM bauen muss, dann enthält das 1. Band nur die Striche also die Eingabe (zB IIII) . Das 2. Band ist zu Beginn leer und enthält am Ende nur die Ausgabe (IIII) . Wir müssen dann das 1. Band leeren, dann würde es doch ausreichen, dass wir beim lesen des letzten Striches auf Band 1, diesen durch ein Blank ersetzten und nach links gehen. Solange bis wir alle Striche auf Band 1 durch ein Blank ersetzt haben und auf Band 2 nur die Striche stehen haben. Dann lassen wir die TM stoppen und gehen in einen akzeptierenden Zustand.

[@gigi19994]

Ich meinte I^(n^2)

[@wildebeest1454]

Mal ne Frage: Wozu braucht man bei dem Check für L={a^n, b^n, c^n, | n >= 1} das Preprocessing? Ich hab bei mir eine weitaus kompaktere Turingmaschine gebaut, die mMn den selben Effekt hat, aber schneller dabei ist. Da fehlt aber eben das Preprocessing.

[@NLogSpace]

Hätten wir das Preprocessing weggelassen, dann würden wir auch das Wort abcabc akzeptieren. Aber natürlich gibt es viele verschiedene Möglichkeiten diese Sprache mit einer DTM zu akzeptieren, ich habe hier nur eine Möglichkeit gezeigt. Z.B. könnte man sich das Preprocessing, wenn man die "durchgestrichenen" Symbole nicht alle durch das gleiche Symbol ersetzt, sondern z.B. a durch X, b durch Y und c durch Z. Und wenn man dann ein a gefunden hat, darf man nur über X, dann über Y laufen und muss dann ein b finden usw.

[@wildebeest1454]

@@NLogSpace Wow, danke für die schnelle Antwort! Korrektur: Nach dem c akzeptiert er nur blank oder c. Ich hab auf den falschen Zustand geguckt. :D Er endet aber bei abcabc dennoch in einem nicht akzeptierenden Zustand.

[@NLogSpace]

@@wildebeest1454 Also nutzt du weiterhin nur ein Symbol für durchgestrichene Zeichen? Wie ist es dann mit dem Wort ababcc?

[@wildebeest1454]

@@NLogSpace Bei meiner DTM gibt es 6 Zustände. Bei den Zuständen gilt(Ich hoffe mal, ich begehen hiermit nicht zu viele Formsünden): q0(Start) a | X | r -> q1, X | X | r -> q0, _ | _ | n -> q5 q1 X | X | r -> q1, a | a | r -> q1, b | X | r -> q2 q2 X | X | r -> q2, b | b | r -> q2, c | X | r -> q3 q3 c | c | r -> q3, _ | _ | l -> q4 q4 X | X | l -> q4, a | a | l -> q4, b | b | l -> q4, c | c | l -> q4, _ | _ | r -> q0 q5 Akzeptanz/Endzustand Ich hoffe, das ist so überhaupt erlaubt. Ich lerne das hier gerade mehr für mich. In der Uni ist das erst in ein paar Semestern dran.

[@wildebeest1454]

Dementsprechend würde das bei ababcc schon bei dem zweiten a aufhören.

[@crackindenpockets6211]

Ist die Turing Maschine beim letzten Beispiel nicht nichtdeterministisch?

[@NLogSpace]

Ich denke nicht. Wie kommst Du darauf?

[@simonmayrhofer]

Hat jemand eine Ahnung wie man Binärzahlen auf einer Turingmaschine addieren kann?

[@arnoclaude317]

Kennen Sie zufällig den Prof. Tobias Nipkow?

[@NLogSpace]

Nein, den kenne ich nicht.

[@maggus_1]

TUM

[@arnoclaude317]

@@maggus_1 Richtig :D du auch?

[@maggus_1]

Ja. Ich wünsche morgen Viel Erfolg!

[@arnoclaude317]

@@maggus_1 Danke! Wird ne schwere Geburt. Dir auch viel Erfolg!

[@tonikaiser2823]

Aber eines kapiere ich nicht, du sprachst ja darüber das dieses Teil alles kann was ein Computer auch kann. Aber dieses Ding ist ja so langsam, das kann ja mitnichten irgendein Computerspiel laufen lassen oder?

[@NLogSpace]

Die Aussage ist zunächst mal so gemeint: Jede Funktion, die z.B. einen String entgegen nimmt und einen Boolean zurück gibt, die man in deiner Lieblings-Programmiersprache schreiben kann, kann man auch mit einer Turing-Maschine programmieren (akzeptieren ist true, verwerfen ist false). Über den Zeitverbrauch ist erstmal nichts gesagt. Allerdings besagt die "erweiterte Church-Turing-These", dass sich der Zeitverbrauch auch nicht großartig unterscheidet, nämlich dass eine Turingmaschine "nur" polynomiell viel langsamer ist. In der Praxis würde das allerdings doch einen Unterschied machen, denn wenn ein Computer z.B. 1.000.000 Schritte braucht, um das Ergebnis zu berechnen, bräuchte eine Turing-Maschine vielleicht quadratisch, also 1.000.000.000.000 viele Schritte, was schon deutlich länger wäre!

[@tonikaiser2823]

@@NLogSpace ok verstehe ich schon, vielen Dank aber was ist genau eine polinomfunktion, das ist ja irgendwas hoch irgendwas? Ab wann ist etwas nicht mehr polynomiell? Ist das das mit den Quantencomputern? (ich studiere seit 2 Monaten Informatik und ich kenne mich mit dem noch nicht so aus)

[@NLogSpace]

Ein Polynom ist z.B. x^3+3x^2+5x+20, also Potenzen der Variable aufsummiert, ggf. noch mit Koeffizienten multipliziert. Das sollte eigentlich aus der Schule bekannt sein, oder? Eine Funktion, die schneller als jedes Polynom wächst, wäre z.B. 2^x, also eine exponentielle Funktion. (Und mit Quantencomputern hat das erstmal nichts zu tun.)

[@tonikaiser2823]

@@NLogSpace Ja schon, nur das wort nicht, also Polynom ist dann wenn keine Variable in der Hochzahl steht oder?

[@NLogSpace]

Genau.

[@mistersinister93]

"früher hat man es auch Raute genannt" :D

[@TechWorldWithSerdar]

an dem Punkt wo Döner, Menschen ersetzt 😆