{"entities":{"Q1787951":{"pageid":1798693,"ns":120,"title":"Item:Q1787951","lastrevid":57556953,"modified":"2026-03-31T09:43:30Z","type":"item","id":"Q1787951","labels":{"en":{"language":"en","value":"Bounded Turing reductions and data processing inequalities for sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6948123"}},"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":"Q1787951$4E6DBC64-37A8-48FF-8AFF-17A643630D10","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1848e8d68459159abba830c9c984f93ed8de7a44","datavalue":{"value":{"text":"Bounded Turing reductions and data processing inequalities for sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1787951$E582C5E9-D24A-4D71-BD6B-2D4E2688A070","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d0868dc20489c9306e94007243aa82cb6d41bbdf","datavalue":{"value":"1408.68083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1787951$EC21ED3D-E5DC-4F1D-85C4-237FA8C7467E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e12bbfd2b7bb3efa149486b6e6d0b012bcbd2287","datavalue":{"value":{"entity-type":"item","numeric-id":1637217,"id":"Q1637217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$4AACF72B-121A-4ECE-A71F-3C61D0BDEA26","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$65583EE0-84C9-4A72-A3D6-F4A47BEFF21E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a90c83859b430a6e74790db9dff6b41d0d6cb3da","datavalue":{"value":{"time":"+2018-10-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1787951$45CA1EDF-DC63-4D94-A3A2-B158A206B708","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e3cfe6050eeca980683f3a251d649f9afbddf7a1","datavalue":{"value":"https://arxiv.org/abs/1608.04764","type":"string"},"datatype":"url"},"type":"statement","id":"Q1787951$29DCA5D6-856D-4AF9-8288-C1E116B1820D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c2a30820860ce78a442184dc1db9652b01a07110","datavalue":{"value":"Define \\(\\operatorname{mdim}(Z:Y)=\\underline{\\lim}_n\\frac{I(Z\\upharpoonright n:Y\\upharpoonright n)}{n\\log|\\Sigma|}\\) and \\(\\operatorname{Mdim}(Z:Y)=\\overline{\\lim}_n\\frac{I(Z\\upharpoonright n:Y\\upharpoonright n)}{n\\log|\\Sigma|}\\), where \\(\\Sigma\\) is a finite list, both \\(Z,Y\\in \\Sigma^{\\infty}\\) and \\(I\\) is the algorithmic mutual information. The major result in the paper is that if \\(Z\\) is computable Lipschitz reductible to \\(X\\) then, for any \\(Y\\), \\(\\operatorname{mdim}(Z:Y)\\leq \\operatorname{mdim}(X:Y)\\) and \\(\\operatorname{Mdim}(Z:Y)\\leq \\operatorname{Mdim}(X:Y)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1787951$1326F63A-D489-4CDC-BB21-B74EF14F48AE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e7788f229b8213d94373bd7e802bf9837fa05217","datavalue":{"value":{"entity-type":"item","numeric-id":409317,"id":"Q409317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$68E90AF2-D729-478B-A9FA-7CC29CB09E74","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1787951$D2C27B9E-8B4C-49E3-BBA3-65B80F5DFC53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1787951$A95D4E8E-AA8C-4C6C-9C1B-FBBCDDAF8239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bfc1b1c272474384546bcd37c9164f9d239a9903","datavalue":{"value":"03D32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1787951$FE47884E-9200-4B33-89EB-FCDAB0314E2B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f1fdc1565478fdb1f7d941cadf053cdc390e9a49","datavalue":{"value":"6948123","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1787951$DA8F4221-AB41-411A-B0C1-24ADEC08935C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1787951$275AAF1F-C5FF-4FB8-B3A3-E36A81E50B34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff8eae3d7a829a54d513f2ea8224a28753ef41ae","datavalue":{"value":"algorithmic mutual information","type":"string"},"datatype":"string"},"type":"statement","id":"Q1787951$8307B0CE-ACED-4E41-BB1B-5FB3E3ED8FC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e143a0043d06f2739394c65d6feba649a8b7131","datavalue":{"value":"computable Lipschitz reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1787951$9FCF32F7-CFEB-4B90-8141-7FDA01E2090A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b10483e5a061224b89398d0e0b66f5c06400a81","datavalue":{"value":"data processing inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q1787951$02BCAD8A-CBA9-4AA7-A727-E5840838645A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e040afae25247b25a31f72bbdcee846bf869a5c5","datavalue":{"value":"effective dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1787951$3E20E5FE-4A4C-4283-87AE-589F614DFEDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22f51dbd083a4570773d5dfb4907a41404745e53","datavalue":{"value":"Turing reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1787951$1519F5F9-BB6A-4202-B435-F4BD85DD2642","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":"Q1787951$424F5B7A-DCA1-47C1-A4CB-08B30237A7E2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dfe239a7bab09fdcbb10ed52281ac1966b7e5e81","datavalue":{"value":"W2962955706","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1787951$46BA351D-D56D-43FB-ABB4-043B43504EAC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9e85923f56df5c51381272688520fbeab489c31","datavalue":{"value":{"entity-type":"item","numeric-id":5614354,"id":"Q5614354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$6E348794-43A3-49DC-B051-BE332A56F680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6578ca65ddbd8195a9557ed50eeb10440e2b0730","datavalue":{"value":{"entity-type":"item","numeric-id":2832303,"id":"Q2832303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$0400F262-9C5D-4FED-AEEF-FF4EBFA98681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763e3905bf47dfe4b400832ecce38198b0d97320","datavalue":{"value":{"entity-type":"item","numeric-id":5490912,"id":"Q5490912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$D93D65DE-6735-4BFE-B9D0-3E18727E1CA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53b276c1c69041d1db3c8cd0204e9efd42d1d63b","datavalue":{"value":{"entity-type":"item","numeric-id":1878680,"id":"Q1878680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$3045946D-BC5C-4E72-AF14-2E3F8F7FA7C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"269cc02ae7c1fc0239e2e2df5074c90539bab0cb","datavalue":{"value":{"entity-type":"item","numeric-id":3764139,"id":"Q3764139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$4CB94596-C2F9-4A31-86E4-E4E312250484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98ff3a58e77184a77c00e51c0b407e32f3683961","datavalue":{"value":{"entity-type":"item","numeric-id":4070739,"id":"Q4070739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$9A6EE6C5-1DBA-4CC9-A542-EF1D629540C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd6a2ee4e62bbabd30a89fa5d4542078151787b4","datavalue":{"value":{"entity-type":"item","numeric-id":3720586,"id":"Q3720586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$2744E6FF-BE2E-418F-AEAF-822100860405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6f51d919dbd006a854ebe67de01a685ef7a6b69","datavalue":{"value":{"entity-type":"item","numeric-id":3422017,"id":"Q3422017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$A3EDFE67-CEC1-4598-9ABF-EF63B38778A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48aaea6b6c48cee130d32321c2defe858b7c176a","datavalue":{"value":{"entity-type":"item","numeric-id":866567,"id":"Q866567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$232437DC-51C0-4064-9477-5A51F1EA0217","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ad1299f57f214c4c9659c7db19e25c6d0461799","datavalue":{"value":{"entity-type":"item","numeric-id":5900062,"id":"Q5900062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$3C07B5AE-22D0-4469-AD34-645EA8DF7CA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e7049d19adb619fb9302e55ada60a2c32233d20","datavalue":{"value":{"entity-type":"item","numeric-id":1887139,"id":"Q1887139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$8A3B98D1-5CE7-4E09-9865-80BE7E760F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d5e433f5e3b754db084d96194e6a1133e70d6c5","datavalue":{"value":{"entity-type":"item","numeric-id":1853096,"id":"Q1853096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$6AF04DDA-982E-4A8B-AE52-393F054A81DE","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":"Q1787951$FA70BD29-EDC7-4F79-9F41-64FA883D4818","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":"Q1787951$28FFA8D6-5E37-4956-B713-5EE7231FAA34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69d06a3b2a41f0bf48bcc26dd54acf42f064fd7b","datavalue":{"value":{"entity-type":"item","numeric-id":1032637,"id":"Q1032637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$057EDC0F-1EA3-41DA-950C-90BD6BF2E1D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66e8a62cd46463c62f9ff883109d60c4695ebc92","datavalue":{"value":{"entity-type":"item","numeric-id":4485693,"id":"Q4485693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1787951$84ED42FB-B394-4019-955B-AFE03FE218A1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3967684a03ff51bbec441dc18133e1c76e3b8d4e","datavalue":{"value":"10.1007/S00224-017-9804-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1787951$B1F41269-8B7E-44CD-AA03-0259A230DBD1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d03dd4089c2941e45a12d098385fa216e75b9694","datavalue":{"value":{"entity-type":"item","numeric-id":2832303,"id":"Q2832303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44d78692f354b657efcd7f6e81d13f171215abf1","datavalue":{"value":{"amount":"+0.7777222394943237","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":"Q1787951$AE96EA2A-9E76-4216-9DC4-B04B2263A651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd0884273113cb12efde93e00ddcef622a3f72b8","datavalue":{"value":{"entity-type":"item","numeric-id":2957876,"id":"Q2957876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"473640b7f3504a13b5c88d0eee16f53496dee871","datavalue":{"value":{"amount":"+0.7777218818664551","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":"Q1787951$700F7DBD-7BDF-4CDD-BC09-48B38A894040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"794479ab84430c9a9f551dc72f88708d742bdfb7","datavalue":{"value":{"entity-type":"item","numeric-id":2219055,"id":"Q2219055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6dea4d118d6f20a40940d302c8e77e854b5cb12a","datavalue":{"value":{"amount":"+0.7214056849479675","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":"Q1787951$6473533E-93F0-47C5-9C24-901337952AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4f5a42152f2afcc240e7d318b51fd8cca36dba6","datavalue":{"value":{"entity-type":"item","numeric-id":733739,"id":"Q733739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae6104926f4fae64c6654df728ebc699abb8c1a9","datavalue":{"value":{"amount":"+0.7154897451400757","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":"Q1787951$4AD6EA6F-9A47-44E8-BAAE-4E67A7599B49","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1787951","badges":[]}}}}}