{"entities":{"Q694245":{"pageid":696094,"ns":120,"title":"Item:Q694245","lastrevid":63569682,"modified":"2026-04-11T14:03:22Z","type":"item","id":"Q694245","labels":{"en":{"language":"en","value":"Recognition complexity of theories and their computational expressivity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6115030"}},"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":"Q694245$4ED2E15D-FA27-4A43-8EE1-AEFB2CE2FF93","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"53591cdc6d3d81acb1a8fba7c722b1ba8be3d77f","datavalue":{"value":{"text":"Recognition complexity of theories and their computational expressivity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q694245$F5A5DAB2-0FFB-46D2-AC3B-A185BAFC7CB7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4a123120e6c06f0e575dffc5eaebe6653e2ad190","datavalue":{"value":"1270.03064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q694245$6B7E7667-AE2A-4380-B0A6-FFB2F2290202","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7251e8a05044d792e639ae203139790f0611e466","datavalue":{"value":{"entity-type":"item","numeric-id":694244,"id":"Q694244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q694245$1CDEF314-1AEE-4278-B5CE-BC6859EFA973","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ef3ca3322541db05049091162b21145bd512b130","datavalue":{"value":{"entity-type":"item","numeric-id":251873,"id":"Q251873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q694245$28684A81-AA86-458D-BE9C-7BFA9D2FCC06","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"aaff6a94ac821c6dcde7cb7d6a059bb2e8edd01d","datavalue":{"value":{"time":"+2012-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q694245$62F8DC8F-ABC7-47B7-9D9A-64DBA67142C8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6ab495876671ce6e53823f633079f3586a955110","datavalue":{"value":"The computational complexity of a first-order theory is the difficulty to prove or disprove a formal statement to be true in a given theory. There are decidable theories known to have computational complexities bigger than functions given by towers of exponents. The computational complexity for arbitrary theories of Boolean algebras is discussed. In parallel, a new notion is introduced: computational expressivity. This is the possibility of a theory to simulate long computations, and is a notion that can be applied also for undecidable theories. It is proven that Peano arithmetic has a computational expressivity bigger than Boolean algebras.","type":"string"},"datatype":"string"},"type":"statement","id":"Q694245$FEC3735B-B12A-4F41-BA68-8CC78396DE79","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"be9b7bf9cd273aeaf91ec2e38cce549e5afc8f07","datavalue":{"value":{"entity-type":"item","numeric-id":192024,"id":"Q192024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q694245$D744FFEE-3B84-4E98-9E4F-10858255348B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q694245$3EF1B6AF-E355-445D-98D2-F44811709CC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51c3dc27e13e59ca92a9af5f9c02c332a8b9421a","datavalue":{"value":"03C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q694245$C7DCFA43-1407-4958-95EA-F4AA497790BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q694245$EE5518CA-E3EB-470F-891B-B6DB681D2904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q694245$55B125D1-4F8D-400F-95AA-4A10A1EBCF70","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"64d240b5fc6506887e30c93b181b5803079dd5a2","datavalue":{"value":"6115030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q694245$ED7BF290-4432-4C23-920E-9B6B958435AD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ac82369a09bc861a3472a183669af4c78913c02","datavalue":{"value":"Boolean algebras","type":"string"},"datatype":"string"},"type":"statement","id":"Q694245$A42AFF3B-5D9C-4604-B049-9046D9693E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b16fc07d1c5c9c6736cb24a53f5e95e2897062b","datavalue":{"value":"computational complexity of a theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q694245$5F629FF4-7316-42B4-8C89-D71CF549E047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80b15f4712b366b3d488b86b5c299a56e42802be","datavalue":{"value":"computational expressivity of a theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q694245$4DD6FCC4-2CF2-4DBF-B269-06961691C49E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1288bd4f3d84d526b4303bdd434c009832b834ac","datavalue":{"value":"undecidable theories","type":"string"},"datatype":"string"},"type":"statement","id":"Q694245$0E91A719-A461-4C12-BEE7-8A74A5C1ACF8","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":"Q694245$68648789-DFF2-4AB7-9C2D-C8D634E1911C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8bbfd710d62ccaa36b7702e3884e0abb79bed301","datavalue":{"value":"https://doi.org/10.1007/s10469-012-9178-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q694245$D1F97B44-0C7B-4EE2-AB01-B72AF66C2AF9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0f7f215b223c0e0756556dbd47d335205f505fe4","datavalue":{"value":"W2090578206","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q694245$7D4D1BAA-826D-40AF-AD89-F8121BC174D5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c6d07dd80de4de8f6f1d51aa5d78e790a6fd51","datavalue":{"value":{"entity-type":"item","numeric-id":5812175,"id":"Q5812175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q694245$D02FBF1C-8E1A-497F-B546-6814E239B2A2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e04278eaece5a128068e57fb5ad8a39f7b90cbac","datavalue":{"value":"10.1007/S10469-012-9178-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q694245$B4865EAC-5931-4B58-A698-83F460667FBD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebe1f4c098a436376fcab5fc00fe9ff63724e95f","datavalue":{"value":{"entity-type":"item","numeric-id":5086506,"id":"Q5086506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f32d2002ca87cc3624b2c18decafaf99aaef14e0","datavalue":{"value":{"amount":"+0.7747921943664551","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":"Q694245$E0D4666D-DFC7-4CB5-94E3-32A87CC663B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40cb8eba735a0e2232700be445ac5f50db73f7b4","datavalue":{"value":{"entity-type":"item","numeric-id":5315662,"id":"Q5315662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e97dbfbadd38ebbc5fcdf1422131a6a831846cb1","datavalue":{"value":{"amount":"+0.7490683794021606","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":"Q694245$639D8EF3-9110-4694-9CB6-36A1EB4D99BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6538e3ff52d7f1d06762671ff695bb1e083ea7dd","datavalue":{"value":{"entity-type":"item","numeric-id":4669900,"id":"Q4669900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d7dc10cd0e82c205e1e22806fe1468422a6f312","datavalue":{"value":{"amount":"+0.7303338050842285","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":"Q694245$6E2B0F54-F4DF-4B86-97D6-49BBBACC2D8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d06134fd3eda51e2f0c9f3c7bfcccf3fa4be24e1","datavalue":{"value":{"entity-type":"item","numeric-id":3744158,"id":"Q3744158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3277742608974f2e19100f8483eb312e42b76aa","datavalue":{"value":{"amount":"+0.7164532542228699","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":"Q694245$F53E7ADF-A35D-483C-9A9B-A52833F93301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a83f618132c22057313af25bef67dad35aebd90","datavalue":{"value":{"entity-type":"item","numeric-id":5158662,"id":"Q5158662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d59f415d3cf1d11fcc86b33eceaab8e90456f677","datavalue":{"value":{"amount":"+0.7077876925468445","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":"Q694245$6A871E71-27F6-45C3-85FD-471072F3B804","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recognition complexity of theories and their computational expressivity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Recognition_complexity_of_theories_and_their_computational_expressivity"}}}}}