{"entities":{"Q508835":{"pageid":510602,"ns":120,"title":"Item:Q508835","lastrevid":62367492,"modified":"2026-04-11T05:36:20Z","type":"item","id":"Q508835","labels":{"en":{"language":"en","value":"Randomness for computable measures and initial segment complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6681954"}},"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":"Q508835$0BB68BBF-12D6-4F08-B2E5-3AFE3094A730","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b0d1949c01ebb40e3daa5ae1295c03c3e42ea34f","datavalue":{"value":{"text":"Randomness for computable measures and initial segment complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q508835$DE608172-0570-4D89-BB2B-E8138AD3D601","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e24e21aee8cab3dc0a6fd05a92e4270073c742b","datavalue":{"value":"1404.03039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508835$6BA30D83-C609-4AC6-80A9-97F1D595FD86","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5824ab187e347bb42d9c1a52851520aa57d799e2","datavalue":{"value":{"entity-type":"item","numeric-id":324249,"id":"Q324249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$95F13A20-0142-4BBE-9BB2-DD0950C14AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c748cbf791dcfe25803554f79528cb0276e18e9","datavalue":{"value":{"entity-type":"item","numeric-id":508834,"id":"Q508834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$09D57225-2B58-4449-BC60-65FD76E753FB","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":"Q508835$BF332494-E0CB-44DF-8281-0034DC3DFFC8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0e5e5990e36b519f41dfed9405f14b12a1e45d34","datavalue":{"value":{"time":"+2017-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q508835$085A0E5D-6936-4A60-8142-81A137EAEBAB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3042e6d5bec9f5a941c50187c3dd64afd976214d","datavalue":{"value":"https://arxiv.org/abs/1510.07202","type":"string"},"datatype":"url"},"type":"statement","id":"Q508835$EB7708DC-10E6-48C1-B6EE-BF7BED257757","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3a6454475ed1374ce5ec38e42ff40e5ebdffaf27","datavalue":{"value":"The paper studies the growth rates of the Kolmogorov complexity of initial segments of proper sequences, i.e. sequences that are random with respect to some computable measure on \\(2^{\\omega}\\).  There are four main results: {\\parindent=7mm \\begin{itemize}\\item[(1)] the initial segment complexity of a proper sequence \\(X\\) is bounded from below by a computable function iff \\(X\\) is random with respect to some computable, continuous measure; \\item[(2)] there is a family of complex sequences that are random with respect to a single computable measure such that for every computable, continuous measure \\(\\mu\\), some sequence in this family fails to be random with respect to \\(\\mu\\); \\item[(3)] there are proper sequences with extremely slow-growing initial segment complexity; \\item[(4)] various facts about the Turing degrees of proper sequences.   \\end{itemize}} All results are properly explained and proved in detail.","type":"string"},"datatype":"string"},"type":"statement","id":"Q508835$4C795133-7373-475E-9251-67B68155FC88","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":"Q508835$C6988EB7-53B4-4312-A122-63162961096E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bfc1b1c272474384546bcd37c9164f9d239a9903","datavalue":{"value":"03D32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508835$1D4410F7-A866-4B1C-8DC5-94D818E94BD9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c8d3c59ce10ae5759e55bf2208aa013fcb77c6d","datavalue":{"value":"6681954","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508835$E40E20FD-79BB-4A34-A3A4-41B5EC824809","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a70160cb706d2270c875477b279445d63f76410c","datavalue":{"value":"computable measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q508835$4DA08A2A-FF45-44E5-9690-C72061CD30EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"121b0a8ad973d06529e71ea15269ff6f159a0961","datavalue":{"value":"random sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q508835$A5187516-FA76-4E54-9F64-F242F2635D7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0699e930f98c1f52b4db40f7d6fb62b049345c8","datavalue":{"value":"complex sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q508835$8FB764D9-04AF-4837-B837-55BD68A1E609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98c0b453537fe1cff64f873832af8e703e9b4cd7","datavalue":{"value":"atomic measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q508835$4DDEFCF9-802B-4A59-A8C6-21FC8377A19F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee1a698873058555d3e2e99d2905a4d6f5831f7f","datavalue":{"value":"trivial measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q508835$49F46533-075B-4761-9E1A-98F68FF911E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0e245b7ec939380b71d02eef9ff77649383cfc8","datavalue":{"value":"diminutive measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q508835$8CD263DC-58EA-45A6-9CA0-32BF17B60165","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":"Q508835$587F5D1F-227A-4D1E-A894-6805FBAA888E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"acf3b34a0efe3b9df91b9dd87d6f485f4f96dfce","datavalue":{"value":"W1823933177","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508835$DF8A33DB-DA63-4F5B-935F-D6D9C0E7717C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"22b9fe13c9bb8b68790c8632794822b90aa24dc8","datavalue":{"value":{"entity-type":"item","numeric-id":4922659,"id":"Q4922659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$8CDC559E-D646-4569-9C07-AF79DEA72436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"264be0b3cf818dd85fc5e4d3b7085dc898ae111f","datavalue":{"value":{"entity-type":"item","numeric-id":5389973,"id":"Q5389973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$26A90202-C2AB-4513-99BF-8F56C9EE545A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4c2792479746b74bec095579c18f8db6446b1d2","datavalue":{"value":{"entity-type":"item","numeric-id":1758164,"id":"Q1758164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$4C82948C-E223-4126-B7E9-615BBFC67CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4e9e53feb908d2cd606ef4671ebd9af8d68ff34","datavalue":{"value":{"entity-type":"item","numeric-id":5502821,"id":"Q5502821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$949CED4C-8597-4B39-96E7-31F48ADA2C91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"688e530530b2aa80b106b3a8c0a385dbe89600f0","datavalue":{"value":{"entity-type":"item","numeric-id":4068087,"id":"Q4068087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$D5D41088-64FC-4B43-B12A-1E9C25B2F5EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b95e21ba47a296f497ee74c2f4357bb06e9112f","datavalue":{"value":{"entity-type":"item","numeric-id":3787995,"id":"Q3787995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$6F7A5A7E-1482-43A0-A24B-1172130F2B37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d140eee80ab9faf178a1693e27ebe25436f5930","datavalue":{"value":{"entity-type":"item","numeric-id":3801539,"id":"Q3801539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$CC2286B6-2893-4E5C-A5E4-865C6AB3772B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45131a38ff53f12b9952d52e2962c28740fef2f7","datavalue":{"value":{"entity-type":"item","numeric-id":3161424,"id":"Q3161424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$C54754C2-EF5A-46FE-BF25-C11DF5F36068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bc002ac916dd4751445211db934512aed5c6571","datavalue":{"value":{"entity-type":"item","numeric-id":5407055,"id":"Q5407055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$2EE09707-2324-4679-B0C6-304E73521A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ad3c740aadde1277a24b37d1d9a627173c8cb2d","datavalue":{"value":{"entity-type":"item","numeric-id":386647,"id":"Q386647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$5CDAFD28-D017-46E1-876E-2D2B57C49642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e090dffa36bfcfbac7f260ddab2430c7af753501","datavalue":{"value":{"entity-type":"item","numeric-id":2453070,"id":"Q2453070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$5AE98572-5EFD-44C5-88AB-9D1E43A7DAFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77155bbc34e16cc701b1b9250cc2e5e3db1670ca","datavalue":{"value":{"entity-type":"item","numeric-id":3163891,"id":"Q3163891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$4F4821C8-3C2F-4C2D-BFC8-B519B8BA8427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9403f9584cce4a03226cd3a9499fd4476fcf7f6b","datavalue":{"value":{"entity-type":"item","numeric-id":5668464,"id":"Q5668464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$61A2C8F8-4F9E-4136-841C-41100B7F3D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d9829dc1dcbffe4f37cb05d8ec11d5cdb45d215","datavalue":{"value":{"entity-type":"item","numeric-id":2795307,"id":"Q2795307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$E132C4BC-A8F2-4C19-8BD1-FE6C249C2DBC","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":"Q508835$7B86A000-1F0D-4DB7-ADD2-938B26B2AC86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ef7d3d7b0449f70c767d27ca07a1787366ce824","datavalue":{"value":{"entity-type":"item","numeric-id":610681,"id":"Q610681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$2E5CBF26-D4D9-4596-AED8-14E0DAC613B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bdfc80d0c14e9b01af0753930378e1510541708","datavalue":{"value":{"entity-type":"item","numeric-id":5737996,"id":"Q5737996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$664C30D0-8AC5-45AD-B893-CC05429CF29B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55925e4427f56296e6dd5b43dea359b56ab0d8d8","datavalue":{"value":{"entity-type":"item","numeric-id":3611832,"id":"Q3611832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$596F2C5F-8959-40E6-93D5-2A43073CFEA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c583bad86cc9e3f68e0974b9e07610f9e6615105","datavalue":{"value":{"entity-type":"item","numeric-id":2354580,"id":"Q2354580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$5DA81E91-3BD8-4F1B-AAE0-068CA16B16E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dc1a6f8ff87f7a8ac439004cefc9a3275a9068e","datavalue":{"value":{"entity-type":"item","numeric-id":958494,"id":"Q958494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$716CACE8-6D2A-43F7-9E75-34C9334025A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82eb07c107b60fc71f764021195fbf0a05cec556","datavalue":{"value":{"entity-type":"item","numeric-id":5247029,"id":"Q5247029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$0BDFF7F1-3780-487D-A9DA-44A71B3CDEA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15736a1fabe53e34c9adbd1c3f77269c133e2124","datavalue":{"value":{"entity-type":"item","numeric-id":4040892,"id":"Q4040892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$6F8E9429-DD51-40FF-BD0B-5716E5D6087B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55cfc0ff9590d7beb1ccb038cddeb12787b6740f","datavalue":{"value":{"entity-type":"item","numeric-id":5626617,"id":"Q5626617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508835$1283C92B-4FCB-40DC-96B6-6461AF97B263","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"febf81add07d3bfb7e028a712aebe17034a7f58d","datavalue":{"value":"10.1016/J.APAL.2016.10.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508835$44B761D3-ABBF-406E-8C31-A0E54BBEE57A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e2b64e08297d2c9087308c532e1864f19e25c86","datavalue":{"value":{"entity-type":"item","numeric-id":2062126,"id":"Q2062126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c78bf9b2d4ed933ad1d83c5775783103491693e9","datavalue":{"value":{"amount":"+0.8664615750312805","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":"Q508835$8884697A-C885-44F0-A186-30360D6ADAD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2eab88c0a031929e9face7ed38dc0ca382c39a15","datavalue":{"value":{"entity-type":"item","numeric-id":2921016,"id":"Q2921016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d189360ef6e8c12049da7caab81b5d474e4d2c6","datavalue":{"value":{"amount":"+0.8246908783912659","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":"Q508835$A9B93BBC-F028-4607-9867-64B07406F9B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf501a771f52562a4bb4056e4ca71a99fcb00558","datavalue":{"value":{"entity-type":"item","numeric-id":1887661,"id":"Q1887661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58414ee1cb7d1c2344a699fb1779c8e2e857b3f8","datavalue":{"value":{"amount":"+0.8038167953491211","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":"Q508835$22732A24-89FD-41FD-99F4-ECF9CF10A372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f603a93f90d5741a304c49deb5ca18f6cb14701e","datavalue":{"value":{"entity-type":"item","numeric-id":2475407,"id":"Q2475407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28d0a1b9f1106f55fca2e3b2312885a8cc756bb6","datavalue":{"value":{"amount":"+0.8025822639465332","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":"Q508835$A593156C-956E-4413-A784-EAA283183805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"090515d102daaf6317275dfee3cc23c8e8bac598","datavalue":{"value":{"entity-type":"item","numeric-id":3506714,"id":"Q3506714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57439bd02505f74583799ecb17b587658702060c","datavalue":{"value":{"amount":"+0.8024125695228577","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":"Q508835$6F600C2D-7006-47C2-92A7-556B46769022","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Randomness for computable measures and initial segment complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Randomness_for_computable_measures_and_initial_segment_complexity"}}}}}