Algorithmus Vorstellungsgespräch



  • Bashar schrieb:

    Da fehlt ein entscheidendes Detail. Ein LOOP-Programm terminiert ja immer, aber es gibt nicht-terminierende Programme, von daher war von Anfang an klar, dass LOOP nicht alles kann. Man könnte nun vermuten, dass jedes Programm, dass für jede Eingabe terminiert, in LOOP geschrieben werden kann. Die Ackermann-Funktion ist das klassische Gegenbeispiel.

    Oh shit, ja da hast du Recht 😉
    Total vergessen. Zum Glück ist das hier keine Prüfung...

    Aber wo wir grad bei einem halbwegs theoretischen Thema sind (blurrys OP wird ja nicht ernst weiter verfolgt). Wie kann ich zeigen/beweisen/begründen, dass eine Sprache turingvollständig ist - also alles berechenbare auch berechnen kann?
    Ich denke mal nicht, dass Beispiele für WHILE- und LOOP- Berechenbarkeit reichen, oder?!



  • Skym0sh0 schrieb:

    Wie kann ich zeigen/beweisen/begründen, dass eine Sprache turingvollständig ist - also alles berechenbare auch berechnen kann?

    Kannst du das nicht tun, indem du sie auf eine Turingmaschine abbildest?

    Wenn wir annehmen können, dass Turingmaschinen alles berechnen können und deine Sprache als Turingmaschine funktionieren kann, können wir doch den entsprechenden Schluss ziehen.



  • Skym0sh0 schrieb:

    Aber wo wir grad bei einem halbwegs theoretischen Thema sind (blurrys OP wird ja nicht ernst weiter verfolgt). Wie kann ich zeigen/beweisen/begründen, dass eine Sprache turingvollständig ist - also alles berechenbare auch berechnen kann?

    Durch Simulation, d.h. durch Implementation einer Turingmaschine.



  • Ok, ich frage konkreter.
    Mir geht es weniger um den formalen, universellen Beweis, sondern ich möchte einem Kollegen klar machen, dass die Templates (und damit das Typsystem) von C++ turingvollständig sind.

    Nur wie?



  • Skym0sh0 schrieb:

    Ok, ich frage konkreter.
    Mir geht es weniger um den formalen, universellen Beweis, sondern ich möchte einem Kollegen klar machen, dass die Templates (und damit das Typsystem) von C++ turingvollständig sind.

    Nur wie?

    Und dir muss ich Beweise, dass das Typesystem im C++ nicht turingvollständig ist, weil ein Template kein Type ist, sonder nur ihre Instanzierung.

    Implementiere eine Funktion als Template?



  • Ich spreche von sowas hier:

    #include <iostream>
    
    int ack(unsigned int n, unsigned int m)
    {
    	if ( n == 0 )
    		return m + 1;
    	else if ( m == 0 )
    		return ack(n - 1, 1);
    	else
    		return ack(n - 1, ack(n, m - 1));
    }
    
    template<unsigned int N, unsigned int M>
    struct Ack
    {
    	static const unsigned int value = Ack<N - 1, Ack<N, M - 1>::value>::value;
    };
    
    template<unsigned int M>
    struct Ack<0, M>
    {
    	static const unsigned int value = M + 1;
    };
    
    template<unsigned int N>
    struct Ack<N, 0>
    {
    	static const unsigned int value = Ack<N-1, 1>::value;
    };
    
    int main()
    {
    	const unsigned int N = 3;
    	const unsigned int M = 4;
    
    	std::cout << "Ack(" << N << ", " << M << ") = " << ack(N, M) << std::endl; // 125
    	std::cout << "Ack<" << N << ", " << M << ">::value = " << Ack<N, M>::value << std::endl; // 125
    	return 0x0;
    }
    


  • Das reicht natürlich nicht. Als Beweis.

    edit: Sorry zu schnell gepostet. Als Begründung taugt es vielleicht schon, man müsste erkennen, dass die entscheidenden Elemente eines Berechenbarkeitsmodells umgesetzt werden können. Ich selbst kenne allerdings keines, das hier zutrifft.



  • Bashar schrieb:

    man müsste erkennen, dass die entscheidenden Elemente eines Berechenbarkeitsmodells umgesetzt werden können. Ich selbst kenne allerdings keines, das hier zutrifft.

    Oder die Elemente irgendeiner Sprache nehmen, von der man weiß, daß sie Turingvollständig ist. Brainfuck hat hübsch wenig Elemente https://github.com/knome/metabrainfuck/blob/master/bf.cpp




Anmelden zum Antworten