{"entities":{"Q2290652":{"pageid":2301395,"ns":120,"title":"Item:Q2290652","lastrevid":73651827,"modified":"2026-04-14T16:47:59Z","type":"item","id":"Q2290652","labels":{"en":{"language":"en","value":"Descriptive complexity of computable sequences revisited"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7159826"}},"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":"Q2290652$66B60E32-83C0-410D-BDF4-DBD2AECEC601","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c588dd7780e31a6d1ac37e04bbb6bc80a95510c6","datavalue":{"value":{"text":"Descriptive complexity of computable sequences revisited","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2290652$2C45A5F0-025C-498E-A8AD-77E35DC4C856","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0b6dcbf5ff862a9e17091619fdc1957262d51eb8","datavalue":{"value":"1443.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290652$E32D702F-E0CA-4584-9F70-BCA2A77301C5","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":"Q2290652$608A1D65-3E76-47F4-87D3-94BCF19861D8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"36449951a56e6135e4ec71fa99d76436027843e1","datavalue":{"value":{"time":"+2020-01-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2290652$C91A386E-5B0F-40B2-9CC7-965296102DD0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dbcbe16af15070432e73e15253d810cb11948670","datavalue":{"value":"https://arxiv.org/abs/1902.01279","type":"string"},"datatype":"url"},"type":"statement","id":"Q2290652$F46A31C1-AA68-4086-9014-C38F188A5B3E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b767767d88fd18f0400117d23dd2984bf5a97f4e","datavalue":{"value":"Consider the following two complexities of an infinite computable binary sequence \\(\\alpha\\): \\(C^{0'}(\\alpha)\\) is the minimal length of a program with oracle \\(0'\\) that prints \\(\\alpha\\), and \\(M_{\\infty}(\\alpha)\\) is \\(\\limsup C(\\alpha 1:n|n)\\), where \\(\\alpha 1:n\\) denotes the length-\\(n\\) prefix of \\(\\alpha\\) and C\\((x|y)\\) stands for conditional Kolmogorov complexity. The paper proves the following two results: \\(C^{0'}(\\alpha)\\le M_{\\infty}(\\alpha)+O(1)\\) and \\(M_{\\infty}(\\alpha)\\) is not bounded by any computable function of \\(C^{0'}(\\alpha)\\), even on the domain of computable sequences. They  answer two questions left open in [\\textit{B. Durand} et al., Theor. Comput. Sci. 271, No. 1--2, 47--58 (2002; Zbl 0982.68074)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2290652$8214CFE2-9A0C-45AE-8507-CCA3AE0AA6F2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"21fa9a9223cebca47884c37548205488b3400e7b","datavalue":{"value":{"entity-type":"item","numeric-id":235567,"id":"Q235567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$98989982-0E5F-422E-8563-0FF2B370F881","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290652$8E5F9068-A633-4522-8CAA-F088729C165A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b0f166240d9dc937c89dbc2241079deae14191f","datavalue":{"value":"68Q19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290652$24AB1649-9AED-4D4F-BA51-FB0900118227","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"18d073ca8a7e38d656e5462e5a0075892c47c2d4","datavalue":{"value":"7159826","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290652$52215CFB-7ACC-47E4-8CC5-E5398E4A46FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2290652$B2BE6A7F-9DFC-44B1-A8E1-FED91CF6ACF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b72e6f511e99774417c0be3af314214a76e3f8fd","datavalue":{"value":"limit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2290652$22F0E98B-8DE8-413F-BFB5-BCB168312329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93ff058e5fff510e040db8c3a683e5f26fe5c0b0","datavalue":{"value":"computable sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q2290652$D16B4656-4E47-4270-B076-90EE4A6FBE30","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a878a6ace55a42ed0f1b3e5cefb54bfc6712237b","datavalue":{"value":{"entity-type":"item","numeric-id":1275007,"id":"Q1275007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$4F306F00-E2E0-4919-84A2-BFBCF1A4B29A","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":"Q2290652$6F8B756B-8933-4138-B5D5-FF32F1D9644B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e3726305b956b03cb24004a3ffa9741391115523","datavalue":{"value":"W3000495224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290652$643E64B0-16B3-4201-9980-8210461F5202","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0264bde3db1a3f128adb5c985a83576db98b78bf","datavalue":{"value":"Q126347941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290652$AB7C535F-D1DA-463C-A31E-4D0E87D8CD87","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d88a1af1ba4970e30cf9005409b23a741c859fe","datavalue":{"value":{"entity-type":"item","numeric-id":5579041,"id":"Q5579041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$EFDE2275-8566-44EE-BC49-1A6390E53958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3088737f257da01af63f0db7ea710cbfbc9e18b","datavalue":{"value":{"entity-type":"item","numeric-id":5958281,"id":"Q5958281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$D2848A8B-65F2-40DB-A70D-DF1A73C2C9EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd5becf6b269d2da73d5affe1d576ca0555ebccf","datavalue":{"value":{"entity-type":"item","numeric-id":4337021,"id":"Q4337021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$182201FB-AC97-48B7-943A-73D15CD8B3EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66c928703c81779fae52967e0ccaf0c215e1df40","datavalue":{"value":{"entity-type":"item","numeric-id":5582801,"id":"Q5582801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$52AA4BE3-C510-4B1B-B2F6-462BE164858B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3f4f13509c05ca44b6aa78d129e88e614ae0100","datavalue":{"value":{"entity-type":"item","numeric-id":1307029,"id":"Q1307029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$F0F1045F-DBC6-4C4C-A087-16E9C07D4814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f9c77e3dde77e04dd6614cec16b65b4a68fe197","datavalue":{"value":{"entity-type":"item","numeric-id":4599290,"id":"Q4599290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$809AA1EE-807B-4918-B38E-4978BE7F498E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6c50777e5961226fad33fc5b9491156664a3e6f","datavalue":{"value":{"entity-type":"item","numeric-id":5674994,"id":"Q5674994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$44875290-2CB4-473E-87A8-69374F2EA8AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76e81b94e303e3a7768dfb4c39576c7d108a43e7","datavalue":{"value":{"entity-type":"item","numeric-id":4879210,"id":"Q4879210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$37707A22-7059-424F-8960-07D242F0F52C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58926e5a9eb0323f945caf9cb48728b30dcdbd71","datavalue":{"value":{"entity-type":"item","numeric-id":5958282,"id":"Q5958282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2290652$588A62B0-5B54-459C-93A5-EE5A40746BC8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"630f0279f6609a0a3527ae632d60158804242d8f","datavalue":{"value":"10.1016/J.TCS.2020.01.013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2290652$360AF7C3-8B98-4196-908B-E82335BD225C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84edc890443661b754eb6b484276a76c5c272caf","datavalue":{"value":{"entity-type":"item","numeric-id":5958281,"id":"Q5958281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ed59643a15fdae33761a13cc01d0732dd256e3c","datavalue":{"value":{"amount":"+0.8179633617401123","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":"Q2290652$6F60F110-BF72-44EA-8F73-4A36B1F15DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d737ead8a801b661ea3355d2828aab23a27e8c35","datavalue":{"value":{"entity-type":"item","numeric-id":4251047,"id":"Q4251047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15c1addf15b439e76217f0cf419dce902033d7fc","datavalue":{"value":{"amount":"+0.815833330154419","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":"Q2290652$A80A9E8F-045B-40A9-9885-FEAC0DCAFCB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08ac810d5a72d1952f80615d2935acf304d3cf80","datavalue":{"value":{"entity-type":"item","numeric-id":5898805,"id":"Q5898805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28b8130daa0f95daed1d11c080cafd3e0d320783","datavalue":{"value":{"amount":"+0.7941494584083557","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":"Q2290652$DEAD1053-06F8-487C-B19A-F64B849A9420","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":"fc689354675853801ec2b1f5ab5acf962bea7935","datavalue":{"value":{"amount":"+0.778974711894989","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":"Q2290652$A4F4F35C-20C4-4A28-B9A4-FD1D4657C561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6084908b6772ad61ba18b8c40d5d67f6a1e722e1","datavalue":{"value":{"entity-type":"item","numeric-id":3644713,"id":"Q3644713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a17c5012f4e9da1a228e73be2ba18580bec4a12","datavalue":{"value":{"amount":"+0.7766702175140381","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":"Q2290652$8A4B3846-2C19-4432-8B99-03C57C591EF8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Descriptive complexity of computable sequences revisited","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Descriptive_complexity_of_computable_sequences_revisited"}}}}}