Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Gödelnummer einer Turingmaschine
Autor
Universität/Hochschule Gödelnummer einer Turingmaschine
mathletic
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 11.11.2013
Mitteilungen: 1596
  Themenstart: 2017-07-25

Hallo, wir haben die Zahl $931188502990012161008464125091373506842 = 2 \cdot 3^2 \cdot 59 \cdot 103^2 \cdot 149^3 \cdot 353^4 \cdot 401 \cdot 823^2 \cdot 1873 \cdot 3163$ Wie kann man prüfen ob diese Zahl die Gödelnummer einer Turingmaschine ist? In der vorgeschlagene Lösung steht folgendes: VOn der Primfaktorzerlegung haben wir dass m=1 und h=2. $\sigma_2(i,j)=2^i(2j+1)-1$ Wir haben folgende Tabelle $(i,j) \ \ \ \sigma_2 \ \ \ P\sigma_2 $ $(1,3) \ \ \ 13 \ \ \ 41 $ $(1,4) \ \ \ 17 \ \ \ 59 $ $(2,3) \ \ \ 27 \ \ \ 103 $ $(2,4) \ \ \ 35 \ \ \ 149 $ $(3,3) \ \ \ 55 \ \ \ 257 $ $(3,4) \ \ \ 71 \ \ \ 353 $ $(4,3) \ \ \ 111 \ \ \ 607 $ $(4,4) \ \ \ 143 \ \ \ 823 $ $(5,3) \ \ \ 223 \ \ \ 1409 $ $(5,4) \ \ \ 287 \ \ \ 1873 $ $(6,3) \ \ \ 447 \ \ \ 3163 $ $(6,4) \ \ \ 575 \ \ \ 4201 $ 401 kann nicht in der Primzerlegung sein, die Zahl kann also eine gültige Gödelnummer einer Turingmaschine sein. Könnt ihr mir erklären was man hier gemacht hat? Außerdem will ich die Gödelnummer der Bandfunktion, die das Band beschreibt berechnen, auf dem das Wort TURINGMASCHINE steht, wobei das Zeichen M an Bandposition 0 geschrieben ist. Der Rest des Bandes sei leer. Die Indizierung der Zeichen soll in alphabetischer Reihenfolge geschehen, also A → 1, C → 2, usw. Das Wort TURINGMASCHINE hat 14 Buchstaben. Nehmen wir also die ersten 14 Primzahlen und nehmen als die Potenzen diese Indizierung ?


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6994
Wohnort: Niedersachsen
  Beitrag No.1, eingetragen 2017-07-25

Das hängt alles davon ab, auf welche Weise ihr einer TM oder einem Bandinhalt eine Gödelnummer zuordnet. Dafür gibt es mehr als eine Möglichkeit. Du müsstest also dazuschreiben, wie ihr das macht, sonst kann man als Außenstehender nichts dazu sagen.


   Profil
mathletic
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 11.11.2013
Mitteilungen: 1596
  Beitrag No.2, vom Themenstarter, eingetragen 2017-07-26

Wir haben folgende Definitionen: http://matheplanet.de/matheplanet/nuke/html/uploads/b/38039_def1.JPG http://matheplanet.de/matheplanet/nuke/html/uploads/b/38039_def2.JPG


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6994
Wohnort: Niedersachsen
  Beitrag No.3, eingetragen 2017-07-26

Die Definition 3.27 beschreibt unter anderem, welche Primfaktoren in der Gödelnummer einer TM überhaupt vorkommen dürfen. Ein Beispiel: 59 ist die 17. Primzahl. 17 ist 21*(2*4+1)-1 (überlege Dir, dass diese Darstellung immer eindeutig ist). Die Primzahl 59 gehört also zu dem Paar i=1 und j=4. -- OK, das kannst Du auch Deiner Tabelle entnehmen, aber es kann nichts schaden, das auch von Hand nachzuvollziehen. Das entsprechende c1,2 ist also 1 (der Exponent von 59). Auch 103, 149 und 353 kommen in Deiner Tabelle vor. Hier kann man analog i, j und cij bestimmen. Die 401 steht nicht in der Tabelle. Verdächtig! Wir rechnen von Hand nach. 401 ist die 79. Primzahl 79 ist 24*(2*2+1)-1 (da 80=16*5 ist). Diese Primzahl gehört also zum Paar (4,2). j kann aber nur die Werte 3 oder 4 annehmen. Also ist die ganze Zahl keine Gödelnummer einer TM. \quoteon Das Wort TURINGMASCHINE hat 14 Buchstaben. Nehmen wir also die ersten 14 Primzahlen und nehmen als die Potenzen diese Indizierung ? \quoteoff Ja. Die Gödelnummer ist also 220*321*518*... \sourceon Matlab G=prod(primes(43).^('TURINGMASCHINE'-64)) \sourceoff


   Profil
mathletic
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 11.11.2013
Mitteilungen: 1596
  Beitrag No.4, vom Themenstarter, eingetragen 2017-07-26

\quoteon(2017-07-26 11:30 - Kitaktus in Beitrag No. 3) \quoteon Das Wort TURINGMASCHINE hat 14 Buchstaben. Nehmen wir also die ersten 14 Primzahlen und nehmen als die Potenzen diese Indizierung ? \quoteoff Ja. Die Gödelnummer ist also 220*321*518*... \quoteoff Also die Indizierung ist die Platzierung von jeden Buchstaben im Alphabet, oder nicht? Aber warum steht bei der Aufgabenstellung $A\mapsto 1, \ C\mapsto 2$ ? Ist B statt C gemeint? Oder betrachten wir nur die Buchstaben des Wortes, dann ist der zweite Buchstabe in alphabetischer Reihenfolge das C? Ausserdem was bedeutet dass das Zeichen M an Bandposition 0 geschrieben ist?


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6994
Wohnort: Niedersachsen
  Beitrag No.5, eingetragen 2017-07-26

\quoteon(2017-07-26 13:26 - mathletic in Beitrag No. 4) Also die Indizierung ist die Platzierung von jeden Buchstaben im Alphabet, oder nicht? Aber warum steht bei der Aufgabenstellung $A\mapsto 1, \ C\mapsto 2$ ? Ist B statt C gemeint? \quoteoff Das hatte ich zunächst für einen Schreibfehler (von Dir) gehalten. \quoteon Oder betrachten wir nur die Buchstaben des Wortes, dann ist der zweite Buchstabe in alphabetischer Reihenfolge das C? \quoteoff Das erscheint mir plausibel. das angegebene Programm funktioniert dann natürlich nicht. Sinnvollerweise müsste man die verwendete Menge an Bandsymbolen natürlich angeben, um die Aufgabe bearbeiten zu können. \quoteon Ausserdem was bedeutet dass das Zeichen M an Bandposition 0 geschrieben ist? \quoteoff Sehr gute Frage. Die Bandfunktion bildet von den natürlichen Zahlen (mit 0) nach T ab. Was es bedeuten soll, wenn nicht das erste Symbol auf der nullten Zelle steht, ist mir unklar. Würde man die Definition 3.25 wörtlich nehmen, so müsste man alle Zeichen links vom M ignorieren. Eventuell steht mehr dazu in der Definition des Begriffs "Bandfunktion". Der Zusammenhang zwischen dem Bandinhalt und der Bandfunktion ist so ja noch nicht ganz klar.


   Profil
mathletic
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 11.11.2013
Mitteilungen: 1596
  Beitrag No.6, vom Themenstarter, eingetragen 2017-07-26

\quoteon(2017-07-26 15:10 - Kitaktus in Beitrag No. 5) Sehr gute Frage. Die Bandfunktion bildet von den natürlichen Zahlen (mit 0) nach T ab. Was es bedeuten soll, wenn nicht das erste Symbol auf der nullten Zelle steht, ist mir unklar. Würde man die Definition 3.25 wörtlich nehmen, so müsste man alle Zeichen links vom M ignorieren. Eventuell steht mehr dazu in der Definition des Begriffs "Bandfunktion". Der Zusammenhang zwischen dem Bandinhalt und der Bandfunktion ist so ja noch nicht ganz klar. \quoteoff Es gibt folgende Definition des Begriffs "Bandfunktion": http://matheplanet.de/matheplanet/nuke/html/uploads/b/38039_deff.JPG


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6994
Wohnort: Niedersachsen
  Beitrag No.7, eingetragen 2017-07-26

Warum bildet jetzt die Bandfunktion in 3.3 von $\displaystyle \IZ$ nach T ab, während die Bandfunktion in 3.25 von $\displaystyle \IN_0$ nach T abbildet? Das passt nicht zusammen und ich wüsste nicht, wie man ohne Nachfrage beim Verfasser (oder anderen "Eingeweihten") dieses Dilemma auflösen könnte.


   Profil
mathletic
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 11.11.2013
Mitteilungen: 1596
  Beitrag No.8, vom Themenstarter, eingetragen 2017-07-26

\quoteon(2017-07-26 16:05 - Kitaktus in Beitrag No. 7) Das passt nicht zusammen und ich wüsste nicht, wie man ohne Nachfrage beim Verfasser (oder anderen "Eingeweihten") dieses Dilemma auflösen könnte. \quoteoff Ok. Wenn man das so macht wie wir eben besprochen hatten, ohne dass das M auf Position ) ist, ist es folgenderweise? Wenn wir das ganze Alphabet betrachten haben wir die Indizierung: $A\mapsto 1, \ B\mapsto 2, \ C\mapsto 3, \ D\mapsto 4\ldots$ Wir haben also folgendes: $G(\text{TURINGMASCHINE})=\prod_{i=0}^{\infty}p_{i+1}^{\text{ind}(\beta (i))} \\ = \prod_{i=0}^{13}p_{i+1}^{\text{ind}(\beta (i))}\prod_{i=14}^{\infty}p_{i+1}^{\text{ind}(\beta (i))} \\ = \prod_{i=0}^{13}p_{i+1}^{\text{ind}(\beta (i))}\prod_{i=14}^{\infty}1 \\ = \prod_{i=0}^{13}p_{i+1}^{\text{ind}(\beta (i))} \\ = p_1^{\text{ind}(T)}\cdot p_2^{\text{ind}(U)}\cdot p_3^{\text{ind}(R)}\cdot p_4^{\text{ind}(I)}\cdot p_5^{\text{ind}(N)}\cdot p_6^{\text{ind}(G)}\cdot p_7^{\text{ind}(M)}\cdot p_8^{\text{ind}(A)}\cdot p_9^{\text{ind}(S)}\cdot p_{10}^{\text{ind}(C)} \cdot p_{11}^{\text{ind}(H)}\cdot p_{12}^{\text{ind}(I)}\cdot p_{13}^{\text{ind}(N)}\cdot p_{14}^{\text{ind}(E)} \\ = 2^{20}\cdot 3^{21}\cdot 5^{18}\cdot 7^{9}\cdot 11^{14}\cdot 13^{7}\cdot 17^{13}\cdot 19^{1}\cdot 23^{19}\cdot 29^{3} \cdot 31^{8}\cdot 37^{9}\cdot 41^{14}\cdot 43^{5}$ Wenn wir nur die Buchstaben des Wortes betrachten haben, also $\{T, U, R, I, N, G, M, A, S, C, H, E\}=\{A, C, E, G, H, I, M, N, R, S, T, U\}$ wir die Indizierung: $A\mapsto 1, \ C\mapsto 2, \ E\mapsto 3, \ G\mapsto 4, \ H\mapsto 5, \ I\mapsto 6, \ M\mapsto 7, \ N\mapsto 8, \ R\mapsto 9, \ S\mapsto 10, \ T\mapsto 11, \ U\mapsto 12$ Wir haben also folgendes: $G(\text{TURINGMASCHINE})=\prod_{i=0}^{\infty}p_{i+1}^{\text{ind}(\beta (i))} \\ = \prod_{i=0}^{13}p_{i+1}^{\text{ind}(\beta (i))}\prod_{i=14}^{\infty}p_{i+1}^{\text{ind}(\beta (i))} \\ = \prod_{i=0}^{13}p_{i+1}^{\text{ind}(\beta (i))}\prod_{i=14}^{\infty}1 \\ = \prod_{i=0}^{13}p_{i+1}^{\text{ind}(\beta (i))} \\ = p_1^{\text{ind}(T)}\cdot p_2^{\text{ind}(U)}\cdot p_3^{\text{ind}(R)}\cdot p_4^{\text{ind}(I)}\cdot p_5^{\text{ind}(N)}\cdot p_6^{\text{ind}(G)}\cdot p_7^{\text{ind}(M)}\cdot p_8^{\text{ind}(A)}\cdot p_9^{\text{ind}(S)}\cdot p_{10}^{\text{ind}(C)} \cdot p_{11}^{\text{ind}(H)}\cdot p_{12}^{\text{ind}(I)}\cdot p_{13}^{\text{ind}(N)}\cdot p_{14}^{\text{ind}(E)} \\ & = 2^{11}\cdot 3^{12}\cdot 5^{9}\cdot 7^{6}\cdot 11^{8}\cdot 13^{4}\cdot 17^{7}\cdot 19^{1}\cdot 23^{10}\cdot 29^{2} \cdot 31^{5}\cdot 37^{6}\cdot 41^{8}\cdot 43^{3} $


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6994
Wohnort: Niedersachsen
  Beitrag No.9, eingetragen 2017-07-26

Ja, so hätte ich das auch gemacht.


   Profil
mathletic
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 11.11.2013
Mitteilungen: 1596
  Beitrag No.10, vom Themenstarter, eingetragen 2017-07-26

\quoteon(2017-07-26 17:52 - Kitaktus in Beitrag No. 9) Ja, so hätte ich das auch gemacht. \quoteoff Ok!! Vielen Dank!! :-)


   Profil
mathletic
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 11.11.2013
Mitteilungen: 1596
  Beitrag No.11, vom Themenstarter, eingetragen 2019-10-09

Ich gucke eine ähnliche Aufgabe wie der erste Teil. Wir haben die Zahl $706737922567786324304462189150536772513339293263220644 =2^2\cdot 3\cdot 59^5\cdot 103\cdot 149^2\cdot 353\cdot 607\cdot 823^4\cdot 1409\cdot 1873^2\cdot 4201^3$ Wir haben folgende Tabelle $(i,j) \ \ \ \sigma_2 \ \ \ P\sigma_2 $ $(1,3) \ \ \ 13 \ \ \ 41 $ $(1,4) \ \ \ 17 \ \ \ 59 $ $(2,3) \ \ \ 27 \ \ \ 103 $ $(2,4) \ \ \ 35 \ \ \ 149 $ $(3,3) \ \ \ 55 \ \ \ 257 $ $(3,4) \ \ \ 71 \ \ \ 353 $ $(4,3) \ \ \ 111 \ \ \ 607 $ $(4,4) \ \ \ 143 \ \ \ 823 $ $(5,3) \ \ \ 223 \ \ \ 1409 $ $(5,4) \ \ \ 287 \ \ \ 1873 $ $(6,3) \ \ \ 447 \ \ \ 3163 $ $(6,4) \ \ \ 575 \ \ \ 4201 $ Alle Primzahlen kommen in der Tabelle vor. Folgt es dass die Zahl die Gödelnummer einer Turingmaschine ist?


   Profil
mathletic
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 11.11.2013
Mitteilungen: 1596
  Beitrag No.12, vom Themenstarter, eingetragen 2019-10-10

Wie bekommt man davon die entsprechende Turingtafel?


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 02.12.2013
Mitteilungen: 284
  Beitrag No.13, eingetragen 2019-10-12

\quoteon(2019-10-10 21:46 - mathletic in Beitrag No. 12) Wie bekommt man davon die entsprechende Turingtafel? \quoteoff Für die konkrete Aufgabe kann bzw. will ich nicht helfen. Vielleicht könnte ich es, aber bei solchen nutzlosen und überflüssigen Fleißaufgaben verweigere ich mich. Statt dessen eine Anmerkung zum Thema dieses Threads: In der Berechenbarkeitstheorie geht es darum, was berechenbar und insbesondere was NICHT berechenbar ist. Man betrachtet dabei Berechungsformalismen, bei denen Programme als Eingabedaten Programme nebst Eingabedaten für diese Programme erwarten und das Eingabeprogramm mit den gegebenen Daten dann ausführen. Die Berechenbarkeitstheorie wurde (als exotisches Teilgebiet der formalen Logik) zu Beginn des letzen Jahrhunderts entwickelt, also zu einer Zeit als es keine programmierbaren Rechner gab. Man verwendete dazu ein mathematisches Modell eines programmierbaren Rechners, nämlich die Turingmaschine. Soll ein Turingprogramm A ein anderes Turingprogramm B als Eingabe erhalten, so muß B als Datum repräsentiert werden. Da man sich in der Berechbarkeitstheorie auf arithmetische Funktionen beschränkt, muß das Turingprogramm B als natürliche Zahl repräsentiert werden. Dazu wird B gödelisiert. Die Gödelnummer von B ist also die Repräsentation des Turingprogramms B durch eine Zahl, die das Turingprogramm A dann als Eingabe erhält. Das war vor 100 Jahren gut und richtig. Heute kann man jedoch (leistungsfähige) Rechner bei Karstadt kaufen, es gibt zahllose Programmiersprachen usw. Unsere Rechner sind von-Neumann-Maschinen und keine Turingmaschinen. In jeder gängigen Programmiersprache können Programme Programme verarbeiten, man denke nur an einen in C geschriebenen C-Compiler, einen in JAVA implementierten Interpreter für JAVA Programme usw. In manchen Programmiersprachen gibt es keinen Unterschied zwischen Programmcode und Programmdaten (z.B. bei LISP), in anderen Programmiersprachen werden Programme als Zeichenreihen (etwa "array 1..n of ASCII") repräsentiert. Man kann die Berechenbarkeitstheorie damit auf modernen, gängigen Rechenmodellen entwickeln, die obendrein den Studenten aus ihrer Praxisarbeit bekannt sind, anstatt sich mit den barocken Turingmaschinen herumzuschlagen. Insbesondere die Gödelisierung von Programmen entfällt dabei, bzw. ist trivial und einleuchtend. Als Beispiel, wie die Berechenbarkeitstheorie modern, anschaulich und verständlich präsentiert werden kann, sei das Lehrbuch Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997. genannt das unter http://www.diku.dk/~neil/comp2book2007/book-whole.pdf im freien Download erhältlich ist. Studenten in Übungsaufgaben mit Gödelisierungen von Turingmaschinen zu belästigen, wie es hier offenbar der Fall ist, ist didaktisch völlig wertlos und grober Unfug. Obendrein verdeckt es die wesentlichen Inhalte der Berechbarkeitstheorie und schreckt viele Sudenten von der Thematik ab, denn wer hat schon Interesse daran mit Primzahlprodukten herumzurechnen. Das ist doch nur zeitraubend, fehleranfällig und langweilig. Leider ist es so, daß die meisten Dozenten ihre Vorlesung didaktisch daran ausrichten, was sie selbst als Studenten erleiden mußten, und so wird der Stoff dann so präsentiert wie zu Gödels Zeiten. Hoffentlich finden Studenten mal den Mut, ihre Dozenten nach dem didaktischen Wert solcher Rechenaufgaben zu fragen. Denn Universitäten werden durch Steuermittel finanziert und Studenten haben Anspruch auf gute Lehre.


   Profil
mathletic hat die Antworten auf ihre/seine Frage gesehen.
mathletic hatte hier bereits selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]