… und unsere Nummerierungen von \\(P^{(1)}\\).<\/p>\n\n\n\n
Da ich mittlerweile ein paar Mails zu diesem Thema bekommen habe, w\u00fcrde ich hier gerne noch etwas erl\u00e4utern. F\u00fcr viele ist das Theorem noch nicht greifbar. Ebensowenig die Nummerierung \\(\\varphi\\) der einstelligen, berechenbaren Funktionen \\(P^{(1)}\\). Auch den Begriff Modellprogrammiersprache in Bezug auf \\(\\varphi\\) haben ein paar geh\u00f6rt, k\u00f6nnen das aber noch nicht so ganz „anfassen“. Ich versuche mal mal Gl\u00fcck, vielleicht wird es nach meinen Ausf\u00fchrungen f\u00fcr euch etwas deutlicher.<\/p>\n\n\n\n
Achtung<\/strong>: w\u00e4hrend wir im Skript \\(P^{(1)}\\) direkt nummerieren, gehe ich zun\u00e4chst einen etwas anderen Weg. Also nicht erschrecken. Am Ende folgt die Aufl\u00f6sung.<\/p>\n\n\n\n Zun\u00e4chst: Warum ist \\(\\varphi\\) eine Programmiersprache?<\/strong><\/p>\n\n\n\n Sicher habt Ihr schon einmal im Kurs imperative Programmierung (01613) oder Einf\u00fchrung in die objektorientierte Programmierung (01618) belegt. Dort programmieren wir in Java und Pascal. Was hat nun Java und Pascal mit uns und \\(\\varphi\\) zu tun?!<\/p>\n\n\n\n Z\u00e4umen wir das Pferd mal von hinten auf.<\/p>\n\n\n\n Nehmen wir zun\u00e4chst eine Funktion \\(f(x)=x\\), d.h. unsere Identit\u00e4tsfunktion aus \\(P^{(1)}\\). Im Endeffekt wollen wir diese Funktion auf unserem Computer, unserer Turingmaschine berechnen. Wir k\u00f6nnen, wie man sich leicht vorstellt, eine beliebige Funktion nehmen. Aber \\(f\\) reicht f\u00fcr unsere Zwecke komplett aus.<\/p>\n\n\n\n So sieht unser Programm in PASCAL aus:<\/p>\n\n\n\n Und so in Java<\/p>\n\n\n\n (Bitte nicht darauf festnageln, dass ich „public class“ bei Java und „program“ bei PASCAL vergessen habe, mir geht es nur um’s Verst\u00e4ndnis)<\/p>\n\n\n\n Wir sind uns einig, dass damit die Funktion \\(f\\) berechnet wird? Gut. Und da wir \\(\\varphi\\) eine Programmiersprache genannt und gesagt haben, dass es nur eine Programmiersprache zu geben braucht (\u00c4quivalenz und so), nennen wir die Programmiersprache Java einfach \\(\\kappa\\) (Kappa) und PASCAL \\(\\omicron\\) (Omicron). Das sind also unsere Nummerierungen von \\(P^{(1)}\\), bzw. sollen es einmal werden.<\/p>\n\n\n\n Erinnert Ihr euch, wie \\(\\varphi\\) definiert war? Das machen wir mit \\(\\kappa\\) und \\(\\omicron\\) genauso! Wir haben nur ein anderes Alphabet. Hatten wir bei \\(\\varphi\\) das Alphabet \\(\\Omega:=(1\\mid{B}\\mid{(}\\mid{)}\\mid{,}\\mid{:}\\mid{R}\\mid{L})\\), so sind wir bei \\(\\kappa\\) und \\(\\omicron\\) bei ein paar mehr Zeichen. Ich f\u00fchre sie jetzt nicht alle auf, aber die paar sollten gen\u00fcgen. Wir m\u00fcssen unsere Programme von oben mit Zeichen aus diesem Alphabet darstellen k\u00f6nnen:<\/p>\n\n\n\\(\\Omega_\\kappa:=(b\\mid{e}\\mid{g}\\mid{i}\\mid{n}\\mid{(}\\mid{)}\\mid{;}\\mid{.}, …)\\)\n\n\n\\(\\Omega_\\omicron:=(p\\mid{u}\\mid{b}\\mid{l}\\mid{i}\\mid{(}\\mid{)}\\mid{[}\\mid{:}\\mid{]}\\mid{;}, …)\\)\n\n\n\n Wie gesagt: nicht alle Zeichen drin. Hauptsache Ihr wisst, worauf ich hinaus will. Kommen wir nun zu unseren Nummerierungen \\(\\kappa\\) und \\(\\omicron\\). Diese werden genauso definiert wie unser \\(\\varphi\\).<\/p>\n\n\n\n Wir bekommen damit zur Nummer \\(i\\) das zugeh\u00f6rige Bandprogramm wenn es tats\u00e4chlich ein Bandprogramm ist. Oder einfach nur eine Endlosschleife wenn die Nummer \\(i\\) zu irgendwelchem Kauderwelsch geh\u00f6rt, denn mit \\(\\nu_{\\Omega_\\kappa}\\) haben wir (siehe oben) alle Worte \u00fcber \\(\\Omega_\\kappa\\), d.h. auch Unsinn, nummeriert.\n<\/p>\n\n\n\n Warum haben wir kein \\(\\xi_\\kappa\\) und kein \\(\\xi_\\omicron\\)? Sehen wir gleich!<\/p><\/li>\n\n\n\n Wir haben mit Java und Pascal also das gemacht, was wir mit \\(\\varphi\\) getan haben. Nur nutzten wir nicht \\(\\Omega:=(1\\mid{B}\\mid{(}\\mid{)}\\mid{,}\\mid{:}\\mid{R}\\mid{L})\\) als „Programmieralphabet“, sondern \\(\\Omega_\\kappa\\) f\u00fcr unsere Zeichen der PASCAL-Programme und \\(\\Omega_\\omicron\\) f\u00fcr Java.<\/p>\n\n\n\n Das f\u00fchrt uns zu ihren Kompositionen:<\/p>\n\n\n\\(\\kappa = \\xi\\circ\\nu_M\\kappa\\circ\\nu_P\\kappa\\)\n\n\n\\(\\omicron = \\xi\\circ\\nu_M\\omicron\\circ\\nu_P\\omicron\\)\n\n\n\n Die ebenfalls Nummerierungen von \\(P^{(1)}\\) sind. Damit sie zu \\(\\varphi\\) \u00e4quivalent sind, m\u00fcssen sie das utm- und das smt-Theorem erf\u00fcllen. Kommen wir daher zum utm-Theorem.<\/p>\n\n\n\n utm-Theorem f\u00fcr \\(\\kappa\\) und \\(\\omicron\\)<\/strong><\/p>\n\n\n\n Intuitiv wisst Ihr schon, dass beide Programmiersprachen das utm-Theorem erf\u00fcllen. Sie k\u00f6nnen interpretiert\/compiliert werden und unsere Funktion berechnen. Das k\u00f6nnt Ihr im zugeh\u00f6rigen Compiler testen.<\/p>\n\n\n\n Und genau das ist unser \\(u\\) aus der Definition des utm-Theorems:<\/p>\n\n\n\\(u_\\varphi(i,x) = \\varphi_i(x)\\)\n\n\n\\(u_\\kappa(i,x) = \\kappa_i(x)\\)\n\n\n\\(u_\\omicron(i,x) = \\omicron_i(x)\\)\n\n\n\n Euch ist sicherlich auch klar, dass jeder Compiler\/Interpreter f\u00fcr jede Programmiersprache unterschiedlich ist. W\u00e4hrend ich f\u00fcr PASCAL Befehle wie „Writeln()<\/em>;“ interpretieren und in Maschinencode f\u00fcr x86 (oder andere Prozessoren) \u00fcbersetzen darf, muss ich f\u00fcr Java Zeug in Form von „System.out.println();<\/em>“ interpretieren. W\u00e4hrend beide g\u00e4nzlich unterschiedliche Worte \u00fcber ihren Alphabeten \\(\\Omega_\\kappa\\) und \\(\\Omega_\\omicron\\) sind, so sind die daraus entstehenden Bandmaschinen jedoch gleich<\/strong>!<\/p>\n\n\n\n Und genau das ist der Grund, warum wir nur einmal \\(\\xi\\) definiert haben. Wir nutzten zwar unterschiedliche Programmiersprachen (\\(\\kappa\\) und \\(\\omicron\\)) und hatten nat\u00fcrlich auch unterschiedliche Programme \\(BP\\), aber immer ein Berechnungsmodell, d.h. nur eine \\(BM\\), z.B. die gleichen Assembler Befehle f\u00fcr einen x86 Prozessor (oder die gleichen Befehle f\u00fcr eine Turingmaschine).<\/p>\n\n\n\n Ich nehme also die Programmiersprachen-Kommandos „Writeln()<\/em>;“ und „System.out.println();<\/em>“ und \u00fcbersetze sie mit den zugeh\u00f6rigen Funktionen die gleiche Bandmaschine, die auf dem x86 Prozessor ausgef\u00fchrt wird.<\/p>\n\n\n\n\\(\\nu_{M\\kappa}(„Writeln();“)=BM_1\\)\n\n\n\n\\(\\nu_{M\\omicron}(„System.out.println();“)=BM_1\\)\n\n\n\n Nur haben wir oben nicht einen x86 Befehlssatz als Berechnungsmodell, sondern eine Turingmaschine gew\u00e4hlt. D.h. die Bandmaschine \\(BM_1\\) hat die Befehle in der Form, wie unsere Turingmaschine sie versteht. Denn die TM ist unser mathematisches, einfaches Modell f\u00fcr unsere Berechnungen. Und nach der Church\/Turing-These ist sie genauso m\u00e4chtig wie unser x86 Prozessor. Nur brauchen wir uns um die komplizierten Befehle des Prozessors nicht zu k\u00fcmmern und verbleiben bei den \u00fcberschaubaren Befehlen der TM \ud83d\ude09<\/p>\n\n\n\n Im Endeffekt hat also jede<\/strong> Nummerierung, d.h. jede<\/strong> Programmiersprache ihren eigenen<\/strong> Interpreter, die universelle Funktion \\(u\\), der die Befehle der Programmiersprache in die Befehle des Berechnungsmodells (sei es TM, x86, Registermaschine oder sonstwas \u00e4quivalentes) \u00fcbersetzt.<\/p>\n\n\n\n Und da wir am Ende immer auf einem Berechnungsmodell landen (landen k\u00f6nnen<\/strong>, dazu gleich auch noch mehr), egal welche (\u00e4quivalente) Programmiersprache\/Nummerierung wir verwenden, liegt ein Schluss sehr nahe: wir k\u00f6nnen zwei \u00c4quivalente Sprachen auch ineinander \u00fcbersetzen.<\/p>\n\n\n\n Und das ist dann auch der Bezug zum \u00dcbersetzungslemma, dem smn-Theorem<\/strong>. Nennen wir diese Funktion einfach mal \\(r\\), so k\u00f6nnen wir unsere Programmiersprachen Pascal und Java ineinander \u00fcbersetzen, so dass mathematisch gilt:<\/p>\n\n\n\\(\\kappa(i)(x) = \\omicron(r(i))(x)\\)\n\n\n\n Wie \\(r\\) funktioniert, k\u00f6nnt Ihr euch sicher bereits im Kopf zurechtschustern. Z.B. w\u00fcrde \\(r\\) uns die \u00e4quivalenten Befehle „Writeln()<\/em>;“ und „System.out.println();<\/em>“ ineinander \u00fcbersetzen: Tun wir mal so, als w\u00e4ren das Befehle funktionierender Programme, so haben sie durch die Nummerierungen \\(\\kappa\\) und \\(\\omicron\\) auch entsprechende Nummern. Seien die willk\u00fcrlichen Nummer der beiden Befehle:<\/p>\n\n\n\n \\(\\kappa(27181)=“Writeln(x);“\\) und<\/p>\n\n\n\n \\(\\omicron(516322)=“System.out.println();“\\),<\/p>\n\n\n\n so \u00fcbersetzen wir mit \\(r\\) letztendlich:<\/p>\n\n\n\n\\(\\kappa(27181)(x) = \\omicron(r(27181))(x) = \\omicron(516322)(x)\\)\n\n\n\n Wie geht \\(r\\) dazu vor? \\(r\\) nutzt einfach die universellen Funktionen von \\(\\kappa\\) und \\(\\omicron\\). Da beide Interpreter am Ende die gleiche Bandmaschine f\u00fcr „Writeln()<\/em>;“ und „System.out.println();<\/em>“ ausspucken, k\u00f6nnen wir das problemlos tun.<\/p>\n\n\n\n Und hier kommt das „Mehr“ und die Aufl\u00f6sung<\/strong><\/p>\n\n\n\n Wir sind sogar nicht einmal auf das gleiche Berechnungsmodell, bzw. die gleiche Bandmaschine \\(BM\\) angewiesen. Auch wenn unsere Programmiersprachen g\u00e4nzlich andere Berechnungsmodelle f\u00fcttern (z.B. wir interpretieren PASCAL f\u00fcr x86 und Java f\u00fcr ARM), so haben wir dennoch eine gemeinsame Basis! Die Nummern beider Programme werden zwar auch auf anderen Berechnungsmodellen (x86 und ARM) ausgef\u00fchrt, haben alle eigene Bandmaschinen \\(BM\\), berechnen aber die gleiche Funktion aus \\(P^{(1)}\\)!<\/p>\n\n\n\n Denn hier f\u00fchrt am Ende alles hin: egal welche Programmiersprache und welches Berechnungsmodell. Haben wir eine Programmiersprache\/Nummerierung, die eine berechenbare universelle Funktion \\(u\\) (utm-Theorem) besitzt und das smn-Theorem erf\u00fcllt, so sind diese \u00e4quivalent und berechnen alle das Gleiche: die Funktionen aus \\(P^{(1)}\\).<\/p>\n\n\n\n Und da das so ist, kann ich PERL weiterhin Java und PASCAL guten Gewissens vorziehen \ud83d\ude09<\/p>\n","protected":false},"excerpt":{"rendered":" … und unsere Nummerierungen von . Da ich mittlerweile ein paar Mails zu diesem Thema bekommen habe, w\u00fcrde ich hier gerne noch etwas erl\u00e4utern. F\u00fcr viele ist das Theorem noch nicht greifbar. Ebensowenig die Nummerierung der einstelligen, berechenbaren Funktionen . Auch den Begriff Modellprogrammiersprache in Bezug auf haben ein paar geh\u00f6rt, k\u00f6nnen das aber noch nicht … <\/p>\nbegin\n\n writeln(ParamStr(1));\n\nend.<\/code><\/pre>\n\n\n\npublic static void main(String []args){\n\n System.out.println(args[0]);\n\n}<\/code><\/pre>\n\n\n\n\n
<\/li>\n<\/ul>\n\n\n\\(\\nu_P\\kappa(i)=\\begin{cases}\\nu_{\\Omega_\\kappa}(i)&\\text{ wenn }\\nu_{\\Omega_\\kappa}(i)\\in{BP}\\\\Endlosschleife&\\text {sonst}\\end{cases}\\)\n\n\n\n