{"entities":{"Q1106201":{"pageid":1116950,"ns":120,"title":"Item:Q1106201","lastrevid":67011879,"modified":"2026-04-12T14:19:09Z","type":"item","id":"Q1106201","labels":{"en":{"language":"en","value":"A note on arbitrarily complex recursive functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4061220"}},"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":"Q1106201$8A4E56D6-BB3B-47CB-B063-D068CC077D3B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"28a27acc0d2e2198ce5d4c69168e3871e9ebecb8","datavalue":{"value":{"text":"A note on arbitrarily complex recursive functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106201$7138F50E-F2F0-45DF-9CB8-CE0AF37EECDC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8763b92684337dbb8decda4c5465fba8147c470a","datavalue":{"value":"0651.03032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106201$2838AF85-E0AD-4CAE-905F-B71ED246CF13","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b9430876ee67798e04f590d506b46f0dbca256d","datavalue":{"value":{"entity-type":"item","numeric-id":674180,"id":"Q674180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106201$4AFA3B19-0CB4-47D4-BF12-AF2C7F389E6E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106201$C6F61A6A-9713-46DB-87B2-50028EB15889","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1106201$000C0B3F-7450-4D74-8698-9D02BDDF3800","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d24c6fc4f1c607b77877d1a01d0ee2ada9c47c27","datavalue":{"value":"\\textit{M. Rabin} [Degree of difficulty of computing a function, Hebrew University Technical Report 2 (1960)] first proved that there exist almost everywhere arbitrarily complex recursive functions with range \\(\\{\\) 0,1\\(\\}\\) which was generalized to the machine independent case by \\textit{M. Blum} [J. Assoc. Comput. Mach. 14, 322-336 (1967; Zbl 0155.015)]. This paper gives a best possible generalization of that result. Let \\(\\phi_ 0,\\phi_ 1,..\\). be an arbitrary acceptable programming system, \\(\\Phi_ 0,\\Phi_ 1,..\\). an arbitrary abstract complexity measure on \\(\\phi_ 0,\\phi_ 1,... \\). For any recursive functions f and g, f is finite variant of g iff \\(\\{\\) \\(x| f(x)\\neq g(x)\\}\\) is finite; f is g-sparse iff \\(\\forall x[f(x)\\neq 0\\to f(y)=0\\) for all y's such that \\(x<y\\leq x+g(x)]\\). Main result: For any recursive functions g and h with g(x)\\(\\geq x\\) for all x, there exists a \\(\\{\\) 0,1\\(\\}\\)-valued g-sparse recursive function f such that, for any program i, if \\(\\phi_ i\\) is a finite variant of f then \\(\\Phi_ i(x)>h(x)\\) for all but finitely many x.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106201$3EC0A2AD-F92A-4D2D-A694-AFECEB934FD6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106201$70C2A5A3-256C-4F44-BDFB-22F521E824EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106201$AF6C0520-E419-4EA1-AE68-123097A04C6D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4bdc74c8c107c787db8a0d34dd2e70ca4acf83c7","datavalue":{"value":"4061220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106201$5618A9A3-E517-4817-B8AF-0B7E2BD34F4A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd8bdc873b702857b5cc16dd771b5ad8a56c8d55","datavalue":{"value":"arbitrarily complex recursive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106201$6513867B-816B-49E1-AD3E-4F47F4875A17","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"488d048a8186245364a15937ead16119e53adf2e","datavalue":{"value":{"entity-type":"item","numeric-id":1176062,"id":"Q1176062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106201$A0F8F398-2D3E-43F4-9B32-44A6D400B06C","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":"Q1106201$8F6FAEF2-BA59-4181-9F32-6899F4517F8B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d7bea30736f37fdc0aa5d202e2b438154d131841","datavalue":{"value":"https://doi.org/10.1305/ndjfl/1093637869","type":"string"},"datatype":"url"},"type":"statement","id":"Q1106201$6C11E22C-6137-4E57-A3A4-74196B232FDA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d7406898d36036efa2e3db12141631229ba12909","datavalue":{"value":"W2051066685","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106201$7DD23C5A-EBA8-4287-91E8-C1731728BCAE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9b4d1cb5c89142889d6052b8ca96c4c299f174b1","datavalue":{"value":"10.1305/NDJFL/1093637869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106201$B8648F01-3608-4AAD-A238-E065DD3C242A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db4cfc293cbdae5219c7985db0d85c7df379399e","datavalue":{"value":{"entity-type":"item","numeric-id":909459,"id":"Q909459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcda6ab9733fb3d8182554ef3b0ffed045e98d23","datavalue":{"value":{"amount":"+0.8118391036987305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106201$029B6AA5-CBDD-4FFA-9D12-5596E4747D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"243a6260f9e0186068f9e8fc27d9d6b63fcdf40f","datavalue":{"value":{"entity-type":"item","numeric-id":3803097,"id":"Q3803097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aee7bfc0fa53de97c152de3d028f54797f3dd9b4","datavalue":{"value":{"amount":"+0.7562206387519836","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106201$CBDC2837-95EE-4121-BA19-EB8AF16421A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d4f945d05228f1c005066abe1f647c85d4d7aa9","datavalue":{"value":{"entity-type":"item","numeric-id":5958280,"id":"Q5958280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be7baa845f490ffafac81f9ef541e4adc3c39c1c","datavalue":{"value":{"amount":"+0.7473207116127014","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106201$F17DDF74-535F-46C4-9DD1-26D6B6E5F52E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f93f00bc633405b69ca797119646e486efad789","datavalue":{"value":{"entity-type":"item","numeric-id":4218151,"id":"Q4218151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf5d79fefa41e2f0cec91380622a3a07ff41771d","datavalue":{"value":{"amount":"+0.7473204731941223","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106201$B1E354C6-9D91-4B8D-96BC-3B81DA08B1EC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on arbitrarily complex recursive functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_arbitrarily_complex_recursive_functions"}}}}}