{"entities":{"Q5923142":{"pageid":8056577,"ns":120,"title":"Item:Q5923142","lastrevid":41301398,"modified":"2025-04-28T13:18:23Z","type":"item","id":"Q5923142","labels":{"en":{"language":"en","value":"An unsolvable problem of elementary number theory."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2525171"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5923142$7A579770-8DB0-4F67-9E4F-43BFCB58720A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7441e6d6bc579dfdbd5438c1ccd550e7365a6d91","datavalue":{"value":{"text":"An unsolvable problem of elementary number theory.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5923142$06589D7B-5EC4-467A-8776-4000BCD8AB83","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b9509728ce8e80bbe0c9e768071f82deae5a419c","datavalue":{"value":"62.0046.01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5923142$8451AB8B-5584-4E61-9B11-723F21A7A638","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa9b9066839cd5352f42c5cbfdc2176385fa952f","datavalue":{"value":"10.2307/2371045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5923142$194A4280-36C3-43EE-8491-2E60A3A4CB32","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1add02162fef49a66552187e850c2369475498a6","datavalue":{"value":{"entity-type":"item","numeric-id":559377,"id":"Q559377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5923142$8BDF557C-E200-41E5-80E3-04807AD84293","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b4fd24e618322be35613a64fc5f86a90753a27b1","datavalue":{"value":{"time":"+1936-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5923142$6CD8DA9B-3249-4F22-80CC-7EB3B6237AF5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"494f10097ce50fac8b5b30e90ca34a810d81a9f4","datavalue":{"value":"https://semanticscholar.org/paper/60400c043b2624f9cfc2d8daa0f45f3c1d524de3","type":"string"},"datatype":"url"},"type":"statement","id":"Q5923142$71DC1EE7-E167-4E6A-B74D-6F68A7798F6D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1f8ff574f67a3801296d617121f976c31419e12a","datavalue":{"value":"Betrachten wir eine Klasse von Aussagen der elementaren Zahlentheorie, die eine freie Variable \\(n\\) (\\(n\\) positiv und ganz) oder auch mehrere derartige Variable \\(x_1, x_2, \\dots, x_m\\) enthalten, z. B. die Aussage: Es gibt positive ganze Zahlen \\(x, y, z\\), so da\u00df \\(x^n + y^n = z^n\\). Zu jeder derartigen Klasse von Aussagen geh\u00f6rt eine zahlentheoretische Funktion \\(f\\), so da\u00df \\(f (n)\\) bzw. \\(f(x_1, x_2, \\dots, x_m)\\) den Wert 2 oder 1 hat, je nachdem ob f\u00fcr \\(n\\) bzw. \\(x_1, x_2, \\dots, x_m\\) die betreffende Aussage richtig oder falsch ist. Die Kenntnis eines Verfahrens, das uns f\u00fcr jedes \\(n\\) die Entscheidung \u00fcber die Richtigkeit der Aussage erm\u00f6glichen w\u00fcrde, b\u00f6te uns die M\u00f6glichkeit, den Wert von \\(f(n)\\) f\u00fcr jedes gegebene \\(n\\) zu berechnen. Das Umgekehrte ist nat\u00fcrlich ebenfalls der Fall. Funktionen der angegebenen Art, die die Eigenschaft der Berechenbarkeit besitzen, wollen wir rekursiv nennen. \\textit{Church} gibt nun eine Funktion an, von der er beweist, da\u00df sie nicht rekursiv ist. Die Bildung dieser Funktion steht in engem Zusammenhang mit dem \\textit{Church}schen System der Logik (\\textit{A. Church}, Proc. nat. Acad. Sci. USA 21 (1935), 275-281; F. d. M. \\(61_{\\text{I}}\\), 55) und dem dort gebrauchten Begriff der Konversion. Zwei Formeln \\(\\mathfrak A\\) und \\(\\mathfrak B\\) des \\textit{Church}schen Systems hei\u00dfen durch Konversion ineinander \u00fcberf\u00fchrbar, im (metamathematischen) Zeichen \\(\\mathfrak A\\) conv \\(\\mathfrak B\\), wenn \\(\\mathfrak B\\) sich aus \\(\\mathfrak A\\) nach den \\textit{Church}schen Regeln zur Ableitung neuer Formehl gewinnen l\u00e4\u00dft. Nun l\u00e4\u00dft sich jeder Formel des \\textit{Church}schen Systems nach dem Verfahren von \\textit{G\u00f6del} (\\textit{K. G\u00f6del}, Mh. Math. Phys. 38 (1931), 173-198; F. d. M. \\(57_{\\text{I}}\\), 54) eine positive ganze Zahl als Repr\u00e4sentant zuordnen. \\(\\mathfrak A\\) conv \\(\\mathfrak B\\) entspricht dann eine zahlentheoretische Aussage und eine zahlentheoretische Funktion der oben genannten Art mit zwei Argumenten. Von dieser Funktion zeigt der Verf. nun, da\u00df die Annahme der Rekursivit\u00e4t auf einen Widerspruch f\u00fchrt. Das w\u00fcrde also bedeuten, da\u00df es schon Probleme der elementaren Zahlenlehre gibt, die nicht entscheidbar sind. -- Um den Beweis f\u00fchren zu k\u00f6nnen, mu\u00df der Verf. selbstverst\u00e4ndlich den Begriff der Rekursivit\u00e4t formal genau bestimmen. Es fragt sich nun, ob sich dieser Begriff ein f\u00fcr allemal in einem formalen System genau festlegen l\u00e4\u00dft und ob nicht jedes derartige System einer unendlichen Erweiterung f\u00e4hig ist. Oder um die Frage zun\u00e4chst einfacher zu formulieren: Gibt es zahlentheoretische Funktionen, die zwar die Eigenschaft der Berechenbarkeit besitzen, aber nicht ``rekursiv'' im \\textit{Church}schen Sinne sind? Diese Frage ist sicher nicht einfach zu entscheiden, denn tats\u00e4chlich ist die \\textit{Church}sche Definition der Rekursivit\u00e4t die allgemeinste, die wir kennen. (\u00dcber andere Definitionen der Rekursivit\u00e4t siehe z. B. \\textit{D. Hilbert}, \\textit{P. Bernays}, Grundlagen der Mathematik I (1934; F. d. M. \\(60_{\\text{I}}\\), 17-19), Kap. 7.) Jedenfalls gibt uns die vorliegende Arbeit eine gewisse Erkl\u00e4rung daf\u00fcr, weshalb so viele verh\u00e4ltnism\u00e4\u00dfig einfach zu formulierende Probleme der elementaren Zahlentheorie so gro\u00dfe Schwierigkeiten bieten und bisher der Inangriffnahme trotzten.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5923142$DE3C39E5-22B0-414D-B32F-2729288F9D43","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ba50dc7fb59aaf06fc25ea8697a3dd0eb11267f4","datavalue":{"value":"2525171","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5923142$711595D2-B065-4AD8-B54F-7A58DA135BEC","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b5700fe55b21b52523df99a8bd7c0a74ed2a99ef","datavalue":{"value":"Q55868867","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5923142$99508FCA-FBF1-4EEE-B43B-C07B876F901D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5923142$DD6D6FA0-C3E2-41CF-8075-E7C34D75DDFE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a839741d30aa2f0640ad285a3aa46350c2860879","datavalue":{"value":"W2323777246","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5923142$6F47D59F-B6D4-45A0-A504-94AB730292C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a542fc4bb188d61d47e008267b4067a52a2819a","datavalue":{"value":{"entity-type":"item","numeric-id":6480754,"id":"Q6480754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5923142$14FC72DC-A63E-4EF3-B380-09B91A1FCCF9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5923142","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5923142"}}}}}