Dumme Fragen - es gibt sie DOCH!

Original von Pan
Wieso liegt das Halteproblem nicht in Chomsyk-1? Sprachen in Chomsky-1 sind entscheidbar, das Halteproblem ist nicht entscheidbar, sondern nur semi-entscheidbar (was wiederum eine Eigenschaft von Chomsky-0 Sprachen ist).

Hm, die Erklärung klingt so ein bisschen nach "weil das so ist". xD

Na ja, ich glaube nicht, dass ich dieses Material so richtig verstehe, aber vielleicht passiert es ja doch einmal … irgendwann. xD Vielen Dank jedenfalls.

BTW: PN für dich.

Ark

Original von Happy_Mask_Shop
War der 11 September 2001 jetz eigentlich das Werk von Terroristen oder der US Behörde?

Ich war's.

Nein, im Ernst, was ist das für eine Frage?

Die waren's natürlich, no shit Sherlock. ;)
Und zurück zum Thema, Freunde der Sonne. Ich lösche ungern Spam.

Hm, noch eine Frage zur Chomsky-Hierarchie:

Typ 3 unterliegt den Beschränkungen von Typ 2 und hat darüber hinaus noch weitere Beschränkungen. Gleiches gilt ja dann auch für Typ 2 gegenüber Typ 1 und Typ 1 gegenüber Typ 0, oder?

Weiter: Der Automat zu Typ 2 (Kellerautomat) hat einen Keller. Der Automat zu Typ 1 benötigt linear durch die Eingabe beschränkt viel Speicherplatz. Wenn obige Aussagen stimmen, müsste doch auch die Verwendung des Kellers durch den Kellerautomaten linear beschränkt sein, oder?

Ark

Jep, CH-0 enthaelt alle andren CH-Typen. Da gibt's auch son huebsches Bildchen... Z.B. hier.
CH-3 ⊆ CH-2 ⊆ CH-1 ⊆ CH-0

Original von Ark
Hm, die Erklärung klingt so ein bisschen nach "weil das so ist". xD

Naja, ich kann dir hier halt nicht 3/4 meiner Theoretischen Informatik Vorlesung innerhalb eines Posts zusammenfassen Da musst du dich dann schon selbst etwas einlesen

Kurz zur Semi-Entscheidbarkeit vom Halteproblem: Es ist unentscheidbar, ob ein Programm irgendwann hält, daher kann man nicht sagen, ob es jemals halten wird - außer natürlich, wenn das Programm hält! D.h. man kann die Programme, die nach einer endlichen Anzahl von Schritten halten "rekursiv aufzählen". Man lässt einfach alle Programme immer einen Schritt laufen, wenn eins davon hält -> Ausgabe "Programm So Und So hält". Das macht man dann halt ewig weiter. Somit kann man dann haltendene Programme aufzählen. Wenn aber ein Programm auch nach 50 Jahren immer noch nicht hält, kann man noch lange nicht sagen, ob es nicht hält oder doch noch irgendwann halten würde - es könnte ja evtl. irgendwann noch in 5 Milliarden Jahren halten. Man weis es nicht.

Im konkreten Fall kann man natürlich oft schon entscheiden, ob ein Programm irgendwann hält, oder nicht, indem man sich halt den "Code" anguckt. Aber es geht halt darum, eine Funktion halt() zu haben, der man ein beliebiges Programm übergibt und die dann Ausgeben würde "Ja, Programm hält irgendwann" oder "Nein, Programm hält nie". halt() ist aber nicht berechenbar... der Beweis ist eigentlich recht kurz und die Idee ziemlich genial - aber auch gerade deswegen etwas trickreich und nicht so einfach zu verstehen. Den Beweis findet man z.B. auf Wikipedia, kannste dir ja mal angucken.

Zu der Kellerautomatfrage: Nein, der Keller ist rein prinzipiell nicht beschränkt (also Unendlich groß), aber wenn ich das richtig in Erinnerung habe, ist wiederum das, was effektiv auf den Keller geschrieben werden kann linear durch die Eingabe abgeschätzt werden. Außerdem kann man zeigen, dass LBAs PDAs simulieren können (spontan habe ich z.B. hier einen Beweis dazu gefunden: Klick)

Und die andere Frage hat Luna ja schon treffend beantwortet - aber dass hättest du eigentlich wissen sollen, dass hab ich dir doch schonmal erklärt

Das mit dem Halteproblem ist mir schon klar. Tut mir Leid, wenn ich das nicht schon vorher sagte, dann hätte die Antwort auch wesentlich kürzer ausfallen können und ich nicht deine kostbare Zeit zu sehr in Anspruch genommen. Aber ich meine, mir jetzt mehr unter "rekursiv aufzählbar" (in diesem Zusammenhang) vorstellen zu können. Vielen Dank dafür.

Worauf ich mit der Frage eigentlich hinauswollte, betrifft die Möglichkeit, in Typ-0-Grammatiken Regeln aufzunehmen, die auf der rechten Seite kürzer sind als auf der linken. Bildlich stelle ich mir diesen Umstand so vor, dass es möglich ist, dass der Text beim Schreiben kürzer und beim Lesen länger werden kann. (Man entschuldige dabei alle Unwissenschaftlichkeiten; mir geht es darum, ein prinzipielles Verständnis durch Anschaulichkeit zu entwickeln.) Aber was kann ich dann damit machen? Oder besser: Was kann man beispielsweise mit diesen Regeln berechnen, was man mit anderen Typen nicht berechnen kann? Auf welche Art und Weise bewirkt diese "Verkürzung", dass mehr berechnet werden kann als vorher? Ist z.B. für eine Addition Turing-Vollständigkeit von Nöten? Wenn ja: wie sollten solche Regeln aussehen, und wie spielen sie so zusammen, dass sie eine Addition nachahmen?

Zum Link: Danke, ich werde es mir mal durchlesen und im Hinterkopf behalten. Teilweise kann ich mir ja darunter sogar schon etwas vorstellen.

Wenn ich das so weit richtig verstanden habe, ist ein LBA ein PDA, der um die Fähigkeit erweitert wurde, beliebige Manipulationen innerhalb des Stapels vorzunehmen, und eben nicht nur an einem Ende des Stapels operieren kann. Ist das so korrekt?

Ark

Theoretische Informatik != anschaulich... Deswegen heisst's "theoretisch". xD

... was IST theoretische Informatik? xD;
(Spezieller Schwierigkeitsgrad: Bitte so erklären, dass ein Noob wie ich es verstehe. xD;; )

de.wikipedia.org/wiki/Theoretische_Informatik
xD

Sorry, keine Zeit, es naeher zu erklaeren bzw. es zu versuchen, darf morgen fuer die Uni viel zu frueh aufstehen und muss ins Bett... xD Ich geh mal Pan rufen, vielleicht mag der.

Klar will ich

Ich probiers mal. Erstmal sollte man sich darüber klar werden, dass es in der Informatik nicht darum geht, möglichst viele Programmiersprachen zu lernen, tolle Websites zu basteln, die neueste Hardware zu kennen oder sonstige computertechnische Problemchen lösen zu können. Ein Informatiker ist kein Computertechniker Die meisten Informatiker können sowas zwar, aber dass ist eher ein "Abfallprodukt", sag ich mal
Nettes Zitat von Dijkstra (sehr bekannter Informatiker): "Informatik hat soviel mit Computern zu tun, wie Astrologie mit Teleskopen".
Zwar gibt es auch sehr "computerzentrierte" Themengebiete, aber die machen nur einen Bruchteil aus. Der Computer ist eine Anwendung der Informatik, mehr nicht. Insofern ist die Informatik wichtig für den Computer - aber nicht andersrum Alles was der Computer berechnen kann, könnte genauso gut ein Mensch berechnen. Der Computer kanns blos schneller.

Um was gehts denn dann? Großteilig darum Probleme zu lösen. Das hört sich nach so wenig an, aber ist eigentlich riesiges Feld. Angefangen bei ganz praktischen Dingen, wie z.B. "Wie baue ich ein Betriebssystem?", über "Wie plant man die Entwicklung von Software so, dass der Entwicklungsprozess am effektivsten abläuft?" bis halt hin zur theoretischen Informatik.

Um was gehts jetzt in der theoretischen Informatik? Gute Frage
In der theoretischen Informatik geht es darum, herauszufinden, was überhaupt theoretisch berechenbar ist und wenn etwas berechenbar ist, wie effizient man es berechnen kann. Der Begriff "Algorithmus" ist dabei ganz zentral, daher erklär ich erstmal das. Was ist also ein Algorithmus? Eigentlich nichts anderes, als ein Kochrezept, eine Anweisung von Tätigkeiten, die man in bestimmter Abfolge ausführt, um hinterher ein bestimmtes Ergebnis zu erzielen.
Algorithmen begegnen uns überall. Man kann z.B. ein Musikstück als Algorithmus ansehen, denn die Noten geben uns den zeitlichen und tonalen Ablauf größtenteils vor. Oder halt ganz klassisch ein Kochrezept. "Füge Zutat Y hinzu, rühre X mal um, erhitze bei ABC°C ca. T Minuten..."
Ich schreib statt Algorithmus aber hier mal lieber "Lösungsverfahren" - machts vielleicht klarer

Was heisst jetzt ein Problem ist berechenbar? Hier geht es darum, zu einem gegebenen Problem ein Lösungsverfahren zu finden. Und zwar von theoretischer Sicht aus, entfernt vom Computer. Die Erkenntnisse der theoretischen Informatik sind allgemeingültig. Man benutzt dazu einige theortische "Maschinen", die nicht existieren und auch nur teilweise gebaut werden können. Es ist ein theoretischen Maschinenmodell, dass im Großteil sogar wesentlich mächtiger ist, als die Computer, die wir heutzutage zur Verfügung haben (es ist sogar so, dass Computer auf dieser Hierarchie sogar ganz unten anzusiedeln sind).

Wenn sich herausstellen sollte, dass ein Problem nicht berechenbar ist, dann wird es niemals eine Maschine geben, die das Problem lösen kann, ganz egal wie schnell der Prozessor ist oder wieviel Speicher zur Verfügung steht.

Ein ganz konkretes Beispiel, folgendes Problem: Wir wollen wissen, ob es ein Programm geben kann, dass jeden erdenklichen Virus erkennen kann. Also einen "universalen" Virenscanner. Wie sich herausgestellt hat, kann es so einen Virenscanner nicht geben. Wieso ist schwierig zu erklären, wenn man keine Vorkenntnisse hat. Ganz grob: Würde es so einen Virenscanner geben (rein hypothetisch - denn es kann ich nicht geben ), dann könnte man unter Verwendung dieses Virenscanners einen neuren Virus basteln, der so gestaltet ist, dass der "universelle Virenscanner" bei seiner Überprüfung sagen würde: "Nein, kein Virus." Der Virus verwendet sozusagen den Virenscanner selbst, um den Virenscanner auszutricksen. Das wäre ein offensichtlicher Widerspruch zur Annahme, dass der Virenscanner alle Viren erkennen kann.

Ein ähnliches Problem ist das Halteproblem, dass ist jetzt schon von theoretischerer Natur. Wenn man sich beim Programmieren ungeschickt anstellt, kann es passieren, dass sich ein Programm für immer und ewig im Kreis dreht und es nie zum Ende kommt. Das ist ungefähr so, wie wenn man im Kochenrezept beim "Rühren sie 3 Mal um" hängen bleibt und unendlich lange umrührt. Sowas will man natürlich nicht, also hat man sich die Frage gestellt: Kann es ein Programm HALT geben, dass für jedes andere Programm entscheiden kann, ob dieses Programm irgendwann terminiert, oder ob es in einer solchen Endlosschleife stecken bleiben wird? Auch hier lautet die Antwort: Sowas kann es nicht geben! Argumentation ist ähnlich wie beim Virenscanner: Wenn es das Programm HALT geben würde, könnte man es selbst wieder verwenden um es selbst auszutricksen und die Antwort "Ja, es hält" zu bekommen - obwohl es nie hält.

Natürlich findet man aber auch oft genug herraus, dass Probleme lösbar sind.
Und was hätte man gerne, wenn ein Problem lösbar ist? Genau, dass es möglichst schnell und effektiv gelöst werden kann. Unsere Computer werden zwar immer schneller, aber wenn ein Problem sowieso schon schnell gelöst werden kann, dann hat das immer Vorteile.

Das Problem hierbei ist wiederum: Man muss erstmal einen Weg finden, dass Problem effizient zu lösen. Und was heisst überhaupt effizient? (Das möchte ich hier aber mal nicht näher ausführen, weil das doch recht kompliziert wird). Es gibt die sogenannte Klompexitätstheorie, bei der man wiederum ganz theoretisch Probleme anhand ihrer Komplexität in verschiedene Klassen einteilen kann. So wie du vielleicht in deinem Schrank ein Fach für T-Shirts, eins für Unterwäsche usw. hast, hat man hier "Fächer" für verschiedene Arten von Problemen.
Man kann dann z.B. sowas wie "Wenn ich Problem A lösen kann, dann kann ich mein Lösungsverfahren auch benutzen um ein scheinbar komplett anderes Problem zu lösen" herausfinden. Oder aber "Wenn es für dieses Problem kein effektives Lösungsverfahren gibt, dann gibts es auch für diese anderen 42 Probleme keins!".
Stell dir z.B. mal folgendes Problem vor. Du willst eine Rundtour fahren, von deinem Wohnort aus. Angenommen du wohnst in Frankfurt. Du willst einmal nach Berlin, nach Stuttgart, nach Potsdam, Leipzig, Erfurt und am Ende willst du wieder in Frankfurt ankommen. Jetzt frägst du dich natürlich: Wie fahre ich am Effektivsten? Natürlich könntest du einfach drauf los fahren und irgendwo hin fahren. Dabei gehst du aber natürlich das Risiko ein total "unwirtschaftlich" zu fahren und einen Haufen Sprit zu verbrauchen und viel länger zu fahren, als du eigentlich gemusst hättest. Man möchte also die Reihenfolge von Städten haben, die so gewählt ist, dass man möglichst wenig Sprit und Zeit fürs Fahren verbraucht.

Dieses Problem ist bekannt als das "Traveling Salesman Problem"/Problem des Handlungsreisenden - und es ist so "schwierig", dass selbst moderne Rechner es nicht effizient lösen können! Klar, man kann es lösen - aber wenn man z.B. die Sache mal von 5 Städten auf 1000000 Städte erhöht... ja, da siehst selbst für heutige Computer schlecht aus. Wenn du ein effizientes Lösungsverfahren dafür finden würdest, könntest du übrigens 1.000.000$ einsacken, würdest den Turing-Preis (vergleichbar mit dem Nobel-Preis, blos halt für Informatiker) bekommen und vermutlich auf ewig in die Geschichte eingehen. Denn wenn man das Lösen könnte, könnte man auch zigtausend andere, bisher nur uneffizient lösbare Probleme, effizient lösen können. Wie? Ganz einfach: Von diesen Probleme weis man, dass sie "gleich schwer" sind und man sie aufeinander reduzieren kann. Das ist ein bisschen so wie Übersetzen von einer Sprache in eine andere Sprache. Man kann Probleme in andere Probleme übersetzen (die scheinbar nichts miteinander zu tun haben!).


So... ich hoffe, dass reicht mal als grober Einblick
Das ist noch längst nicht alles... es geht dann auch noch um so Sachen wie Logik; Formales Beweisen, dass ein Programm/ein Algorithmus auch wirklich das tut, was man will; Formale Sprachen (zur Spracherkennung und sowas - da gehört übrigens dieser ganze Chomsky-Kram über den Ark und ich uns unterhalten dazu - und dieser Chomsky-Kram ist auch für Linguisten wichtig ); Kodierungs/Informationstheorie; Kryptographie (Verschlüsselung) usw. usf.

Auch wenn es viele Informatiker nicht gern einsehen wollen (weil sie den Kram nicht kapieren oder einfach keinen Bock drauf haben ) - so abgehoben dass alles klingt, es ist von absolut grundlegender Wichtigkeit für die Informatik und daher im Endeffekt auch wichtig für unseren Alltag, da Computer ja immer wichtiger werden und sich solche theoretischen Erkenntnisse immer direkt darauf auswirken.

Oh, doch recht lang geworden... Ich hoffe, dass stillt ein bisschen den Wissenshunger.

Ark, auf deine Frage(n) geh ich morgen ein

Gibt es eventuell ein Programm, mit dem man einen 16:9-Monitor in ein 4:3-Format umschalten kann, also so, dass der "überflüssige" Teil einfach schwarz bleibt?

Original von Phael
Gibt es eventuell ein Programm, mit dem man einen 16:9-Monitor in ein 4:3-Format umschalten kann, also so, dass der "überflüssige" Teil einfach schwarz bleibt?

ich denke das kannst du auch ohne programm in den einstellungen richten. müsste eigentlich gehen.

Ich hab auch Mal von nem Programm gehört, dass das macht. Es heißt Riva-Tuner, oder so ähnlich. Falls es mit Windoof-Boardmitteln nicht geht kannst du das Ding ausprobieren.

können gebrannte cd's viren übertragen?

bzw: kann es passieren, dass ein infizierter pc den virus mit auf die cd brennt und er von dieser cd aus dann einen anderen pc befällt?

Original von N@vi
können gebrannte cd's viren übertragen?

Ja. Für eine Übertragung hinreichend ist eine infizierte Datei, die auf ein noch nicht von diesem Virus befallenen System kopiert wird. Dabei muss es allerdings nicht (metaphorisch gesagt) zum Ausbruch der Krankheit kommen. Es ist also möglich, dass eine infizierte Datei von einem eigentlich kerngesunden Rechner kommt.

Original von N@vi
bzw: kann es passieren, dass ein infizierter pc den virus mit auf die cd brennt und er von dieser cd aus dann einen anderen pc befällt?

Es gibt einige Schwierigkeiten, die es nicht leicht machen sollten, die Infizierung einer CD/DVD unauffällig zu bewerkstelligen. Immerhin muss ein hinreichend beschreibbarer Rohling in einem Brenner liegen und das Schadprogramm Zugriff darauf haben. Dann muss dieses Schadprogramm in der Lage sein, diesen Brennvorgang durchzuführen (softwareseitig). Idealerweise wäre es dabei dem Schadprogramm möglich, für Autostart-Funktionen wirksam zu brennen. Das reicht aber auch nicht, um ein System zu infizieren, nur weil eine so infizierte CD/DVD eingelegt wurde: Das Virus muss vom neuen Wirt erst einmal ausgeführt werden, und das ist kein Naturgesetz, obwohl es in den Medien häufig so dargestellt wird. Ansonsten gilt auch hier, was ich oben schon geschrieben habe.

Ark

Ich schreibe gerade für GameAlive.net eine Review von Batman - The Killing Joke, einer Graphic Novel. Zur Visualisierung würde ich gerne das cover sowie eine bestimmte Seite einscannen und hochladen. Ist das urheberrechtlich sehr bedenklich?

ich glaube nicht, wenn du zeichner, verlag, outliner etc alles angibst.

Original von N@vi
ich glaube nicht, wenn du zeichner, verlag, outliner etc alles angibst.

Oder noch besser: ganz konkret danach fragst.

Ark

Original von Ark

Original von N@vi
ich glaube nicht, wenn du zeichner, verlag, outliner etc alles angibst.

Oder noch besser: ganz konkret danach fragst.

Ark

Wenn ich nur wüsste, wo ich fragen muss.