{"entities":{"Q5923140":{"pageid":8056574,"ns":120,"title":"Item:Q5923140","lastrevid":41399718,"modified":"2025-04-29T08:52:04Z","type":"item","id":"Q5923140","labels":{"en":{"language":"en","value":"General recursive functions of natural numbers."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2525168"}},"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":"Q5923140$B133B27E-2372-4EF7-ABBF-ABFED9958DE9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"23047a9122846ebcff042e227bf0d2612aa75b97","datavalue":{"value":{"text":"General recursive functions of natural numbers.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5923140$C9339D9F-BBCB-4D82-875D-26F7B30372B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7201d77796289c2d908304e2dd5372147236377","datavalue":{"value":"62.0044.02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5923140$851CD199-64A5-4E30-B052-35F0B4FAD02D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b0c6f36e3db23c3678dd302a30ba4b4428042fc0","datavalue":{"value":"10.1007/BF01565439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5923140$5F5E4619-476B-47FE-9146-5CC32068CC8E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7016073dc3661ad2b8fcf740b72e135f31d59f23","datavalue":{"value":{"entity-type":"item","numeric-id":166142,"id":"Q166142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5923140$DDAAE2E1-FB94-4BCC-ACD8-AB1FD868F021","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":"Q5923140$730F1D15-1EBE-4270-9CC7-BA9F22C61CFD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"00fc640f0f90747c414c03791567bb66111fe704","datavalue":{"value":"https://eudml.org/doc/159849","type":"string"},"datatype":"url"},"type":"statement","id":"Q5923140$5DBB72C3-FFF2-41E0-9642-BA59138FD060","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"078998b3caa87a656c8b453f0722ef1d5d7613db","datavalue":{"value":"Bekanntlich gibt es verschiedene Definitionen des Begriffes ``rekursive Funktion''. Man hat z. B. die primitiven Rekursionen, n\u00e4mlich Rekursionen nach blo\u00df einer Variablen, und die simultanen Rekursionen nach mehreren Variablen, welche nicht auf die primitiven zur\u00fcckf\u00fchrbar sind. Deshalb ist es w\u00fcnschenswert, einen allgemeinen Begriff ``rekursive Funktion'' zu definieren. In vorliegender Arbeit wird in \\S\\,1 eine solche allgemeine von \\textit{J. Herbrand} und \\textit{K. G\u00f6del} herr\u00fchrende Definition aufgestellt. Weiter wird in \\S\\,1 unter Anwendung der bekannten \\textit{G\u00f6del}schen Numerierung aller Formeln der Satz bewiesen: Jede rekursive Funktion, und zwar in dem hier definierten allgemeinen Sinn, kann in der Form  \\[  \\psi(\\varepsilon y[\\varrho(x_1, \\dots, x_n, y) = 0])  \\]  geschrieben werden, wo \\(\\psi\\) und \\(\\varrho\\) primitiv-rekursive Funktionen sind und  \\[  (x_1, \\dots, x_n] (Ey) [\\varrho (x_1, \\dots, x_n, y) = 0]  \\]  gilt, w\u00e4hrend \\(\\varepsilon y [\\varrho (x_1, \\dots, x_n, y) = 0]\\) \\ die kleinste Zahl \\(y\\) \\ bedeutet, f\u00fcr welche \\linebreak \\(\\varrho (x_1, \\dots, x_n, y) = 0\\) \\ stattfindet. Die Umkehrung dieses Satzes gilt auch; Verf. zeigt n\u00e4mlich, da\u00df \\ \\(\\varepsilon y[R(x_1, \\dots, x_n, y)]\\) \\ rekursiv ist, wenn \\ \\(R(x_1, \\dots, x_n, y)\\) \\ eine solche rekursive Relation ist, da\u00df \\ \\((x_1, \\dots, x_n) (Ey)R(x_1, \\dots, x_n, y)\\) \\ gilt.  In \\S\\,2 wird die Frage studiert, welche Gleichungssysteme rekursive Funktionen definieren. Die wichtigsten Ergebnisse sind: Diejenigen Systeme, welche das tun, k\u00f6nnen nicht rekursiv abgez\u00e4hlt werden, d. h. es ist nicht m\u00f6glich, da\u00df die Zahlen, welche bei der \\textit{G\u00f6del}schen Numerierung diesen Systemen zugeordnet werden, die sukzessiven Werte einer rekursiven Funktion darstellen. H\u00e4tte man n\u00e4mlich eine solche Abz\u00e4hlung, so k\u00f6nnte man mit Hilfe des Diagonalverfahrens eine neue Funktion rekursiv definieren. Ebenso ist ein rekursives Verfahren nicht m\u00f6glich zur Entscheidung dar\u00fcber, welche Gleichungssysteme rekursive Funktionen definieren, d. h. es ist nicht m\u00f6glich, eine rekursive Funktion der Systemnummer zu bilden, welche die Werte 0 oder 1 annimmt, je nachdem das System eine rekursive Funktion definiert oder nicht. Es wird weiter gezeigt, da\u00df gewisse formallogische Systeme unentschuldbare S\u00e4tze der Form  \\[  (x)(Ey)[\\varrho(x, y) = 0]  \\]  enthalten, wo \\(\\varrho\\) primitiv-rekursiv ist. Verf. beweist auch, da\u00df es nicht-rekursive Funktionen \\(\\tau(x)\\) gibt, die so definierbar sind: \\(\\tau(x) = 0\\) oder 1, je nachdem \\((y) [\\varrho(x, y) = 0]\\) gilt oder nicht, wobei \\(\\varrho\\) primitiv-rekursiv ist.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5923140$674547C7-CDD1-4089-8AA7-8DF5C824562A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a02615b7555541fab7ab019e77a319b319556a86","datavalue":{"value":"2525168","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5923140$A88E1D19-7F09-4F59-80F2-56A50F8B17DE","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f9ff5817c1ef3db8d46dec864a560d7b6a510b7a","datavalue":{"value":"Q56037875","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5923140$F5514F0C-8220-4B28-9FEA-1BCA07EB608E","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":"Q5923140$6661F142-9FB6-4BDD-89CD-01315B5A44BD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88100a68597a0f0388ad29f5d27eac96d4997788","datavalue":{"value":{"entity-type":"item","numeric-id":1840177,"id":"Q1840177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5923140$0ACAC7FF-ED73-4BB9-BD31-A5EADCEE9BEE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7fdd3d6b9cc141f6d005556f1ba7c68d933a429","datavalue":{"value":{"entity-type":"item","numeric-id":6672169,"id":"Q6672169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5923140$E27B9EE3-DE36-4A43-9BA1-3041BD65C62E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5923140","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5923140"}}}}}