{"entities":{"Q760795":{"pageid":762644,"ns":120,"title":"Item:Q760795","lastrevid":64170549,"modified":"2026-04-11T18:06:54Z","type":"item","id":"Q760795","labels":{"en":{"language":"en","value":"On the power of probabilistic strategies in inductive inference"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3885302"}},"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":"Q760795$7843B843-89E4-44EC-A097-CE08993A9DFF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5fb6b572639a3af95680050195db824c49afd39a","datavalue":{"value":{"text":"On the power of probabilistic strategies in inductive inference","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q760795$8BA615EE-5123-4115-B28A-C4419A06E25E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7e84b4f4965e58eefc62477b5120ce15f541e0ec","datavalue":{"value":"0555.68014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$5945B09D-CBC8-4EE6-8E05-2424F1E257FD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e18574e7d1abd3fc0a0f2a9ec0f6e23065ff6cc5","datavalue":{"value":"10.1016/0304-3975(83)90067-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$84D23F01-3C8B-4CD1-B728-CA7FE269B979","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d07e083a9c84ce44546596ac735a33577e30388d","datavalue":{"value":{"entity-type":"item","numeric-id":202184,"id":"Q202184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$2CD2FB57-1F40-4C4C-ADDF-0034F1D0B95E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec3b29744c0c4a5e008618686519803ba2d0b097","datavalue":{"value":{"entity-type":"item","numeric-id":760794,"id":"Q760794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$44FB592A-0CC5-4388-8FB7-7E71D2F0B476","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a1b024062144599d578c4d162aad677602df6a1","datavalue":{"value":{"entity-type":"item","numeric-id":656589,"id":"Q656589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$4CB98163-2D55-46EF-935A-A1B380BC6A21","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$1A649D9E-1462-4FCC-9566-349B74B8620A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q760795$86C479C2-D953-4652-A8F5-3C0DF76AADF2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1964d783eb2a7a9ce03d0676d6f5aec94a22aa3a","datavalue":{"value":"The paper deals with probabilistic algorithms for inductive inference of programs solely from input/output examples. Let \\(LIM_ n\\) denote the family of all classes of recursive functions U limit identifiable with n changes of hypotheses in the following sense: there exists a deterministic Turing machine with input tape and output tape such that for every function \\(f\\in U\\), starting the computation when exactly all the values f(0), f(1), f(2),... are written on the input tape in natural order, the machine never stops and on the output tape it writes a nonempty, finite sequence of at most \\(n+1\\) numbers, the last one of which being an f-program, i.e. an index of f in an acceptable G\u00f6del numbering of partial recursive functions. For p \\((1/2\\leq p<1)\\) let \\(p\\)-LIM\\({}_ n\\) denote the family of all classes U such that, with probability p, U is limit identifiable (by some probabilistic Turing machine) with n changes of hypotheses. It is proved that \\(\\cup_{n\\in N}1/2-LIM_ n=\\cup_{n\\in N}LIM_ n\\). However if the number of changes of hypotheses is a priori bounded then probabilistic identification strategies are more powerful than deterministic ones. Namely, it is shown that: (1) for every \\(n\\geq 2\\) there is a class U such that U is in \\((1- \\epsilon)-LIM_ n\\) for every \\(\\epsilon >0\\), but \\(U\\not\\in LIM_ n\\); (2) for every \\(n\\geq 0\\) and every p \\((1/2\\leq p<1)\\), \\(LIM_{\\det (n,p)}\\subseteq p-LIM_ n\\), where \\(\\det (n,p)=\\max \\{k:\\) \\(k\\leq ((n+1)/(p+\\epsilon))-1\\) for some \\(\\epsilon >0\\}\\); (3) for every \\(n\\geq 0\\), \\(LIM_{2n}\\subset 1/2-LIM_ n\\subset LIM_{8n+2}\\). This last result shows both the strength and the weakness of probabilistic strategies with a priori bounded number of changes of hypotheses.","type":"string"},"datatype":"string"},"type":"statement","id":"Q760795$08D3364A-CC78-4BDE-805A-C1641C1FCF9C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$B249EF36-2DE9-4DA2-9310-C62CBF8A3E54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$44D3E982-AACC-4C8F-B77E-AA5F14B6146D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$2A5F0D41-E871-4064-BF91-1FD945D44AA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$EFCD7862-52C8-4406-B9EA-B363E49FA0C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$CD524485-A0CB-4357-8A2A-2BC2190A9929","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$A7E328CC-B5D7-4D64-8179-0CC20113A67E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9c1c22ef731595d89a3bd0db369ff4004b87a73c","datavalue":{"value":"3885302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$7CB22EA8-34FF-477E-81BE-D0989CBF14B3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e569e07a49c82ee4107766a600078715f7a3daaf","datavalue":{"value":"probabilistic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q760795$1CF174AD-3CAD-40AC-A178-DB5D4508C8D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a691dc3bd790653ada610f0b5e2d3f2d74cae79","datavalue":{"value":"inductive inference of programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q760795$0292468E-75E9-4056-9603-FFE972189207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c92f25b9ea895f2b57606a79389bb66216727043","datavalue":{"value":"recursive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q760795$333A74CF-E35D-4D8F-BEC3-C2F3453C613A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c0f1970b625c924543cd42f8a54c7ce976554","datavalue":{"value":"Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q760795$0B339BE1-7126-4AAC-B636-E24E00963D3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"707dcc1a7600891da7461acc4d535cd59d57a157","datavalue":{"value":"G\u00f6del numbering","type":"string"},"datatype":"string"},"type":"statement","id":"Q760795$C8FCB209-EAD2-4D87-8347-11ECB7FCEFAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f133fc265514877878253343553c131ebef1646c","datavalue":{"value":"probabilistic strategies","type":"string"},"datatype":"string"},"type":"statement","id":"Q760795$6B3730A5-DE2D-4495-AEA7-05F8FD0958C3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1833d190eb6492ca84e0c93a6ff12de5694705d3","datavalue":{"value":{"entity-type":"item","numeric-id":1109753,"id":"Q1109753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$6626E519-ABE6-4918-B6C3-D03859892613","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":"Q760795$5EB98E52-59A9-43FA-B244-3BD9EBE4B3D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ce838160eb8dd1737c62c9ebc366845ca382e431","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90067-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q760795$ED581938-B8A5-4865-B3FF-B77CBCFBF6FE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c6bbf6243ebb28520c68bdae69a74c39878702b3","datavalue":{"value":"W1997380360","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760795$84204B46-50B9-414A-99CE-5977A420FA6B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"711725225ec21381bb1ef1fdb1862e7a2a73fa75","datavalue":{"value":{"entity-type":"item","numeric-id":4155651,"id":"Q4155651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$6860DF37-D279-4028-AA4C-28822A19F193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f13c2ce0315ebf9725fc3f7a233cd4e3815200f","datavalue":{"value":{"entity-type":"item","numeric-id":5685065,"id":"Q5685065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$7C20A0A3-5751-49BB-A467-B6CAC127E8A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b38edea1b938fbdd8a9623a6542490f846108277","datavalue":{"value":{"entity-type":"item","numeric-id":4154852,"id":"Q4154852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$54E8C355-AF62-4ED2-91AF-5F8093B24426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81d2482321d454b114c72263bdb29cdb26bb1a17","datavalue":{"value":{"entity-type":"item","numeric-id":3855155,"id":"Q3855155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$C3E0BB8D-E75E-4770-BF5C-971FAACDCCEF","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":"Q760795$F57B312B-6ADA-46EA-9D37-DB523AD30627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ad62835a55923ec861c71dbb6edfd53ffd42573","datavalue":{"value":{"entity-type":"item","numeric-id":5601468,"id":"Q5601468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$FD0983DD-2E51-4E21-94AE-7CFD9F96838C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86e90797d616829572eb9b729f6a2beb7258f3e2","datavalue":{"value":{"entity-type":"item","numeric-id":3894947,"id":"Q3894947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$AFB097B3-3437-4FCE-8D28-99441BB6AC26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14c4d6301eb58a5a9bed75a57ba9f7937df7acdf","datavalue":{"value":{"entity-type":"item","numeric-id":4145699,"id":"Q4145699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$0C4265A9-D16A-4DFB-B53F-DDA63B013BAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08d4599b8026fa405fdd44d73039d12333ab04de","datavalue":{"value":{"entity-type":"item","numeric-id":1151889,"id":"Q1151889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$C5E5C75F-69A0-4AEB-957A-AA131B13457C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9378de5a0a0174e80abfaa815d7ab9b5a8ee4fac","datavalue":{"value":{"entity-type":"item","numeric-id":4108307,"id":"Q4108307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$EC6DA34E-6914-404D-8C64-72D9F4441494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$F3C269DA-139D-4B39-8009-A50DA48ABE10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffeb253077017578b514058dad4897c327ae3f54","datavalue":{"value":{"entity-type":"item","numeric-id":3960153,"id":"Q3960153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$6BDC310A-7CF9-4267-B62C-639CD4BE9BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6acc84c64e46319842ef17497b61b468633b165c","datavalue":{"value":{"entity-type":"item","numeric-id":5622168,"id":"Q5622168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$AE4E8AF3-0C4B-47DE-A705-3DC01D15D418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d57bf5e529a31f826b0dba240ff131f2cd9bd1a","datavalue":{"value":{"entity-type":"item","numeric-id":4170707,"id":"Q4170707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760795$E0685004-4367-475F-81C5-FE3AD3ADC319","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a5819e9eb5119f898078cad600da7745f9ee23f","datavalue":{"value":{"entity-type":"item","numeric-id":3832071,"id":"Q3832071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5239004a4e9c5d5eb2b38f34325e0c8942ba85bf","datavalue":{"value":{"amount":"+0.8722828030586243","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":"Q760795$92B78C3A-8BC0-4C94-81EE-891C9665F6D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9abcf8adf9bd5bfad79dfc92302871be3d4804d","datavalue":{"value":{"entity-type":"item","numeric-id":5687656,"id":"Q5687656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c904835139ae4f662fa3b31bce03607ce014d717","datavalue":{"value":{"amount":"+0.8527798652648926","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":"Q760795$79881DF8-A651-477B-9AB9-A39215907E1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db59370f011aab3ce1c31f36d0030e0651e5cb93","datavalue":{"value":{"entity-type":"item","numeric-id":5056125,"id":"Q5056125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c904835139ae4f662fa3b31bce03607ce014d717","datavalue":{"value":{"amount":"+0.8527798652648926","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":"Q760795$376CCFFD-8F57-4B60-9D76-17487268337F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e03995f1ec468e0e476b7ba04612a66366796e76","datavalue":{"value":{"entity-type":"item","numeric-id":3824298,"id":"Q3824298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76b1ad169146174e16038906b935382cb1d25a1b","datavalue":{"value":{"amount":"+0.8452660441398621","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":"Q760795$854B61C7-AED6-4BFA-8DCB-8045AA02586D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d35d0787c428660ffa29ee46a2478a43d2ef3fae","datavalue":{"value":{"entity-type":"item","numeric-id":4240334,"id":"Q4240334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b25dc4b4670abe30389985bdc29242f97ef3ef58","datavalue":{"value":{"amount":"+0.8299220204353333","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":"Q760795$57BFB5AB-D25F-42EA-A780-38E028EA16EA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the power of probabilistic strategies in inductive inference","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_power_of_probabilistic_strategies_in_inductive_inference"}}}}}