{"entities":{"Q5926254":{"pageid":8103056,"ns":120,"title":"Item:Q5926254","lastrevid":93376607,"modified":"2026-06-05T04:18:05Z","type":"item","id":"Q5926254","labels":{"en":{"language":"en","value":"Algorithmic information theory and undecidability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1570837"}},"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":"Q5926254$F7B55B71-1348-4867-804E-8B8FDD1508EE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"058c55576e83ac15847819013e99687de1f0dc9c","datavalue":{"value":{"text":"Algorithmic information theory and undecidability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5926254$61F4DFB8-1EF9-4EC9-BBDD-4A3E1186FDE6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"98134f477ccd324fbf58336bbabbadcea79274cd","datavalue":{"value":"0971.03003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5926254$3ECEDC92-B43A-4DF1-BC8E-82C70180F13D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f0d41570ba6d880612fac0c508d7304df1208bd","datavalue":{"value":"10.1023/A:1005298819345","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5926254$D7E773EF-6A58-460A-AE38-719BD86D03F1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"72b7c301f4b02aff1be5220f52a5fad9d3047f8c","datavalue":{"value":{"entity-type":"item","numeric-id":162815,"id":"Q162815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5926254$756389CE-84CB-4D64-8488-13870BE4BF9D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"28921346d64a666ce2dd47540df2f388e07634f5","datavalue":{"value":{"entity-type":"item","numeric-id":162813,"id":"Q162813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5926254$8E8F509D-03E2-431C-B8F3-DAE629A537C2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9c942329286f61912919b34bd0734f5ee78c9108","datavalue":{"value":{"time":"+2001-10-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5926254$9224A356-0FDB-4BAB-9014-5A7C505ACB2E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"32ff8b69989a1feec12a84b246d08694407b91be","datavalue":{"value":"Chaitin has proven that the halting probability \\(\\Omega=\\sum\\{2^{-|p|}\\mid p\\text{\\;halts}\\}\\) of a universal Turing machine is not computable, and, moreover, that any recursively axiomatizable theory enables us to determine only finitely many digits of \\(\\Omega\\). These interesting results have led to a lot of mathematical-sounding philosophical statements. The author shows that some of these statements, if interpreted literally, are actually false. For example, it is sometimes claimed that the non-computability of \\(\\Omega\\) is stronger than the known result about the undecidability of a halting problem. In reality, these problems are reducible to each other: if we can solve the halting problem, then we can easily compute \\(\\Omega\\) and vice versa. It is also sometimes claimed that the number of digits of \\(\\Omega\\) determined by a theory can be used as a measure of this theory's complexity. The author gives a counterexample: an intuitively simple theory that determines many digits of \\(\\Omega\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5926254$7DD1392F-5C6C-4A87-84BB-6F3CF7F8547D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7a7a7a3dd3a08360856ececf3d8a629dcc430503","datavalue":{"value":{"entity-type":"item","numeric-id":592003,"id":"Q592003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5926254$FB7E5541-866F-41DD-9103-1B85388F6EC9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"48a2830216eefdc24b89ba9895c8f20366f6740d","datavalue":{"value":"03A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5926254$6D81EC2E-3CFA-4E56-A591-BD8978A0AE93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5926254$5627B92C-529F-489F-984D-30FAC39798FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5926254$3ED0829B-4A1C-4EBA-B3A7-95D26CCE32EE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8baf81b02157bd190e3205d6d0fbac7593134284","datavalue":{"value":"1570837","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5926254$8A9F75E1-08AD-40D0-8DA6-CC3BA397768D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9baf9b21255bc7c4f08f1de2606000e9b9a9e18","datavalue":{"value":"algorithmic information theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q5926254$8A3817F0-F963-4771-9DA2-B1C6BA0C7300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a813fd0e4aef1fda5e8e7d4b77b02104337d96e6","datavalue":{"value":"undecidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q5926254$1FA0C5F1-1015-43EF-A733-75D27242B7CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3774d5f7dc2824657f882edcc990b7fd71ab0fb3","datavalue":{"value":"Chaitin's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5926254$74B23391-A496-4D2C-9789-C3CE0E2C92BE","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":"Q5926254$A2EC7C29-7694-4758-B64A-B147824194CD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a06155a855bf65885d25f05f814e376310bd6d00","datavalue":{"value":{"entity-type":"item","numeric-id":2868411,"id":"Q2868411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f25d5103af50802ec0bd79392455acf26d7f772d","datavalue":{"value":{"amount":"+0.93406755","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$0CC581D7-E92C-41F1-BF4D-C3A3454DCDF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35e4a22e41ad10578149abe1fdff48737951f97c","datavalue":{"value":{"entity-type":"item","numeric-id":3802576,"id":"Q3802576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"516e1a00753084ea9f1728ae7ea371a140dfd4ea","datavalue":{"value":{"amount":"+0.9303729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$ABDB0905-E364-4B0E-969A-42CC6CCB0091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53b53c531ff0eed05ee96047668cb6e2391b6a7d","datavalue":{"value":{"entity-type":"item","numeric-id":3197800,"id":"Q3197800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"516e1a00753084ea9f1728ae7ea371a140dfd4ea","datavalue":{"value":{"amount":"+0.9303729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$EC5407C1-DEFE-4B92-9979-6B7B8DA2E836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbaaf1190a16a411cb5927ed1521f26c17584dce","datavalue":{"value":{"entity-type":"item","numeric-id":3299605,"id":"Q3299605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df61c590b35a167a5157f6c7327ecd4c91a02004","datavalue":{"value":{"amount":"+0.92707324","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$85D7CF15-768D-4D9A-BC51-498ADD91E2E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a34341431d593e240bf5abcd0ae0ca2385d676f3","datavalue":{"value":{"entity-type":"item","numeric-id":4520316,"id":"Q4520316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a3fb05394d4b9c294dc79f615cb0b6a9efde615","datavalue":{"value":{"amount":"+0.924935","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$6EF52393-0D97-47BA-9048-2FB0736AC921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e0325f0b689ebf3d2ca80fbabab99b9dcea33e2","datavalue":{"value":{"entity-type":"item","numeric-id":4942046,"id":"Q4942046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a3fb05394d4b9c294dc79f615cb0b6a9efde615","datavalue":{"value":{"amount":"+0.924935","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$C8373FC2-961B-49C9-8EC2-A966017832A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"343671b57a822897067b136cdff538798e02daff","datavalue":{"value":{"entity-type":"item","numeric-id":2709403,"id":"Q2709403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"585fc0a8406120b9f16961b05acf982044eea16a","datavalue":{"value":{"amount":"+0.90786153","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$D18FADE8-3CCF-446F-BBA9-16CCF6868F12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c041422a685b19d5588b040cc2f8a7b42a74d47","datavalue":{"value":{"entity-type":"item","numeric-id":3646249,"id":"Q3646249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ebd8f517da9fa21d8b30d8c5a9a01f67f54d51f","datavalue":{"value":{"amount":"+0.9076599","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$B7B80740-A581-4FA9-9669-5CA2542F0B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abbf1d2f91b6aa89a23a6484aa716ba4e67dde7f","datavalue":{"value":{"entity-type":"item","numeric-id":4215825,"id":"Q4215825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecbffc20640ec91a60d7c13c304421fd00bae28c","datavalue":{"value":{"amount":"+0.89099437","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$EC4ABFC5-9A97-4AB9-8F2D-FF635FFCD21D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7691087b3488cff8fe84ca75e2a654715160f722","datavalue":{"value":{"entity-type":"item","numeric-id":3995518,"id":"Q3995518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"437a8195331f9ef0e10b0c4f1155964a25235fba","datavalue":{"value":{"amount":"+0.89086056","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5926254$1799D449-102D-407F-8414-9AADC7D0F3A6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithmic information theory and undecidability","badges":[]}}}}}