{"entities":{"Q1842381":{"pageid":1853123,"ns":120,"title":"Item:Q1842381","lastrevid":73521606,"modified":"2026-04-14T16:19:17Z","type":"item","id":"Q1842381","labels":{"en":{"language":"en","value":"Discrete families of recursive functions and index sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 745964"}},"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":"Q1842381$30E96DF9-9872-4DFE-8F36-4FA3A8239BCF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3962ec3b50a47737f6d028ed405717ff1576f7f0","datavalue":{"value":{"text":"Discrete families of recursive functions and index sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1842381$8A602120-AA22-448D-B001-EA26C0D5A2C3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"29caafcda43925b73529eda525348536eed9dc1e","datavalue":{"value":"0828.03014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842381$BD2B2990-C7AF-4386-AAED-94A90CDC2319","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6a898dc096311832f37baf56601c5c81a149f094","datavalue":{"value":"10.1007/BF00739994","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842381$1002FF82-B15C-42F5-8B9D-8BDF6226BD63","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$2DF72158-5AFF-4292-B3A2-7A16EC87F572","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ef3ca3322541db05049091162b21145bd512b130","datavalue":{"value":{"entity-type":"item","numeric-id":251873,"id":"Q251873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$D39681F4-CD39-4D16-A717-483A8EAE8AE5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e4431a17581abb9eec0e2ce2a0ab6195ec93539e","datavalue":{"value":{"time":"+1995-05-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1842381$C989CAD6-B860-4564-B70C-0DAE122E3FD5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"72b64fc21dab9e68ff951945707f07ff4e530625","datavalue":{"value":"Second order index sets of the discrete families of partial recursive functions (PRF) are studied.   Let \\(\\{\\varphi_e\\}_{e \\in \\omega}\\) be a G\u00f6del numbering of the set of PRF. The \\(e\\)-th computable numbering is defined as follows: \\(\\nu^e : = \\lambda i,x. \\varphi_e (\\langle i,x \\rangle)\\), and let \\(\\nu^e\\) enumerate the family of PRF \\(F^{(e)} : = \\{ \\lambda x. \\nu^e (i,x)\\}_{e \\in \\omega}\\). Denote by \\(I(F)\\) the set \\(\\{e : F^{(e)} = F\\}\\), and denote by \\(R_1\\) the family of total recursive functions.   The authors show:   If \\(A\\) is a non-recursive recursively enumerable set then \\(\\{\\langle i,j \\rangle : W_i \\cap W_j = \\emptyset\\;\\&\\;W_i \\cup W_j = A \\cap W_i\\;\\&\\;W_i\\) is nonrecursive\\} is \\(\\Pi_3\\)-complete.   The family \\(\\{e : F^{(e)} \\subseteq R_1\\) is effectively discrete\\} is \\(\\Sigma_3\\)-complete.   The family \\(\\{e : F^{(e)} \\subseteq R_1\\) is discrete\\}, as well as the family \\(\\{e : F^{(e)} \\subseteq R_1\\) is discrete, but not effectively discrete\\} are both \\(\\Pi_3\\)-complete.   The index set of any family \\(F\\) of total recursive functions which has exactly one (i.e. \\(|L \\{F\\} |= 1)\\) numbering up to numbering equivalence, is \\(\\Pi_4\\)-complete.   The article contains a series of other results closely related to the above-mentioned ones. A number of open problem are listed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842381$558F862B-F3BD-438F-96F0-28718384E173","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842381$BBD5FD0A-7A5E-4208-970E-740623B08015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842381$6E6CC37F-AE44-441B-9910-C81F0A425D67","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6c91c3fbbbe3f83f033f2a59f893d6ad4842401c","datavalue":{"value":"745964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842381$97305AFD-782E-4DBA-9C34-626A005592DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d96457f9bda1a8293cca61a2da98808378991f4f","datavalue":{"value":"computable family","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842381$3CF2D137-8729-4E06-A3D1-3842CE408A10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df98fdba78209319e7a776aa20071eefd171c2ca","datavalue":{"value":"discrete class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842381$1836F61E-B195-41F8-9F8F-21A6F160A9CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8d9fb2b26e7d5559455c0330013b6cebfe35fe8","datavalue":{"value":"semilattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842381$2AC70F30-5074-4B21-B127-AD64FC2D44AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d7d07f38ec58dd62dd712e1d243ae3a3974b348","datavalue":{"value":"index sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842381$8F8C3F20-FF14-472B-8EE6-6B362C99744A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84be346d5b2e3007dfca566cae60632b5f37519c","datavalue":{"value":"partial recursive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842381$C003566F-DBB9-4CE6-BF52-B326A860F4D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"163104295a1d9549194718c0bee6c91d1a6e7f35","datavalue":{"value":"computable numbering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842381$104983EE-73CB-47E8-B737-14C73CBCCCB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35e5fc900b33c9142150c32605a97ad7f76b6319","datavalue":{"value":"total recursive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842381$2C2A553E-718C-418E-A3C5-49106D7EEB52","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fe64c30036b6931dfc08c246a2592bfd800c1f57","datavalue":{"value":{"entity-type":"item","numeric-id":1612485,"id":"Q1612485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$444EBDA5-D021-4B25-BCDA-9F171CB6A2A5","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":"Q1842381$0631DCB2-9EDA-4C33-A16E-9ED27F09F3A0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f9a07423a6f859067df13b8eb1bd5252eb4537d","datavalue":{"value":{"entity-type":"item","numeric-id":4168603,"id":"Q4168603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$72DC6B2C-18D5-4446-8D0B-97BDE0308B2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84fc7188193dcc24094147cdb1f19183b0e45997","datavalue":{"value":{"entity-type":"item","numeric-id":4047540,"id":"Q4047540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$C044E11B-7B3D-44F5-843B-BDA8B0168EAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a050065d8146a2e8b8610a0db470282da2529282","datavalue":{"value":{"entity-type":"item","numeric-id":3328535,"id":"Q3328535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$AFDE8E4F-7DD5-44BE-BCFE-820E3FB703B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c453502c51837b4024533172c1fb7684b119edba","datavalue":{"value":{"entity-type":"item","numeric-id":5341752,"id":"Q5341752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$F96CA803-9486-4DE2-9031-0A9099B1A72A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f2dd8cc71ae75870179a3826f397ccdb62d4f7d","datavalue":{"value":{"entity-type":"item","numeric-id":3797173,"id":"Q3797173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$C7E7FBAE-CDD8-47AD-B3C9-07480EED2566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e246c478e9af4a3c77a62e9d8234b08daa4e5dc5","datavalue":{"value":{"entity-type":"item","numeric-id":5625133,"id":"Q5625133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$4519F402-7881-4E37-8838-6951B3DB53C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bcf7054a2e03acbc27c10ac0867811414686948","datavalue":{"value":{"entity-type":"item","numeric-id":4063428,"id":"Q4063428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$2321BD78-CA72-4C47-8118-F8ADD9E3140F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3533d851352a6467f9155ad5d0d21cd6ace027a5","datavalue":{"value":{"entity-type":"item","numeric-id":4198743,"id":"Q4198743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$E858A01A-CC94-48CF-B849-B36CC8BA72BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2921862f96a0007daaf79a448cfdbf787884a558","datavalue":{"value":{"entity-type":"item","numeric-id":4168913,"id":"Q4168913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$B97BD124-23E1-4E7C-A78C-5410B4AC21C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1edcfc8f162dce621803913f4363a765362e71d8","datavalue":{"value":{"entity-type":"item","numeric-id":3819052,"id":"Q3819052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$E20382E5-79DB-471F-A828-0C13E66B4B4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23d0c78fb5a11a4bf0147b9c16b1bcc5e28367e1","datavalue":{"value":{"entity-type":"item","numeric-id":3220577,"id":"Q3220577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842381$4AC180E3-43FA-4A98-9EDE-7B50A17FC0A8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"217c762d3ea8a8f4d1c29a92a021ccb7f539511e","datavalue":{"value":"https://doi.org/10.1007/bf00739994","type":"string"},"datatype":"url"},"type":"statement","id":"Q1842381$67319F9F-02C6-4E5C-817A-31C34240D033","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9391a6e6f4a2dc54bd7e428a30c140c7c6b6fdf0","datavalue":{"value":"W2011107619","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842381$50CAF9ED-57AA-4025-B3BB-D137109A8C73","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b16efa721a9b849da65dede4671f00a4dc08283d","datavalue":{"value":{"entity-type":"item","numeric-id":3220577,"id":"Q3220577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3739cf0911d138b22f1df337af147d9f21dcb731","datavalue":{"value":{"amount":"+0.854295551776886","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":"Q1842381$AB7154B2-07D5-4B49-A61C-9C004453FBF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7d0ca4eaefdc1ce6c727639738c3403fa5e40e2","datavalue":{"value":{"entity-type":"item","numeric-id":4664631,"id":"Q4664631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"624f7474009ced2c02063e23eea8e0482b25b88b","datavalue":{"value":{"amount":"+0.8367849588394165","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":"Q1842381$89C6DABC-E0F6-4FBA-93D6-190B470963C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4e784884617c59ab8db0a3400b9a30f2d0aaa99","datavalue":{"value":{"entity-type":"item","numeric-id":3325708,"id":"Q3325708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"784aaad8723c5526f311b71712f77a6aa3b16358","datavalue":{"value":{"amount":"+0.789545476436615","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":"Q1842381$D1A83A2A-186D-4FD7-B307-712CF4C420A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1137d995b28eb5f636e3f569aad92762024aa160","datavalue":{"value":{"entity-type":"item","numeric-id":3792672,"id":"Q3792672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"577cfe1d4dd856ea212ad87cd13e1812cca4770b","datavalue":{"value":{"amount":"+0.7887199521064758","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":"Q1842381$4BC24520-6853-44B2-8493-3BEF4E12E113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d6778482679ab652a7bd6b8920d7b6967d76a65","datavalue":{"value":{"entity-type":"item","numeric-id":3832555,"id":"Q3832555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"498ca678d90072fbc764d5f549b618fa5550c145","datavalue":{"value":{"amount":"+0.7794694304466248","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":"Q1842381$3362DABB-0732-4364-8E6F-FB7FE437519F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Discrete families of recursive functions and index sets","badges":[]}}}}}