Die fleißigen Biber der Informatik

Kommentare (14)

1. #1 rolak

   21. Juni 2016

   Heidewitzka – nach dem Wechsel zur Informatik wurde ich binnen eines Jahres eingezogen, konnte aber die Panzergrenadiererei durch eine die Rückstellung abschließende Verhandlung in den schon vorher avisierten Zivildienst umtauschen. So gings dann 2.Hälfte 80er mit Moped, Baß, Rechner und Kassettensammlung in die Jugendherberge — und Elektor veranstaltete irgendwann einen Wettbewerb über iirc 5zuständige Biber. Also wurde Donnerstags eine Turingmaschine geschrieben und ein wenig probiert, Freitags ein Programm, das die TuringBiber durchtestet – und beim Überlegen, wie denn die Maschinen am günstigsten aufzählbar seien dämmerte mir, daß der Ansatz dem berühmten Widerspruchsbeweis des Halteproblems verdächtig ähnelte…

   Also Samstag morgens in die Bibliothek, ahja, eines der nichthaltenden Probleme. Dann wars ab nachmittags doch wesentlich unbeschwerter auf der Party, auch wenn dadurch die Nacht auf Montag unangenehm kurz wurde ;‑)

2. #2 Laie

   22. Juni 2016

   Das Problem der Berechenbarkeit ließe sich nicht mal mit unendlicher Zeit(dauer) lösen, da dadurch nicht nur die Stromrechnung ins Unermessliche steigt, sondern die Turinmaschine irgendwann dazwischen (vor unendlich) kaputtgeht, und wer könnte schon das Servicepersonal für eine Ewigkeit bereitstellen, und wer zahl den Strom? 🙂

3. #3 schlappohr

   22. Juni 2016

   “Solange der Biber Einsen schreibt, woher sollen wir wissen, ob er noch anhalten wird oder niemals stoppt?”

   Hier habe ein bisschen gestutzt. Du bringst hier den Aspekt der Zeit ins Spiel, aber im Turing-Modell existiert eigentlich keine Zeit, oder? Ist schon ein paar Jahre her, aber soweit ich mich erinnere, ist eine theoretische TM gewissermaßen unendlich schnell, d.h. sie terminiert sofort, und wenn sie nicht sofort terminiert, dann tut sie es niemals. Es ergibt also eigentlich keinen Sinn, auf irgendetwas zu warten.
   Das Problem ist eigentlich das folgende: Der hypothetische Über-Algorithmus ist selbst ein Turing-Programm, dass nacheinander alle n-state-Turingprogramme durchrechnet. Wenn eines dieser Programme nicht terminiert, dann terminiert auch der Über-Algorithmus nicht, d.h. er kann anschließend keine Biber-Einsen mehr zählen und liefert somit kein Ergebnis. Vermutlich meinst Du genau das.

   • #4 rolak

     22. Juni 2016

     den Aspekt der Zeit ins Spiel, aber im Turing-Modell existiert eigentlich keine Zeit, oder?

     Zeiteinheit=1Takt bzw ein Zustandswechsel, schlappohr, und zwar unabhängig davon, wie lange nun ein Takt dauert (also inkl 0). Relevant ist zumeist tatsächlich nur die Antwort auf die Frage, ob das Teil beim gegebenen Input stoppt oder ewig weiterklappert – beim EffizienzVergleich zweier Algorithmen allerdings ist die ~Zeit wesentlich.

4. #5 Dr. Webbaer

   22. Juni 2016

   Howdy!

   Nur ein paar Anmerkungen:
   1.) Mathematiker sind bereits ‘faul’ und ihnen zuvorkommend bereits einige Philosophen, wobei sie nicht wirklich ‘faul’ sind, sondern sparsam.
   2.) Hierzu – ‘Kann man alle Probleme mit dem Computer lösen?’ -. also Probleme, sollten sie weltlicher oder im Speziellen sozialer Art sein, können durch Software nicht gelöst, sondern nur unterstützt werden in ihrer Bearbeitung bis ‘Lösung’.
   Auch rein mathematisch oder weitergehend tautologische Probleme, also nicht-weltliche, können regelmäßig vom Rechner und mit Software nicht gelöst werden.
   3.) Das ‘Halteproblem’ wird im Rahmen eines sozusagen robusten Software-Einsatzes regelmäßig umgangen, indem eine Routine austimen kann, dann sozusagen extern gestoppt wird, natürlich ohne (positives) Ergebnis.

   MFG + viel Erfolg!
   Dr. Webbaer

5. #6 kalo

   22. Juni 2016

   Müßte nicht in der Zustandstabelle im gezeigten Schema unter “Bewegung” in der zweiten Zeile “nach links” stehen? Sonst hält doch dieser Algorithmus nie! – Oder verstehe ich das hier unterstellte Zustandskonzept nicht?

   • #7 Franziska Hufsky

     22. Juni 2016

     Die Abbildung stimmt. Hier die Arbeitsweise:
     

6. #8 kalo

   22. Juni 2016

   Ah, ja. Hatte nicht zu Ende gedacht.

7. #9 Braunschweiger

   22. Juni 2016

   @Laie ~#2:
   Das war Satire oder verar…nd gemeint, oder?
   Eine Turingmaschine geht nicht kaputt und verbraucht keinen Strom, und eigentlich auch keine Zeit. Ich schreibe das, weil ich unterstreichen möchte, dass so eine Turingmaschine ein theoretisches Modell ist.

   @schlappohr:
   Eigentlich hast du recht, und der Begriff einer “Zeit” ist meiner Meinung nach eine praktische Vereinfachung. Eine Turingmaschine produziert eine Folge von Zuständen (die, die sie durchläuft — neben der Bandausgabe), die entweder beim Stopp abbricht und endlich ist, oder aber die unendlich ist. Egal, welche Zeitspanne ungleich 0 du einem Schritt zuordnest: wenn die Verarbeitung nicht abbricht, läuft sie dann unendlich. Unendliche Folgen sind mathematische Objekte.

   Das Problem mit der Zustandsfolge ist, dass man eine wirklich unendliche und explizit hingeschriebene Zustandsfolge nicht handhaben könnte. Man kann sie ja eben nicht in endlicher Zeit schreiben oder lesen. Also behilft man sich mit der Vorstellung, dass eine Turingmaschine eine solche unendliche Folge “gerade eben produziert”, und man sieht zumindest, dass noch nicht gestoppt wurde. Es ist aber unzulässig mit Zeit zu argumentieren (“wenn die TM in x Sekunden nicht fertig ist…”), weil immer Fälle denkbar sind, in denen trotz endlicher Folge bis x noch kein Abbruch erfolgt, egal welche Größe x hat.

8. #10 Laie

   23. Juni 2016

   @Braunschweiger
   Weder, noch!

   … der Witz oben bei mir soll sein, eine Turingmaschine kann man ja nicht wirklich (sinnvoll mechanisch)* nachbauen – da es eine theoretisches Modell ist -, jedoch in Computern simulierbar, bzw. fast-Äquivalenz zu bestehenden Computern herstellbar ist bezüglich Berechenbarkeit, die benötigen Strom und Rechenzeit, sind also nicht so schnell. Und einen unendlichen Speicher gibts halt auch nicht in Computern…
   Geht denn das nicht aus dem Geschriebenen deutlichst hervor?

   * Es hat sogar jemand mal aus Liebe zur Sache eine mechanische Turing-Maschine gebaut, jedoch mit endlichem Band.

   Anderes Beispiel: Verschicke einen Witz mit der Deutschen Bahn: Problem, er kommt nicht an.

9. #11 schlappohr

   23. Juni 2016

   ” Also behilft man sich mit der Vorstellung, dass eine Turingmaschine eine solche unendliche Folge “gerade eben produziert”, und man sieht zumindest, dass noch nicht gestoppt wurde. ”

   Das sieht man von “außen” als Beobachter, aber der Beobachter ist nicht Teil der Turingmaschine und auch nicht Teil des Beweises. Die TM selbst kann hingegen nur feststellen, dass ein TM-Programm terminiert, aber nicht, dass es nicht terminiert. In einer “echten” Software würde man sagen, dass der Funktionsaufruf nicht zurück kommt.

   Zu meiner Schande muss ich gestehen, dass ich das Vordiplom in Theoretischer Informatik im ersten Versuch versemmelt habe und die Prüfung nach einem Semester bei einem anderen Lehrstuhl wiederholen musste. Dieser Professor hat anstelle der TM die Klasse der µ-rekursiven Funktionen bevorzugt. im Nachhinein war es sehr hilfreich, beides kennen zu lernen. Diese Modelle sind äquivalent, aber irgendwie kam ich mit den µ-rek. Funktionen besser zurecht (was sich auch in einem recht gut bestandenen VDP zeigte). Die Frage, wann eine Maschine mit einer Berechnung fertig wird, stellt sich hier nicht, weil es keine Maschine gibt 🙂 Zudem fand ich die Vorstellung von einer Maschine, die unendlich schnell auf einem unendlich langen Papierstreifen schreibt, irgendwie unbehaglich.

10. #12 Was steckt drin im Molekül? – BioInfoWelten

    21. Juli 2016

    […] wenn ihr die Münzen vorher sortiert. Aber wie gesagt, ihr seid faul (vermutlich seid ihr Informatiker). Also brauchen wir einen Algorithmus, der uns das gemessene Gewicht zerlegt, in die Anzahl der […]

11. #13 Von leichten, schweren und vollständigen Problemen – BioInfoWelten

    9. August 2016

    […] ein paar Wochen habe ich euch das Konzept der Berechenbarkeit in der Informatik vorgestellt. Damit lässt sich die Frage beantworten, ob ein Problem berechenbar ist oder nicht. […]

12. #14 Die fleißigen Biber der Informatik | Bioinformatik

    18. Oktober 2016

    […] Beitrag auf ScienceBlogs lesen. […]