{"entities":{"Q2382278":{"pageid":2393021,"ns":120,"title":"Item:Q2382278","lastrevid":78614879,"modified":"2026-05-06T12:01:21Z","type":"item","id":"Q2382278","labels":{"en":{"language":"en","value":"On the Turing degrees of minimal index sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5196804"}},"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":"Q2382278$4993EED9-1CBA-4C57-872D-AFFBD996AC3A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a57fe4fd840128aa96b18e36fef02905bb4f864b","datavalue":{"value":{"text":"On the Turing degrees of minimal index sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2382278$7B9216AE-AF62-4AC5-9728-D192E61BD0AF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"70cefe512947a068a8a3c2fa2b68200d35d80509","datavalue":{"value":"1128.03033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382278$81AD802F-BB93-4AEE-8F13-5F10331A7BEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d33e72c15639eebdd6008918802154b667d8c006","datavalue":{"value":{"entity-type":"item","numeric-id":342725,"id":"Q342725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$B1CC55CD-E5DD-4448-BE87-AC5456736994","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$5FE97F32-35A0-42B5-8410-12D8F07F4B74","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0f3bb612485fd64be80be5677ab1cdc0f4709762","datavalue":{"value":{"time":"+2007-09-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2382278$0B1BADE3-87B6-45FF-84C0-F7330545848F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a5e2988aae96593ebd6f00314942c8b7f3a1e33a","datavalue":{"value":"The author considers the problem MIN*, studied by \\textit{M. Schaefer} in [Arch. Math. Logic 37, No. 8, 521--548 (1998; Zbl 0910.03037)]. He gives a generalization of Schaefer's MIN* shortest program and obtains analogous results by characterizing the Turing degrees for four sets of indices, called minimal index sets. Some results about complexity of the set of shortest descriptions are proved and it is shown that it will be difficult to prove the optimality of the previous results. As a particular case, the author shows that there exists a Kolmogorov numbering for which all the minimal index sets simultaneously achieve maximum possible truth-table or Turing degree. At the end some open questions are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382278$83E644ED-A188-493B-AA41-EB5F7819A7B9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"86e7d9065663fa3ffd8f6c70df93df9f4742e385","datavalue":{"value":"03D28","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382278$BEF06128-1F51-4920-A0E4-DD96F448641F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382278$CD6100B4-EF6C-45ED-BAEB-B8D622884155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382278$E2516F56-209D-4AA5-AAAF-8469F3655F0D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1c5bc3acad1159bff2f0830d245dca9c89d79eb8","datavalue":{"value":"5196804","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382278$C030B78E-4053-4B17-B541-224C8EC9DBAF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91fe4280e2e06a0a064865358db087007d3f302b","datavalue":{"value":"Turing degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382278$A0FCF8D3-1FEC-432C-8E8A-EA73BCFA7230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"666551f41133f21dc92d7b76fa3b8aa3101dc61a","datavalue":{"value":"minimal indices","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382278$E8CF2E4D-69BF-4070-B3A7-6F2B6A2F19AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1d2050e747d98412f12f0e7386f511f9364dbcf","datavalue":{"value":"shortest programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382278$DBE59749-D296-48B8-B89A-4D987C837CAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7c84c51e332877a7a006ded1eb53647f8d859c2","datavalue":{"value":"shortest descriptions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382278$0F7C499B-EC80-43AD-9215-1C5BD2751909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b466e92d77be04ee0e52ee8197f2ba6f8943df4","datavalue":{"value":"Kolmogorov numberings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382278$57DC8267-F5BD-469A-95EE-A9BA3A405790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2949fc281bed09d1a282780bb1ba94789c84966","datavalue":{"value":"truth-table degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382278$E30935B7-5087-4A26-B031-E19B01F4383F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"10ce3a5d9313b648d3b16631524f630b08f534db","datavalue":{"value":{"entity-type":"item","numeric-id":587297,"id":"Q587297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$41E4E5B4-CA9C-4FA0-8ABD-81752D918850","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":"Q2382278$3CDF8625-0A7F-419C-A97C-FD601009B8DD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fbbec9d5f14dcc60d513aa603796317860386ddd","datavalue":{"value":"https://doi.org/10.1016/j.apal.2007.07.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q2382278$534CF51A-3FEC-4B5D-837D-B70BA91730DC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a018441c9b7e8c1190c44f5f7e83a20152ef3de","datavalue":{"value":"W2113988846","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382278$117D9FFD-6074-49CF-9E98-A745C037CC6E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ce84a7b1c7ab92c6703d5ab4009b1868b2001c8","datavalue":{"value":{"entity-type":"item","numeric-id":5829026,"id":"Q5829026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$392127AC-A237-45D5-99FC-89271915F0DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a48e39f9aca59c78d19c6f70a4c683ffb544e3e7","datavalue":{"value":{"entity-type":"item","numeric-id":4238422,"id":"Q4238422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$B497A834-C1BD-4C0B-8325-9EB3D6EBB731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dae26af80a5696fa8c01db658b71f7ff80167bbe","datavalue":{"value":{"entity-type":"item","numeric-id":3248015,"id":"Q3248015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$E1EFFF12-C352-4869-AD5F-0101EFAD8B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfe38fe19cf97f81a630bbeb3a96a5b65d421db0","datavalue":{"value":{"entity-type":"item","numeric-id":3489987,"id":"Q3489987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$E3261951-639C-4F49-8302-C12B074C9385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dcb46b0aaefeb6e9984794a82270c9b10ed1a25","datavalue":{"value":{"entity-type":"item","numeric-id":4161311,"id":"Q4161311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$5BBCD370-E0D5-4877-820F-662AB6E8E97D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2133328bdb68fe8478a6a1735372029a4a4c3396","datavalue":{"value":{"entity-type":"item","numeric-id":4593915,"id":"Q4593915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$4D5C6174-410B-4094-B731-D23CD4CF121B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cc858e204245d49f72b64a4aeb12c67d57861e0","datavalue":{"value":{"entity-type":"item","numeric-id":4055150,"id":"Q4055150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$C6B5CFE3-B941-4F03-A8C2-E7FDE7C6EEB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"850ec53483c087fa2e8890fc924e571da7793c17","datavalue":{"value":{"entity-type":"item","numeric-id":3232283,"id":"Q3232283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$7BB12D81-2490-4F11-91A9-772AE787BBA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dec668d27b17236d20c4d0c731e94df29b5e12e","datavalue":{"value":{"entity-type":"item","numeric-id":5519129,"id":"Q5519129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$5B4800B5-A932-42DE-92F4-814B1CE35E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcd3a853401c0a338f3c6d9ef11af48e72f68c40","datavalue":{"value":{"entity-type":"item","numeric-id":5729295,"id":"Q5729295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$58F8C6B8-BC36-4C4D-91A1-E87F148151AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c39b32a5c80667d0b220938d4be50fcdc7cae40","datavalue":{"value":{"entity-type":"item","numeric-id":1127831,"id":"Q1127831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$D41A03BA-23F8-4F05-BD4B-1A826765339E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e47a2b9d13405189c02127187179ae3a2b67315a","datavalue":{"value":{"entity-type":"item","numeric-id":2864221,"id":"Q2864221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$FB354FBA-1D4A-4FE6-B89C-E36C98A37050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0ab7072cc10946be1b3fa64322fa7549b21d8d2","datavalue":{"value":{"entity-type":"item","numeric-id":5631091,"id":"Q5631091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$3287763C-BA6C-4988-A8E0-DFD3C5784E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba17c610b66d156b76e62a37325c965ffedff718","datavalue":{"value":{"entity-type":"item","numeric-id":4184825,"id":"Q4184825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$CE7BF2D9-2CC0-470B-8538-EBCFDED12414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f06c8bfeb472d70e261bcd9f6972a2b537924104","datavalue":{"value":{"entity-type":"item","numeric-id":929628,"id":"Q929628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$0F1821CF-17A2-4EE2-B738-D52E63F09ABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a9e2bef4fdbd225bb9be5b208982286cb515e8a","datavalue":{"value":{"entity-type":"item","numeric-id":2382278,"id":"Q2382278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$CF56DEFE-B2CB-4BE7-921C-6C1409712099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce38d666d23d39801802e7eff3732bc0ae06ca41","datavalue":{"value":{"entity-type":"item","numeric-id":2395863,"id":"Q2395863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$1B3E00E5-156A-4435-922F-806E57E67E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff431a272f467dfb02b804bd42fce10899a446b9","datavalue":{"value":{"entity-type":"item","numeric-id":5519130,"id":"Q5519130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382278$AE364ED6-437A-4190-8130-F0B2B641FA52","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a130fc8edabac078e13c340cfb9d5d911675975f","datavalue":{"value":"10.1016/J.APAL.2007.07.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382278$5F8CC71E-C3E1-4437-997B-E9E85333C023","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dd69164ebb4575a1f18c613a6ac63c3f6ef3b53","datavalue":{"value":{"entity-type":"item","numeric-id":1127831,"id":"Q1127831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03bfbe63943af75d8b840941688a3cb4a9cad28f","datavalue":{"value":{"amount":"+0.8501189947128296","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":"Q2382278$AC69F6E3-B328-4BE7-B129-ABC52436AE83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"363030eaab0200e9d7889fde389b8314b386eeff","datavalue":{"value":{"entity-type":"item","numeric-id":5402506,"id":"Q5402506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03bfbe63943af75d8b840941688a3cb4a9cad28f","datavalue":{"value":{"amount":"+0.8501189947128296","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":"Q2382278$EE89BF03-EC5B-45BF-8381-2AE7083D80DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"945819f356220a67268c9f83323f3ddbe5113745","datavalue":{"value":{"entity-type":"item","numeric-id":716308,"id":"Q716308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cd299f479340412e9888d8617e979c4d774589f","datavalue":{"value":{"amount":"+0.8161393404006958","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":"Q2382278$3EC0BB65-4908-447A-8E50-87468EE59EBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f19b8355aa37c2a191f70f9d82131a401ec7ac1","datavalue":{"value":{"entity-type":"item","numeric-id":3576059,"id":"Q3576059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90cc7e5d45a5de6621909cf87cf493a800cba866","datavalue":{"value":{"amount":"+0.8125981688499451","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":"Q2382278$7EB9CD9A-4489-4ACC-8C77-3E1F646A0B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2635569f9e9f5638f58be671925adadfa4231ac6","datavalue":{"value":{"entity-type":"item","numeric-id":5388731,"id":"Q5388731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d979946ea25b14f0de3fc4ce80caf069dd525a6","datavalue":{"value":{"amount":"+0.8051733374595642","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":"Q2382278$53DC7E29-3DE2-4515-BD9F-36F5795A8405","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the Turing degrees of minimal index sets","badges":[]}}}}}