{"entities":{"Q1816488":{"pageid":1827230,"ns":120,"title":"Item:Q1816488","lastrevid":69034845,"modified":"2026-04-13T03:52:50Z","type":"item","id":"Q1816488","labels":{"en":{"language":"en","value":"Non-definability of the Ackermann function with type 1 partial primitive recursion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 950073"}},"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":"Q1816488$16C82EE8-4BD7-46E3-8E4E-2AD720DB7EE2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"584a64801af31a766cff0a7afa32eb0b6f07f2bd","datavalue":{"value":{"text":"Non-definability of the Ackermann function with type 1 partial primitive recursion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1816488$8C4BF5DE-8227-452A-BB01-DCC3AF669EAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a3f60461f25f4104b6f8505a80fc5ba7e64fa3cc","datavalue":{"value":"0894.03021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1816488$7F0319D9-0397-4398-8E0D-37E3DDFF18F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"35dac4a82d7994982b6498e99b5b158ff9ad79c7","datavalue":{"value":{"entity-type":"item","numeric-id":688506,"id":"Q688506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1816488$BA30BDCD-CC55-4A0D-B45E-3CB485515ACF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a0a7cd28a9f85b9c6ad57bd5bb1ae477bfe37846","datavalue":{"value":{"entity-type":"item","numeric-id":114337,"id":"Q114337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1816488$64D7872B-1E7E-468B-BC29-D1ED5B18CBDD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41120fa38ca7c0e02cc8570d48b8fe3190cff57c","datavalue":{"value":{"time":"+1996-12-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1816488$87892A0E-1E44-4954-B757-E69FEB3E7F3E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b05dd55ada801c6cacff5d9fb81bd3486ce1479","datavalue":{"value":"The paper builds on a simply typed term system \\({\\mathcal {PR}}^\\omega\\) [cf. the author, Ann. Pure Appl. Logic 75, 153-178 (1995; Zbl 0832.68057)] providing a notion of partial primitive recursive functional on arbitrary Scott domains \\(D_\\sigma\\) that includes a suitable concept of parallelism. Computability on the partial continuous functionals seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (SCVR) is not reducible to partial primitive recursion. The aim of the paper is to present an extension \\({\\mathcal {PR}^{\\omega e}}\\) that is closed under SCVR and yet stays within the realm of subrecursiveness in an appropriate extended sense. The twist are certain type 1 G\u00f6del recursors \\({\\mathcal R}_k\\) for simultaneous partial primitive recursion. Formally, given objects \\(\\vec g\\), \\(\\vec H\\), \\(x\\), \\(i\\) of appropriate types, \\({\\mathcal R}_k \\vec g \\vec H xi\\) denotes a function \\(f_i\\) of type \\(\\iota\\to \\iota\\), however, \\({\\mathcal R}_k\\) is modelled such that \\(f_i\\) is a finite element of \\(D_{\\iota\\to \\iota}\\) or in other words, a partial sequence. It is shown that the growth of any function \\(f\\) definable in \\({\\mathcal {PR}}^{\\omega e}\\) can be dominated by a primitive recursive function in suitable codes of \\(f\\)'s arguments. Thus, the Ackermann function is not definable in \\({\\mathcal {PR}}^{\\omega e}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1816488$6C00CD04-0953-414C-AD68-599F71D15090","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1816488$F4D8D624-B89A-4796-94EF-4C43FF1EB174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1816488$C3357F3B-9CC1-41B6-8108-65B724F90A6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"40d293f5d2161e80872b42afb12a3fc45e5d1401","datavalue":{"value":"68Q55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1816488$2BCB5FF5-7E4E-4A4E-B7B3-7ADF4E1826A3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a2694dae0286cd931a7ceee0af58c636d9cd41fb","datavalue":{"value":"950073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1816488$41206A2B-591C-4D93-94CB-F2116E52118F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93fead43f3e315dc245bca6d8df97d8d8d8b10ba","datavalue":{"value":"simply typed term system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1816488$F368E6CE-C51B-4111-A310-B765141ED294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fba21d4de3910cb9e40618fdacc13e6d95dc968e","datavalue":{"value":"partial primitive recursive functional","type":"string"},"datatype":"string"},"type":"statement","id":"Q1816488$F30FEC29-5C75-4897-8D88-CCB632B662A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b84f3daf8e8ec671c2d12787f1264514c92ea524","datavalue":{"value":"continuous functionals","type":"string"},"datatype":"string"},"type":"statement","id":"Q1816488$EF1EB250-7A11-499E-BA85-3DB0C432BBDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dd512973f26c724b5c67f2bb727dbc59ee0c491","datavalue":{"value":"subrecursiveness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1816488$ACB1BE57-40BE-49AC-B963-8F89C07A8274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b68af17186eb266e6ae21b31bf2de8f0d12ea77","datavalue":{"value":"G\u00f6del recursors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1816488$06888820-F239-4214-A0A5-6D7B04D96E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c366d9e44e0d6a9e2cdc753868eab05ee1b2ecc","datavalue":{"value":"Ackermann function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1816488$653698E8-9224-40BF-84A0-F5CEAF5B3537","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":"Q1816488$22F68289-2E27-4AD4-BB17-32866DB74CBC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa544f4101d04939fe3c06adde894db2ae5884d6","datavalue":{"value":"https://doi.org/10.1007/s001530050077","type":"string"},"datatype":"url"},"type":"statement","id":"Q1816488$BCFE26DC-4269-4517-A790-78F986CDACC7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bcbc8c1628a03fddced075464403f63803e50357","datavalue":{"value":"W1967612355","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1816488$2D597800-76DE-4BD3-A1EA-92B286F40AF5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c8b6c6c69ed4d947fb272b513d9c43e96ebf52b4","datavalue":{"value":"10.1007/S001530050077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1816488$62781DC2-53C1-4026-8681-A6A27E95CDD2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef764f97d8bc3a6afce16e9594d609153bf13b82","datavalue":{"value":{"entity-type":"item","numeric-id":5190202,"id":"Q5190202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfe0c1e62bbdb267c1adb2a3c2418a947c7ce355","datavalue":{"value":{"amount":"+0.7458327412605286","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":"Q1816488$C749C30C-FF37-4ED8-AA3A-B6FA717E263D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e8920f87e30043edc9dcb8a727081482c062449","datavalue":{"value":{"entity-type":"item","numeric-id":3689173,"id":"Q3689173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bbffe490d3ca1245b3dd07be6879c181c121b03","datavalue":{"value":{"amount":"+0.7436150312423706","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":"Q1816488$BCD8618D-D5AF-40EE-9DA1-471F78C1DF6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0762ec8cefdff9e7e3bba0857c0f2be3ec2ca3a","datavalue":{"value":{"entity-type":"item","numeric-id":1283120,"id":"Q1283120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d5815a1133bf80daf7cd3c25eca0fdaacbcffef","datavalue":{"value":{"amount":"+0.7436100840568542","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":"Q1816488$6775D1EA-2C83-4027-8725-DED9C99DEADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c13854bae0fd74afb256d1ebac556515fc1741c0","datavalue":{"value":{"entity-type":"item","numeric-id":1306824,"id":"Q1306824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b13c9c82385e889ff81bab1bdaf754e71c67760e","datavalue":{"value":{"amount":"+0.7368409633636475","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":"Q1816488$5B8D12FD-F887-448D-B58C-85B32AE0E251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5ccf6c9a9f738dfc870202c18d8fd4ec31bd38c","datavalue":{"value":{"entity-type":"item","numeric-id":5427433,"id":"Q5427433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89f4584e3c683d398776ad01b4eed48da259ad74","datavalue":{"value":{"amount":"+0.7349860668182373","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":"Q1816488$61A56B29-925F-4CF6-97BE-79D95EE57D0D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Non-definability of the Ackermann function with type 1 partial primitive recursion","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Non-definability_of_the_Ackermann_function_with_type_1_partial_primitive_recursion"}}}}}