{"entities":{"Q1382180":{"pageid":1392920,"ns":120,"title":"Item:Q1382180","lastrevid":67452156,"modified":"2026-04-12T17:58:41Z","type":"item","id":"Q1382180","labels":{"en":{"language":"en","value":"Randnomness, computability, and algebraic specifications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1133081"}},"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":"Q1382180$81E4AD3C-F7A9-4FE9-AA9C-7E2C85BAAF6F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8a12adb0ae66f9ea78685cdd612ad9c86c6fd7d5","datavalue":{"value":{"text":"Randnomness, computability, and algebraic specifications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1382180$D6278F43-D1B4-4E04-A01D-A8FA824A05A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9166585d012a514a49ee159edabc5413124e749f","datavalue":{"value":"0915.03037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382180$65A3C52D-4D92-4BE4-B713-F54F1ECAD37A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3237b61e8289a54fb07fa1669ff311acbef762a9","datavalue":{"value":"10.1016/S0168-0072(97)00040-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382180$CD438899-9C62-4ADD-8B1C-9C31C0509BD2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"908230505203eccb837b53bb6b9c33b396a9a16d","datavalue":{"value":{"entity-type":"item","numeric-id":188054,"id":"Q188054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$E48C3C93-4A70-4CA3-9E01-E4D46EC34BBE","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":"Q1382180$9166EF3D-F3A3-49BA-9100-91E1438C3889","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"05bf036feabda231d03853d981bfd44c2d1c51d8","datavalue":{"value":{"time":"+1999-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1382180$2E816ADB-51F4-4346-B9B5-419F4B16401D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0eff20c575b007d5eba64cd20d55e51f6b815288","datavalue":{"value":"The author describes an interesting relation between Kolmogorov complexity and abstract algebra. Traditionally, Kolmogorov complexity is defined and analyzed for integers or for words in an alphabet; however, it can also be described for an arbitrary algebra (crudely speaking, for an arbitrary abstract data type). Namely, if we fix a finite set of constants and a finite set of function symbols of different arity, we can define terms in a standard manner. Each term \\(t\\) is a word, so we can define its Kolmogorov complexity \\(K(t)\\). If an integer-valued function \\(f(t)\\) is defined on the set of all terms, then we can say that a term is \\(f\\)-random if \\(K(t)\\geq f(t)\\). In particular, if we take the height \\(h(t)\\) of a term \\(t\\) as \\(f(t)\\), we can talk about random terms.    We can define the algebra of random terms if we factorize the set of all terms over the equivalence relation in which all non-random terms are equivalent to each other. It turns out that every original function operation is consistent with this equivalence and therefore, this factor-set is indeed an algebra. This algebra is finitely generated (constants serve as generators), and its equality relation is recursively enumerable (although, of course, not decidable). The author proves that this algebra cannot be algebraically specified (i.e., specified by equalities); thus, this algebra is a first natural example of a finitely generated recursively enumerable algebra which cannot be algebraically specified.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382180$40F947DF-8398-48A1-A73E-0E8B7F8E1EE4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382180$1C667C1B-8D93-4C0D-8661-4DE4C8AE7660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382180$DD5C482D-1AE5-49F5-BD7A-B469EAF252D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed4ac44229a63771ae4ded31038fe93f434bffb7","datavalue":{"value":"03C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382180$46973ECA-1733-4284-AF91-87B75F6B986F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"758b4d196a1f97708f26591fee42c00739e26cc0","datavalue":{"value":"03D80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382180$495C7C52-1C29-46E8-A91C-338D70D3682E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382180$A222ECAE-B27F-4AEC-960D-959E37BAC6E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8664222dd6b23ad8d79788ff6ab0d3086d6dc2c0","datavalue":{"value":"1133081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382180$4E5D1850-C229-4108-9666-7E68F576933A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382180$085EDF42-9F0F-416C-A21D-04382F272876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"496fb62b5fbbae0889439900bccaa24ccd7b815b","datavalue":{"value":"randomness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382180$7DEF8F67-19D2-4D81-A152-6B325941DA68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1daee68cedeeadccdf496f924561e3065e4444","datavalue":{"value":"abstract data types","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382180$8D64526F-96EE-45B6-A798-CAD5C29A0B6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2288de0b75809db77e94e2018ee2f7fca368bd99","datavalue":{"value":"finitely generated algebras","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382180$6DF9E9A5-0511-4D2D-9A84-6AA5E12C1CF2","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":"Q1382180$BF71070D-624F-4042-8433-FC144CD91BBF","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":"Q1382180$8EE0412A-F6E9-4D9E-80BB-919502A62660","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"290d3013f4832df97a35c79891587387962ec5e5","datavalue":{"value":{"entity-type":"item","numeric-id":4692466,"id":"Q4692466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$CD8BDF00-3B35-436C-B210-FB2F4C42DC98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6162a47706be814c34042fd00c7c48b95d112be","datavalue":{"value":{"entity-type":"item","numeric-id":3662597,"id":"Q3662597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$5DB815E8-F0ED-4BD9-B0B2-4631188B8CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3744dcf2bce65710124275d29816dcca108a9baf","datavalue":{"value":{"entity-type":"item","numeric-id":1098613,"id":"Q1098613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$9353F214-5875-430B-AFCC-F52904A703FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"062e6b60e77749216114d35202f5ce2c55314034","datavalue":{"value":{"entity-type":"item","numeric-id":3659115,"id":"Q3659115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$B21E0ED4-5484-4153-8232-613714C0BD4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dccf93e6966c15ca8a099e60ee160344ed7f4199","datavalue":{"value":{"entity-type":"item","numeric-id":4326782,"id":"Q4326782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$308160AD-69E3-4381-AC91-949987E9FD44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66a85821eef78ce7e6e0e2ef04d73eeb429828ca","datavalue":{"value":{"entity-type":"item","numeric-id":4520316,"id":"Q4520316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$67A481E0-B0C1-4F7F-BB54-671DCC3B3EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c505b8a452afb6bd145c8e41db160f3580ea1e38","datavalue":{"value":{"entity-type":"item","numeric-id":3995518,"id":"Q3995518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$D4FD7171-2C0A-4CC1-9EF6-B266FCF12BB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f512d3044d87913829cd345dbca09d60481c7fa","datavalue":{"value":{"entity-type":"item","numeric-id":5572358,"id":"Q5572358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$6A8DB8BE-522A-4BF5-A5E7-6058CAE3393B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb8630373e4717a0493dbfa41a7a15321a5bfbd","datavalue":{"value":{"entity-type":"item","numeric-id":3809790,"id":"Q3809790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$B71D052D-19B3-4851-9DEB-7322C3C1C5DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a90b1233f82de64a80906a2f3929c074bde3e85","datavalue":{"value":{"entity-type":"item","numeric-id":4850551,"id":"Q4850551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$21E66687-9ACA-47EF-AB83-0097AC5D29F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"360cc14210d040c82c3fb8482fcff4a97cc7c9bc","datavalue":{"value":{"entity-type":"item","numeric-id":5537373,"id":"Q5537373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$245F2349-EC6D-4C7C-B28F-26308B1A9907","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":"Q1382180$89A141C6-4F7C-4002-A23C-69D519867297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11766368fd4fe71da654ab384c0eb007a14e97da","datavalue":{"value":{"entity-type":"item","numeric-id":4023359,"id":"Q4023359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$9BC16BF7-10DD-479F-8BFE-3020A1832356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71af303659d8129448c6091b17d4d2ae1f52d70a","datavalue":{"value":{"entity-type":"item","numeric-id":1095646,"id":"Q1095646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382180$F613FC56-FDE2-4E00-88F9-A07125CF910E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9a8bfe8fc0f75306e9091a2623b00d5bc6a17672","datavalue":{"value":"https://doi.org/10.1016/s0168-0072(97)00040-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1382180$E7F922F3-1AA6-40DE-B78D-89F5EEEFED1E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f5346c249dedad2bdba0a29c9b9946c1962e0ccd","datavalue":{"value":"W1968784437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382180$850237C2-40A2-40EF-AA50-07375480B692","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7a5aa0af4c5a32ac20183e5a2294da62cc7f58a","datavalue":{"value":{"entity-type":"item","numeric-id":2973065,"id":"Q2973065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"add461fc3f8b961446213c545eed49591daa29f8","datavalue":{"value":{"amount":"+0.8004866242408752","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":"Q1382180$F53D5B84-F185-4EEF-98A8-38DF83B4CE20","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":"e6cf4e684d1d92a32ec5270360217dbf0785ec99","datavalue":{"value":{"amount":"+0.7530733942985535","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":"Q1382180$A4FDCBBC-E315-4C43-9BBB-B03B52F266E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a6faba0c33d0d012b458107ff038de207e2041f","datavalue":{"value":{"entity-type":"item","numeric-id":4227881,"id":"Q4227881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16441b05d2f89ff9142331fef3d03be3bd9f8f2a","datavalue":{"value":{"amount":"+0.7399567365646362","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":"Q1382180$D341172A-7A1D-4405-945E-9FE8827888F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9eeb4a98be1c9d33a447dc755639fbb61bbade6c","datavalue":{"value":{"entity-type":"item","numeric-id":4023358,"id":"Q4023358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ffecb6573f405fea63a40d140647ed029492cdb","datavalue":{"value":{"amount":"+0.7330405116081238","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":"Q1382180$5FC18E00-20D6-4169-BA30-1C8C907A9036","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Randnomness, computability, and algebraic specifications","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Randnomness,_computability,_and_algebraic_specifications"}}}}}