{"id":466,"date":"2010-03-05T13:45:00","date_gmt":"2010-03-05T13:45:00","guid":{"rendered":"http:\/\/www.tutego.de\/blog\/javainsel\/?p=466"},"modified":"2010-03-05T13:45:00","modified_gmt":"2010-03-05T13:45:00","slug":"unentscheidbarkeit-fur-java-programmierer","status":"publish","type":"post","link":"https:\/\/www.tutego.de\/blog\/javainsel\/2010\/03\/unentscheidbarkeit-fur-java-programmierer\/","title":{"rendered":"Unentscheidbarkeit f\u00fcr Java-Programmierer"},"content":{"rendered":"<p>Es wird niemals eine Software geben, die sich eine andere Software anschaut und entscheidet, ob sie etwas bestimmtes macht.  <br \/>In der theoretischen Informatik gibt es das <b>Halteproblem<\/b>.  <br \/>Man kann <b>kein<\/b> Programm schreiben, das sich ein anderes <b>beliebiges <\/b>Programm anschaut und nach endlich vielen Schritten erkennt, ob es h\u00e4lt.  <br \/>(Es kann auch interpretiert werden, aber man hat nicht beliebig Zeit. Wenn ein Programm exakt 10 Jahre l\u00e4uft, kann man das nicht \u201etesten\u201c, da der Test ja auch 10 Jahren dauert.)  <br \/><b>Nehmen wir an<\/b> es gibt ein Programm  <br \/><b>bollean willStop( char[] program ) <\/b> <br \/>das entscheidet, ob ein anderes Programm endet.  <br \/>So sollte folgendes <b>true<\/b> ergeben:  <br \/><b>willStop(&#8222;return&#8220;); <\/b> <br \/><b>willStop(&#8222;for(int i=0;i&lt;100000000;i++)print(i);&#8220;); <\/b> <br \/>und folgendes <b>false<\/b><b>: <\/b> <br \/><b>willStop(&#8222;while(true);&#8220;); <\/b> <br \/>Eine <b>zweites Methode<\/b>:  <br \/><b>void reverser( char[] program ) { <\/b> <br \/><b> while ( willStop( program ) ) <\/b> <br \/><b>&nbsp; out.println( &#8222;willStop will stop&#8220; ); <\/b> <br \/><b>} <\/b> <br \/>Umgangssprachlich:  <br \/>&#8211; Wenn <b>willStop()<\/b> true liefert, endet <b>reverser()<\/b> nicht.  <br \/>&#8211; Wenn <b>willStop()<\/b> false liefert, endet <b>reserver()<\/b>.  <br \/>Frage: Was passiert bei folgendem Aufruf?  <br \/><b>void reverser( &#8222;void reverser(char[]\u2026&#8220; ); <\/b> <br \/>Ausgefaltet:  <br \/><b>void reverser( char[] program ) {<\/b> <br \/><b> while ( willStop( &#8222;void reverser(char[]\u2026&#8220; ) ) <\/b> <br \/><b>&nbsp; out.println( &#8222;willStop will stop&#8220; ); <\/b> <br \/><b>} <\/b> <br \/>Stoppt <b>reserver()<\/b>, hat <b>willStop(&#8222;void reserver\u2026&#8220;)<\/b> aber <b>false<\/b> gegeben. Aber warum ergibt <b>willStop()<\/b> dann <b>false<\/b>? Die Funktion stoppt doch? (Umgekehrtes gilt auch.)  <br \/>Durch diesen Widerspruch muss die Annahme falsch sein, dass es <b>willStop()<\/b> \u00fcberhaupt gibt. <br \/>&nbsp; <br \/><a href=\"http:\/\/www.tutego.de\/seminare\/java-schulung\/findbugs-pmd-checkstyle-jedepend.html\">Aus dem Seminar: Codeanalyse mit FindBugs, PMD, Checkstyle und JDepend<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Es wird niemals eine Software geben, die sich eine andere Software anschaut und entscheidet, ob sie etwas bestimmtes macht. In der theoretischen Informatik gibt es das Halteproblem. Man kann kein Programm schreiben, das sich ein anderes beliebiges Programm anschaut und nach endlich vielen Schritten erkennt, ob es h\u00e4lt. (Es kann auch interpretiert werden, aber man [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":"","_links_to":"","_links_to_target":""},"categories":[1],"tags":[],"class_list":["post-466","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/466","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/comments?post=466"}],"version-history":[{"count":0,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/466\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/media?parent=466"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/categories?post=466"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/tags?post=466"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}