3. Gibt es Programme die von alleine Programieren?

Gibt es Programme die von alleine Programieren?

  • ?

    Hallo!

    Ich meine, daß es schon MÖGLICH ist, sich Programme nach gegebenen
    Spezifikationen selbst entwickeln zu lassen.

    Schließlich sind C++ Programme nur Zeichenketten. Man läßt also einen
    Computer alle Zeichenketten in aufsteigender Länge hintereinander aufzählen, schickt die Zeichenkette
    durch einen C++ Compilter und startet das Compilat. In den meisten Fällen wird
    gar kein Compilat entstehet, da die meisten Zeichenketten keine syntaktisch
    einwandfreien C++ Programme sind. In den Fällen, wo ein Compilat entsteht,
    startet man dies und läßt (ebenfalls von einem Computer) prüfen, ob die
    endlich vielen Spezifikationen in Form von input/output-Paaren erfüllt sind.

    Falls nein: nächste Zeichenkette prüfen.
    Falls ja: Fertig. C++ Programm releasen.

    Theoretisch ist das also möglich,
    praktikabel ist es nicht. Denn:
    1. Falls es zur Spezifikation gat kein Programm gibt, zählt man unendlich
    lange weitere Zeichenketten auf, ohne zu wissen, wann Schluß ist
    2. Selbst wenn man sich auf Zeichenketten der Länge 30 beschränkt
    (das reicht gerade für #include<iostream> int main(){. ....}),
    zählt man länger als das Universum existiert.

    Theoretisch ist es also möglich. Der praktische Nutzen ist aber etwa so
    hoch wie der des Versuchs, Fermats letzten Satz zu wiserlegen, indem man
    alle möglichen Zahlentripel aufzählt und hofft, ein Gegenbeispiel zu finden.

    Grüße

    0
  • M

    Das ist ein ziemlich interessanter Ansatz!
    Denn im Moment ist das Einzige, was diese Methode zum scheitern verurteilt, die Rechenkraft der CPU. Allerdings schreitet auch die Quantentechnologie langsahm voran und wer weiß, was die Zukunft bringt.

    Ich denke daher, dass diese Methode in Zukunft sogar sehr effektiv sein könnte.

    P.s.

    Prof84 schrieb:

    - Innovation is an illusion of human! In fact, it's just an unknown combination of things those already exist! /me

    -In Wirklichkeit ist es eine unbekannte Kombination von Dingen welche bereits existieren.

    Unbekannt? Ich würde sagen: Teils, Teils.
    Viele Kombinationen, oder Vorgänge sind zwar ungewollt in Gang gesetzt aber nicht alle.

    Aber lassen wir das unbekannt einfach mal ausser Acht. 😉

    "-In Wirklichkeit ist es eine Kombination von Dingen welche bereits existieren."

    Gut erkannt, aber deswegen ist es noch lange keine Illusion? 😕

    P.p.s. Entschuldigung, dass ich deine Weisheit so zerfetzt hab. 😉

    0
  • J

    Prof84 schrieb:

    MisterX schrieb:

    Folie 13
    http://ls2-www.cs.uni-dortmund.de/~droste/GTI06/Inhalt/060518.pdf

    Na also! Da sind wir doch d' accord! Ich zittiere deine Folie:
    "Sei S eine Eigenschaft, die von mindestens einer, aber nicht von allen berechnbaren Funktionen erfüllt wird."

    Ich sehe nicht, was das ändern soll? Klar ist die Voraussetzung wichtig, sonst wäre die Entscheidungsfunktion ja die konstante 0 oder die konstante 1-Funktion, die ist in jedem Fall berechenbar. Im allgemeinen werden Deine Anforderungen aber wohl (hoffentlich) von mindestens einer berechenbaren Funktion erfüllt (sonst ist das Projekt nicht realisierbar) und auch nicht von allen erfüllt (sonst wäre die Anforderung trivial).

    0
  • ?

    Hobbyprogrammierer schrieb:

    Hallo!

    Ich meine, daß es schon MÖGLICH ist, sich Programme nach gegebenen
    Spezifikationen selbst entwickeln zu lassen.

    Schließlich sind C++ Programme nur Zeichenketten. Man läßt also einen
    Computer alle Zeichenketten in aufsteigender Länge hintereinander aufzählen, schickt die Zeichenkette
    durch einen C++ Compilter und startet das Compilat. In den meisten Fällen wird
    gar kein Compilat entstehet, da die meisten Zeichenketten keine syntaktisch
    einwandfreien C++ Programme sind. In den Fällen, wo ein Compilat entsteht,
    startet man dies und läßt (ebenfalls von einem Computer) prüfen, ob die
    endlich vielen Spezifikationen in Form von input/output-Paaren erfüllt sind.

    Falls nein: nächste Zeichenkette prüfen.
    Falls ja: Fertig. C++ Programm releasen.

    Theoretisch ist das also möglich,
    praktikabel ist es nicht. Denn:
    1. Falls es zur Spezifikation gat kein Programm gibt, zählt man unendlich
    lange weitere Zeichenketten auf, ohne zu wissen, wann Schluß ist
    2. Selbst wenn man sich auf Zeichenketten der Länge 30 beschränkt
    (das reicht gerade für #include<iostream> int main(){. ....}),
    zählt man länger als das Universum existiert.

    Theoretisch ist es also möglich. Der praktische Nutzen ist aber etwa so
    hoch wie der des Versuchs, Fermats letzten Satz zu wiserlegen, indem man
    alle möglichen Zahlentripel aufzählt und hofft, ein Gegenbeispiel zu finden.

    Grüße

    Ein Problem (hier Programm selbst erzeugen) welches nur mit Algorithmen gelöst werden können, die bei bestimmten Eingaben zwangsläufig in einer Unendlichschleife landen nennt man laut Definition:
    NICHT BERECHENBAR.

    Und wenn der Fehler nur einseitig ist nennt man diese rekursiv aufzählbar.
    (auch rekursiv aufzählbare Probleme sind NICHT BERECHENBAR)

    (Berechnenbar ist ein Problem, wenn ein Programm existiert, dass für ALLE mögliches Eingaben nach ENDLICH vielen Schritten das eindeutige, richtige Ergebnis berechnet hat)

    Demnach ist das Automatische erzeugen eines Programms für das man die Spezifikationen angibt NICHT BERECHENBAR, denn wie du schon bemerkt hast wird es bei Spezifikationen, die nicht erfüllbar sind zwangsläufig zu einer Unendlichschleife kommen.

    0
  • A

    Jester schrieb:

    Prof84 schrieb:

    MisterX schrieb:

    Folie 13
    http://ls2-www.cs.uni-dortmund.de/~droste/GTI06/Inhalt/060518.pdf

    Na also! Da sind wir doch d' accord! Ich zittiere deine Folie:
    "Sei S eine Eigenschaft, die von mindestens einer, aber nicht von allen berechnbaren Funktionen erfüllt wird."

    Ich sehe nicht, was das ändern soll? Klar ist die Voraussetzung wichtig, sonst wäre die Entscheidungsfunktion ja die konstante 0 oder die konstante 1-Funktion, die ist in jedem Fall berechenbar. Im allgemeinen werden Deine Anforderungen aber wohl (hoffentlich) von mindestens einer berechenbaren Funktion erfüllt (sonst ist das Projekt nicht realisierbar) und auch nicht von allen erfüllt (sonst wäre die Anforderung trivial).

    Genau richtig!

    Also zum Beispiel ist schon die Spezifikation " Ein Programm berechnet bei Eingabe X als Ausgabe f(x)=x^2 " nicht berechenbar.

    "Sei S eine Eigenschaft, die von mindestens einer, aber nicht von allen berechnbaren Funktionen erfüllt wird."
    Also gut:

    Es gibt ein Programm welches f(x)=x^2 berechnet. Beweis:

    #include <Iostream>
using namespace std;
int main()
{
   int x;
   cin >> x;
   x=x*x;
   cout << x;

   return 1;
}

    Und diese Anforderung wird nicht von allen Programmen erfüllt, denn es gibt Programme, die nicht f(x) = x^2 berechnen. Beweiß:

    #include <Iostream>
using namespace std;
int main()
{
   cout << "Hallo World!";

   return 1;
}

    Also kann laut dem bewiesenen Satz von Rice kein Computer berechnen, ob ein gegebenes Programm f(x) = x^2 berechnet.

    Und diese Anforderung war ja nun wirklich nicht schwierig. Aber trivial war sie eben nicht. Wenn man das also schon für so einfache Probleme nicht berechnen kann, kannst du dir bestimmt vorstellen, das es für kompliziertere nicht triviale Anforderungen erst recht nicht geht.

    0
  • J

    Da ziehst Du imho nen falschen Schluß. Die Zugehörigkeit ist zwar allgemein unentscheidbar. Das bedeutet aber nicht, daß man nicht doch für einzelne Probleme das sehr wohl entscheiden kann.

    0
  • ?

    Andreas XXL schrieb:

    Der Computer kann aber nicht erkennen, das es sich bei der Eingabe um eine nicht berechenbare Funktion handelt.

    Warum nicht? D.h., bessere frage: Warum kannst DU das, und ein Computer nicht?

    0
  • P

    Jester schrieb:

    Prof84 schrieb:

    MisterX schrieb:

    Folie 13
    http://ls2-www.cs.uni-dortmund.de/~droste/GTI06/Inhalt/060518.pdf

    Na also! Da sind wir doch d' accord! Ich zittiere deine Folie:
    "Sei S eine Eigenschaft, die von mindestens einer, aber nicht von allen berechnbaren Funktionen erfüllt wird."

    Ich sehe nicht, was das ändern soll? Klar ist die Voraussetzung wichtig, sonst wäre die Entscheidungsfunktion ja die konstante 0 oder die konstante 1-Funktion, die ist in jedem Fall berechenbar. Im allgemeinen werden Deine Anforderungen aber wohl (hoffentlich) von mindestens einer berechenbaren Funktion erfüllt (sonst ist das Projekt nicht realisierbar) und auch nicht von allen erfüllt (sonst wäre die Anforderung trivial).

    Joh, kannste knicken! 😉

    Ich kann immer noch nicht glauben, dass ich mir den Scheiß überhaupt durchgelesen habe ...

    @Zauberlehrlinge:
    Hier wird nicht groß gerechnet! Ich habe eine endliche Anzahl von Eigenschaften S(i), ein Konzept k und endliche Anzahl von Funktionen f(x) in einen abgeschlossenen System Y.

    Gemäß http://de.wikipedia.org/wiki/Turingmaschine ist das eine deterministische Turing-Maschine.
    Satz von Rice mit dem Beweis
    http://www-i1.informatik.rwth-aachen.de/Lehre/VBuK0506/Folien/berechenbarkeit6.pdf
    bezieht sich auf eine nichtdeterministische Turingmaschine.

    So, jetzt will ich aus dem Hörsaal nichts mehr hören und gehe zurück auf mein Schlachtfeld:

    In meinen System sind alle Abhängigkeiten der Funktionen beim System Engineering durch das Konzept bereits aufgeschlüsselt worden. Verhalten sich Eigenschaften untereinander nicht-kommulativ ist eine Eigenschaftsaggretation sogar trival. Ist dann reine komponentenbasierte Betrachtung. Verhalten sich Eigenschaften untereinander kommulativ (heiser & kälter -> bleibt das System wohl lauwarm) muss die Abhängigkeit der Funktionen über das Konzept untersucht werden. Welche Eigenschaften untereinander kommulativ sind, wird durch das Konzept bestimmt. Ich kann auch "geizig" mit "warm" in Verbindung bringen, über die Features "Zahlung" <-> "Heizkosten" <-> "Heizung" <-> "Raumtemperatur". Dann muss ich in der Problem-Domain nur noch die Use Cases oder Samples definieren - "geizig" := < 15 €/mon Heizkosten und "warm" := > 20° C Raumtemperatur. Jetzt habe ich nur noch FR's und kann alle den m Features zugehörigen n Funktionen deterministisch durchrechnen lassen, in wieweit Sie der Zielbefriedigung genügen, eine Taxonomie erstellen und wenn Platz 1 die Schwellwerte erfüllt Code generieren lassen => IP. Und wie das funktioniert, kann Euch jeder der vielen Tausend Mathlab/Simulink Entwickler bestens erklären, zum Bleistift bei der sogenannten Kalibrierung.

    http://www.mathworks.ch/products/product_listing/index.html

    Hat bei mir einfach nur super funktioniert! ... Tipps! 👍

    Generative Programming | ISBN: 0201309777 Software Factories | ISBN: 0471202843 Modellgetriebene Softwareentwicklung | ISBN: 3898643107

    0
  • ?

    Hallo!

    @MisterX:

    Was du über die Bedeutung von rek.aufz. und ber.bar schreibst, dem kann ich zustimmen. Nur Deiner Schlußfolgerung nicht:

    Demnach ist das Automatische erzeugen eines Programms für das man die Spezifikationen angibt NICHT BERECHENBAR,<<

    Nein. Ich schrieb, daß die Spezifikation in Form ENDLICH vieler Input/Output-Paare
    gegeben sei, und das kann man bei gegebenem Algorithmus eben doch rekursiv
    überprüfen (Univ.Turing-Masch.).
    Das Halteproblem ist nicht mit endlich vielen I/O-Paaren spezifizierbar,
    wird also von meiner Behauptung nicht betroffen.

    denn wie du schon bemerkt hast wird es bei Spezifikationen, die nicht erfüllbar sind zwangsläufig zu einer Unendlichschleife kommen.<<

    Spezifikationen in Form endlich vieler I/O-Paare sind immer erfüllbar.

    Übrigens: Mein Argument enthält eine undeutliche Stelle, die liegt aber
    woanders: Man kann die Algorithmen nicht *nacheinander* prüfen, da man
    ja auf eine Endlosschleife while(1){;} stoßen könnte. Aber dafür gibt es
    eine einfache Lösung: Man simuliert die Algorithmen nicht nacheinander,
    sondern "interleaved" bei aufsteigender Größe der Programmlänge: Schritt 1 vom 1. Algo der Länge 1, dann Schritt 1 vom 2. Algo der
    Länge 1,....,SChritt 1 vom letzten Algo der Länge 1, usw... wobei man dabei
    eine Methode zur Aufzählung von Tupeln natürlicher Zahlen verwendet
    (Codierung von NxN in N).

    Grüße

    0
  • ?

    Nachtrag:

    Spezifikationen in Form endlich vieler I/O-Paare sind immer erfüllbar.<<

    ...sofern nicht demselben I-Wert verschiedene O-Werte zugeordnet sind
    (Widerspruchsfreiheit).

    0
  • J

    Prof84 schrieb:

    @Zauberlehrlinge:
    Hier wird nicht groß gerechnet! Ich habe eine endliche Anzahl von Eigenschaften S(i), ein Konzept k und endliche Anzahl von Funktionen f(x) in einen abgeschlossenen System Y.

    Gemäß http://de.wikipedia.org/wiki/Turingmaschine ist das eine deterministische Turing-Maschine.
    Satz von Rice mit dem Beweis
    http://www-i1.informatik.rwth-aachen.de/Lehre/VBuK0506/Folien/berechenbarkeit6.pdf
    bezieht sich auf eine nichtdeterministische Turingmaschine.

    War es nicht so, daß deterministische Turing-Maschinen und nichtdeterministische äquivalent sind? Ich kann doch locker eine deterministische Turing-Maschine bauen, die einfach alle möglichen Nachfolgezustände dser nichtdeterministischen auf's Band schreibt und dann immer reih um abarbeitet. Das Problem besteht also weiterhin.

    Vielleicht möchtest Du jetzt einfach zugeben, daß Du Dich an den Strohhalm der Hoffnung klammerst, daß Du immer nur Sachen generieren und beschreiben muß bei den es trotzdem klappt?

    0
  • P

    Jester schrieb:

    Prof84 schrieb:

    @Zauberlehrlinge:
    Hier wird nicht groß gerechnet! Ich habe eine endliche Anzahl von Eigenschaften S(i), ein Konzept k und endliche Anzahl von Funktionen f(x) in einen abgeschlossenen System Y.

    Gemäß http://de.wikipedia.org/wiki/Turingmaschine ist das eine deterministische Turing-Maschine.
    Satz von Rice mit dem Beweis
    http://www-i1.informatik.rwth-aachen.de/Lehre/VBuK0506/Folien/berechenbarkeit6.pdf
    bezieht sich auf eine nichtdeterministische Turingmaschine.

    War es nicht so, daß deterministische Turing-Maschinen und nichtdeterministische äquivalent sind? Ich kann doch locker eine deterministische Turing-Maschine bauen, die einfach alle möglichen Nachfolgezustände dser nichtdeterministischen auf's Band schreibt und dann immer reih um abarbeitet. Das Problem besteht also weiterhin.

    Vielleicht möchtest Du jetzt einfach zugeben, daß Du Dich an den Strohhalm der Hoffnung klammerst, daß Du immer nur Sachen generieren und beschreiben muß bei den es trotzdem klappt?

    Nö! 🙄

    0
  • ?

    Hobbyprogrammierer schrieb:

    Hallo!

    @MisterX:

    Was du über die Bedeutung von rek.aufz. und ber.bar schreibst, dem kann ich zustimmen. Nur Deiner Schlußfolgerung nicht:

    Demnach ist das Automatische erzeugen eines Programms für das man die Spezifikationen angibt NICHT BERECHENBAR,<<

    Nein. Ich schrieb, daß die Spezifikation in Form ENDLICH vieler Input/Output-Paare
    gegeben sei, und das kann man bei gegebenem Algorithmus eben doch rekursiv
    überprüfen (Univ.Turing-Masch.).
    Das Halteproblem ist nicht mit endlich vielen I/O-Paaren spezifizierbar,
    wird also von meiner Behauptung nicht betroffen.

    denn wie du schon bemerkt hast wird es bei Spezifikationen, die nicht erfüllbar sind zwangsläufig zu einer Unendlichschleife kommen.<<

    Spezifikationen in Form endlich vieler I/O-Paare sind immer erfüllbar.

    Übrigens: Mein Argument enthält eine undeutliche Stelle, die liegt aber
    woanders: Man kann die Algorithmen nicht *nacheinander* prüfen, da man
    ja auf eine Endlosschleife while(1){;} stoßen könnte. Aber dafür gibt es
    eine einfache Lösung: Man simuliert die Algorithmen nicht nacheinander,
    sondern "interleaved" bei aufsteigender Größe der Programmlänge: Schritt 1 vom 1. Algo der Länge 1, dann Schritt 1 vom 2. Algo der
    Länge 1,....,SChritt 1 vom letzten Algo der Länge 1, usw... wobei man dabei
    eine Methode zur Aufzählung von Tupeln natürlicher Zahlen verwendet
    (Codierung von NxN in N).

    Du kannst eben nicht Programme für alle Probleme erzeugen.
    Die Definition von berechenbar ist aber, das es für alle gehen muß.
    Wenn du für BESTIMMTE Probleme atomatisch CODE ezeugen kannst (Was ich durchaus nachvollziehen kann) so bleibt es nach Definition immer noch nicht berechenbar. Weil es reicht das es auch nur EINE Anforderung gibt, für die du keinen Code automatisch erzeugen kannst.

    Und diese eine ist z.B die Diagonalsprache.

    => Automatische Codeerzeugung ist (allgemein) nicht berechenbar.

    Grüße

    0
  • ?

    Hobbyprogrammierer schrieb:

    Hallo!

    @MisterX:

    Was du über die Bedeutung von rek.aufz. und ber.bar schreibst, dem kann ich zustimmen. Nur Deiner Schlußfolgerung nicht:

    Demnach ist das Automatische erzeugen eines Programms für das man die Spezifikationen angibt NICHT BERECHENBAR,<<

    Nein. Ich schrieb, daß die Spezifikation in Form ENDLICH vieler Input/Output-Paare
    gegeben sei, und das kann man bei gegebenem Algorithmus eben doch rekursiv
    überprüfen (Univ.Turing-Masch.).
    Das Halteproblem ist nicht mit endlich vielen I/O-Paaren spezifizierbar,
    wird also von meiner Behauptung nicht betroffen.

    denn wie du schon bemerkt hast wird es bei Spezifikationen, die nicht erfüllbar sind zwangsläufig zu einer Unendlichschleife kommen.<<

    Spezifikationen in Form endlich vieler I/O-Paare sind immer erfüllbar.

    Übrigens: Mein Argument enthält eine undeutliche Stelle, die liegt aber
    woanders: Man kann die Algorithmen nicht *nacheinander* prüfen, da man
    ja auf eine Endlosschleife while(1){;} stoßen könnte. Aber dafür gibt es
    eine einfache Lösung: Man simuliert die Algorithmen nicht nacheinander,
    sondern "interleaved" bei aufsteigender Größe der Programmlänge: Schritt 1 vom 1. Algo der Länge 1, dann Schritt 1 vom 2. Algo der
    Länge 1,....,SChritt 1 vom letzten Algo der Länge 1, usw... wobei man dabei
    eine Methode zur Aufzählung von Tupeln natürlicher Zahlen verwendet
    (Codierung von NxN in N).

    Grüße

    Du kannst eben nicht Programme für alle Probleme erzeugen.
    Die Definition von berechenbar ist aber, das es für alle gehen muß.
    Wenn du für BESTIMMTE Probleme atomatisch CODE ezeugen kannst (Was ich durchaus nachvollziehen kann) so bleibt es nach Definition immer noch nicht berechenbar. Weil es reicht das es auch nur EINE Anforderung gibt, für die du keinen Code automatisch erzeugen kannst.

    Und diese eine ist z.B die Diagonalsprache.

    => Automatische Codeerzeugung ist (allgemein) nicht berechenbar.

    0
  • ?

    Hallo MisterX

    Du kannst eben nicht Programme für alle Probleme erzeugen. <<

    Wer hat das behauptet ? Das Halteproblem beweist das doch schon.

    Wenn du für BESTIMMTE Probleme atomatisch CODE ezeugen kannst (Was ich durchaus nachvollziehen kann) so bleibt es nach Definition immer noch nicht berechenbar.<<

    Doch. Denn ich schrieb schon ganz am Anfang, daß ich unter "Spezifikation" eine
    endliche Liste von Input/Output-Paaren verstehe. Und damit kann man mittels
    einer Abzählung der Gödelnummern aller Turingmaschinen mit Programmlänge 1,2,...
    und Prüfen, ob die I/O-Vorgaben vom jeweiligen Turingprogramm erfüllt werden,
    in jedem Fall ein geeignetes Programm finden, solange die I/O-Vorgabe nicht
    widersprüchlich ist. Das letztere ist aber keine wesentliche Einschränkung, denn
    daß eine Spezifikation wie "f(0)=1 AND f(0)=2" nicht erfüllbar sein kann,
    ist klar und läßt sich auch leicht (rekursiv) vorher testen.

    Daß das mit den von Dir benutzten uneingeschränkten Spezifikationen nicht
    mehr funktioniert, ist klar. Siehe Halteproblem. Das läßt sich aber eben
    auch nicht als endliche I/O-Werteliste aufschreiben.

    Grüße

    0
Anmelden zum Antworten