{"entities":{"Q1919986":{"pageid":1930728,"ns":120,"title":"Item:Q1919986","lastrevid":47403541,"modified":"2026-01-01T15:48:18Z","type":"item","id":"Q1919986","labels":{"en":{"language":"en","value":"The intrinsic difficulty of recursive functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 910394"}},"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":"Q1919986$48376CBB-B9E5-4601-8619-D2000A89AD25","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a4f5e28c5ccd64378280aee0eb6b6ac8c0b85213","datavalue":{"value":{"text":"The intrinsic difficulty of recursive functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1919986$77536903-4CAF-4384-8C07-3C032B97CA2C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f0f0199023750fb370c2fada518ca33282ddc17d","datavalue":{"value":"0862.03024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1919986$6C9E3FE8-07D5-4FDB-BE3B-6BE6BAA32133","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bda514590ce26c64ce864163546f69bbc34eb65f","datavalue":{"value":"10.1007/BF00372775","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1919986$FF8FD306-E524-4147-8D1E-81F4A84BF3A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"000eb886d08bdeba44011365aa7a2cbfd96d1fc4","datavalue":{"value":{"entity-type":"item","numeric-id":922526,"id":"Q922526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$5FF91A75-996D-47AD-8417-B7F8E5CDA9B7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e34236ca73b92c6ee0bc17431d03c3537a7f0792","datavalue":{"value":{"entity-type":"item","numeric-id":195358,"id":"Q195358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$8BAEFDAF-B47E-4E51-AFB6-4E50DACB2CD3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5252e1eb2d7b7f01858e2e508ea93d40e7d49d49","datavalue":{"value":{"time":"+1996-07-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1919986$7EDE1F7A-1405-4F01-B0F2-B875AE89D4C2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ac2bed0f67215495fc3cdd911ffaa85ce4f795e6","datavalue":{"value":"The paper attempts to offer a robust definition of the notion of an intrinsic (i.e., independent of the computational model) natural complexity measure. The main concept is obtained by using abstract (Blum) complexity measures and smear monoids, a type of monoid introduced here that allows some slack in the comparison of the complexity of recursive functions. Various mathematical and philosophical arguments stress the merits of the concepts introduced in the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1919986$D2E8F3C5-9D8C-4257-AEAD-788EE590F0F1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1919986$1D0FD941-B9D1-485D-A00F-D2AC539C4DA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1919986$F332ABBE-591B-4425-8E83-55385C876889","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e6411407b3d6708660ba619e0893bfbbefb7529","datavalue":{"value":"910394","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1919986$082012D8-9032-4EE9-9409-91E166952C38","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"556545c10c874235d11dac3140a240f6dd7c969e","datavalue":{"value":"subrecursive hierarchies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1919986$509AA860-DA42-407F-8264-9A4168DB4A22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed4169be77914a771be5a066290133189fd9de20","datavalue":{"value":"intrinsic natural complexity measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1919986$CC825893-07A7-4F84-B9D1-ECCF4952570D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"faab244ff5e9158bb70bf8a7b0bd01b9e9cb9dbb","datavalue":{"value":"complexity of recursive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1919986$CEF59D47-0566-456D-94AC-3A68285D52AF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fc8522c6547fe483c0d1ae4eec1b8d9306e5db1","datavalue":{"value":{"entity-type":"item","numeric-id":290243,"id":"Q290243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$E2D3E800-38C1-4811-B4E8-E79EE621EF68","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":"Q1919986$9F33BC64-2BBF-4E96-BF42-32A6D7F808D7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b420ec73ba6f286df54b90d0d88464e889c2207","datavalue":{"value":{"entity-type":"item","numeric-id":5508280,"id":"Q5508280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$8B99EBA1-69F6-4048-A4BA-18006EC2BC75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"567c454d462a8a001a480f7003ccf7545c952d8c","datavalue":{"value":{"entity-type":"item","numeric-id":1242679,"id":"Q1242679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$FA565478-0CDA-4C3E-AFBE-98C7328D5E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62ba4e673c115c7b9ce2e14b66f90ca97dd5aa21","datavalue":{"value":{"entity-type":"item","numeric-id":4107929,"id":"Q4107929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$AB2092BA-8414-4F1D-951B-EF3F04811E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea45854da7df1d421d45b7aeb6b91b2908960cc1","datavalue":{"value":{"entity-type":"item","numeric-id":5537605,"id":"Q5537605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$5BF9FB42-6766-4DCE-986A-C6DE499773AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a76d91d3dd1208426b047130d39894bfab628f04","datavalue":{"value":{"entity-type":"item","numeric-id":1210716,"id":"Q1210716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$E3F597C8-235C-4AB6-8248-B25B734B5ECD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"627dfc40f56d32772b1586e3c2b075a4cffb4a9e","datavalue":{"value":{"entity-type":"item","numeric-id":3682477,"id":"Q3682477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$3C1D8067-D4F8-4030-95EA-40A400A9AD3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2ad898f482280f7235226b9e02630986c02f7ee","datavalue":{"value":{"entity-type":"item","numeric-id":5737079,"id":"Q5737079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$7015A425-E5C9-4A3D-81D3-AE291B8473C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32edfd02e77f278d344fc02250ea784f191ff433","datavalue":{"value":{"entity-type":"item","numeric-id":3993070,"id":"Q3993070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$69D5D7EB-699F-439F-9DC5-B28D60F144DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd9e5037e4e4cf82e40cd1d813310952fb306a6d","datavalue":{"value":{"entity-type":"item","numeric-id":3291527,"id":"Q3291527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$B5C03726-7B1D-445D-88C1-6FFA300462BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bf84a52a7883f200983e5e7a17fdc1b6cc01ae9","datavalue":{"value":{"entity-type":"item","numeric-id":3124542,"id":"Q3124542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$B073FB8B-FACC-4F72-9B77-25FA95934ECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cee115f650dd9b2c9350f8cdefbe2dab8f0e067","datavalue":{"value":{"entity-type":"item","numeric-id":5824357,"id":"Q5824357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$28913B43-C3D8-41EF-A321-3837D98C14D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"830b7c2e687406b6aec73542f3f86742d97b5bac","datavalue":{"value":{"entity-type":"item","numeric-id":5633652,"id":"Q5633652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$F14D74F2-871B-4402-A533-8AC8445B56B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c568fbb12fc5452c9699a0a3e0159154b2a6454a","datavalue":{"value":{"entity-type":"item","numeric-id":4385525,"id":"Q4385525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$51E12791-E201-4885-A442-3DF3066FDF11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7776da309a3e7db2e30420f463a0570b6d4fce53","datavalue":{"value":{"entity-type":"item","numeric-id":922528,"id":"Q922528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$6D1AB14C-9B43-4F06-A271-11811F3F67CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d4fcb498ec76618d6d4f59a39de4f22e52d70c2","datavalue":{"value":{"entity-type":"item","numeric-id":5612466,"id":"Q5612466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$927710ED-48EA-4DE8-A1E8-5BE36ADA7733","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c8f124158d7067e7483da2752260349cdfd2953","datavalue":{"value":{"entity-type":"item","numeric-id":5659521,"id":"Q5659521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$A9661054-35FF-4A13-9E29-8706422935C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0670b22f2552f07ca7245832dc7b60b11a95ad28","datavalue":{"value":{"entity-type":"item","numeric-id":1232182,"id":"Q1232182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$BEAE4147-5AF8-457D-81BD-03A7A45E75FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2146e12d70096585412fa50f364e0fbe43b7e82d","datavalue":{"value":{"entity-type":"item","numeric-id":3293402,"id":"Q3293402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$F0B00CCC-46A8-4B4D-AA02-1E234CA976F2","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":"Q1919986$0E2D520C-D06B-41A2-A186-FEDA710089FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e06d09a12b20aaf81c10771b83645503c8203f2","datavalue":{"value":{"entity-type":"item","numeric-id":4385526,"id":"Q4385526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$6FF7AC02-83DE-47ED-B8EC-BC7F9DB3FCA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91e1d10e0c77de9812f317b0ff0d8727dd2dd83c","datavalue":{"value":{"entity-type":"item","numeric-id":3781088,"id":"Q3781088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$90950530-A858-4490-8CA7-5DD01327B748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7435100e3d690d36fad3b0237a6b1d48437e9556","datavalue":{"value":{"entity-type":"item","numeric-id":4385524,"id":"Q4385524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$879FA2A5-6208-4DBB-95B4-13D4CF0BBD1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b34a73ab06c7f65600429ed3aef7e1b92fa4fc4","datavalue":{"value":{"entity-type":"item","numeric-id":3853608,"id":"Q3853608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1919986$7E0E4EFD-AECE-4E3D-B3E8-C399BBCDC636","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d60a3cfe6f6118f55f97e393481ef79c7109075","datavalue":{"value":{"entity-type":"item","numeric-id":3219105,"id":"Q3219105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7f589e60406501b899acadb3615ac0851e1563c","datavalue":{"value":{"amount":"+0.7469840049743652","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":"Q1919986$6EDE2DBA-5163-4EEB-8AA8-32D702ED409C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44334fb683f0fd15533f6171f1dabf57a6921eb4","datavalue":{"value":{"entity-type":"item","numeric-id":1398370,"id":"Q1398370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ada75f08a99c04bf0d1dc76eb3c88f60adb40dd1","datavalue":{"value":{"amount":"+0.7264651656150818","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":"Q1919986$092A090F-1E97-41AC-B77A-E5608B3AB50B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa258d6f9910be8b237855634737e0f22d53267b","datavalue":{"value":{"entity-type":"item","numeric-id":1106201,"id":"Q1106201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"887a91ad473aa41d8219158e24d931dec65215fe","datavalue":{"value":{"amount":"+0.7203199863433838","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":"Q1919986$31909079-3B48-4CD4-94D5-8C42F20E03DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"326e947d2ca32595990655b761e629b39a219bb1","datavalue":{"value":{"entity-type":"item","numeric-id":922528,"id":"Q922528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5600acf1914bb08494ddd3ab15dd905180d02498","datavalue":{"value":{"amount":"+0.7192736268043518","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":"Q1919986$FF8008F6-30EA-4C33-94DD-03C26AC259D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77dd7abeb8659ae11ddcecea39d2c0fc5819c72a","datavalue":{"value":{"entity-type":"item","numeric-id":4437079,"id":"Q4437079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dcb109d1c93fbef923c5319bb6c2be101b7c4fc","datavalue":{"value":{"amount":"+0.7143886685371399","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":"Q1919986$A0F26AFA-AEBE-4A38-A2B0-0A6F6E5AA087","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1919986","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1919986"}}}}}