{"entities":{"Q795039":{"pageid":796887,"ns":120,"title":"Item:Q795039","lastrevid":64394991,"modified":"2026-04-11T19:34:10Z","type":"item","id":"Q795039","labels":{"en":{"language":"en","value":"Reducibilities on real numbers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3861147"}},"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":"Q795039$6B5896D1-6B09-45DC-85AA-5E3BF1CFFBB7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d502ced1dce1128126cb506fba414dc132289564","datavalue":{"value":{"text":"Reducibilities on real numbers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q795039$579197C9-E5E0-489E-9DA8-2EA425918813","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"487541a02c9b117dcb6b1912265793533ab3969d","datavalue":{"value":"0542.03033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795039$0D7F9B8C-E76D-442B-8FF3-EF49E8F772E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c9d7ad1d8d71914d385b53ab3b839796ad4e0ff3","datavalue":{"value":"10.1016/0304-3975(84)90129-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795039$86B471E4-71AE-4D49-84EC-B87776CE2D74","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$877EA674-2DF7-43A1-8E92-2F31AF87221B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q795039$D082E16B-318F-413F-A5C2-29B7DE171DE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bbdb91c793ca6d5449264d9d8f59fa7cb1ab9981","datavalue":{"value":"The structure of recursive real functions is investigated through the notion of reducibility. The main result is that a recursive real function f maps a real number x to a real number y if and only if x is truth-table reducible to y in the sense that there is a truth-table oracle Turing machine M that computes a Cauchy sequence representation of x whenever a Cauchy sequence representation of y is given as an oracle. (An oracle Turing machine M is truth-table if the queries made by M depend only on the input and are independent of the oracle.) Other results include: a monotonic increasing recursive real function f maps x to y iff x is many- one reducible to y; a polynomial-time computable real function f maps x to y iff x is polynomial-time Turing reducible to y; and a monotonic increasing, polynomial-time computable real function f maps x to y iff x is polynomial-time many-one reducible to y. Questions are asked to find a characterization, in terms of the notion of reducibility, of the pairs of real numbers (x,y) for which there exist differential, recursive real functions f mapping x to y.","type":"string"},"datatype":"string"},"type":"statement","id":"Q795039$C13FB9B0-81F5-4650-953A-1327469C7808","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0282342b24b585fa878a09dabeb8eb52c72be5a3","datavalue":{"value":"03F60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795039$7B7FAA61-8767-4463-9761-08A15C73F055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795039$83449597-773E-4F43-8838-58AF81A3BDE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795039$4232E39B-DAE0-446A-BB4E-FAA5EC3443F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795039$CEED7F2F-CCD0-493C-8FF8-7D5C9B6FFB70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795039$5AC56207-BD85-4B1B-95FF-25ACE7A4A4C9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b6cbdc47de551fb98bb552817c5733eaef6dfa4","datavalue":{"value":"3861147","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795039$D8F31330-FA92-415C-89AA-EEDB8E05BD46","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd01e05d89477121d8c5f4bb7d50cce490fb8cec","datavalue":{"value":"recursive real functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q795039$E996365F-727D-4537-9B32-8A12F28650BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0bc1cc50e8d4b517f651118878724606a4faacd","datavalue":{"value":"reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q795039$19FE9402-EE53-4208-8438-47C317DF8B08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03c7db5239930b8e51cb04388a7bc3ddd1a403c4","datavalue":{"value":"truth-table oracle Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q795039$31E2A8AE-E8DF-4E60-A9FB-0FEABC80DE2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c31607e128662b0cb24a7ce474a5bab3f5de8b0","datavalue":{"value":"Cauchy sequence representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q795039$BF0694CC-64D5-4C8A-9339-3E47087FC342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a21313022617278de1c5b2c4dc21312ff98f970","datavalue":{"value":"polynomial-time","type":"string"},"datatype":"string"},"type":"statement","id":"Q795039$8674B5C7-97E7-484D-84EC-2AB467AD3E90","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"13bc86079a0769c5ab1c6f28dc4e52a39f4a573a","datavalue":{"value":{"entity-type":"item","numeric-id":1295380,"id":"Q1295380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$A4E2540E-80B7-4249-A774-6F6BF5DDF74E","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":"Q795039$AAFBB0AA-7512-4A43-A062-52221FCDC650","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"10b7d96ed927aa290f88d509cd2295c744317c55","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90129-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q795039$96185FDD-B136-424C-93C5-F56E4535BD65","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1785cbc606c4fecc00d2eaa689927791260aad0d","datavalue":{"value":"W1994458535","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795039$2CE2D23A-783B-4D40-AFEA-326E3C8C8A52","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$D0D3F525-FC7D-47CD-AC0E-FED5F4E10DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d254e028828e9cc5bbaba559068e1f2b7af650f","datavalue":{"value":{"entity-type":"item","numeric-id":3260573,"id":"Q3260573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$B6A27DBB-ADE7-4671-A50A-8C305A76BDF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$57E3DAEE-1FA5-41BC-BD81-5B2D9DD7CBAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fc27d1146b0da21fb0fbb3f5474781c089c6669","datavalue":{"value":{"entity-type":"item","numeric-id":1161742,"id":"Q1161742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$85EEA826-EDBD-43D7-BD90-43CA9CE26B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"895886e691d85b3f1fd2f8a6af1b9616a7323e79","datavalue":{"value":{"entity-type":"item","numeric-id":3310597,"id":"Q3310597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$2C881192-98C1-44DE-829E-08AA058610DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85e648ab1d102acb9b75bf5c4e0b8b52c6806d0e","datavalue":{"value":{"entity-type":"item","numeric-id":1171056,"id":"Q1171056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$6C4AD4A7-A765-4A3C-9A65-D8D6184E8BED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a36b6eaae6dfc992ccd22b5b3ac0b6ee10fd837","datavalue":{"value":{"entity-type":"item","numeric-id":3244108,"id":"Q3244108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$275EF6E8-DC0C-4ADD-862E-CED76C2002D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"239ce8ec4e3b9429fec71841f77bb740f1b8c95d","datavalue":{"value":{"entity-type":"item","numeric-id":5831321,"id":"Q5831321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$6E5C359F-7EAE-4BCD-B1D5-F198BE4B0A5D","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":"Q795039$459CF255-3D3E-4FC0-8A66-4332CFCB237E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af1701f3c3cd50d70e7e62d3f29b34118b581bfd","datavalue":{"value":{"entity-type":"item","numeric-id":1164623,"id":"Q1164623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$83F16881-8B0F-4F34-8079-4E612A37D853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ecfb341882f732b51d37276b54e079b53dc590a","datavalue":{"value":{"entity-type":"item","numeric-id":5571698,"id":"Q5571698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$2592DD91-218E-4F0D-A6DB-2EADEC965B96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68b9b6e1876a7ef6a8d3ae40b917b0c350a8b4db","datavalue":{"value":{"entity-type":"item","numeric-id":5790901,"id":"Q5790901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795039$9695DF44-7D2C-4A1B-B0D9-9AF4771671E1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb4c14f32ed4320fd4f8d06d09a51d4188195c77","datavalue":{"value":{"entity-type":"item","numeric-id":3789544,"id":"Q3789544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aab8fbd579b35440adc9e46a152e9f2c819d7581","datavalue":{"value":{"amount":"+0.8298340439796448","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":"Q795039$5175935D-332B-4E20-9B97-89CE4299FF91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bd33fac0ef536d1de049342ab7341cf74376909","datavalue":{"value":{"entity-type":"item","numeric-id":4132502,"id":"Q4132502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aef1a8db98ba6a2d0aef1a7c71b6675647ac965a","datavalue":{"value":{"amount":"+0.7758525609970093","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":"Q795039$99ACDBFD-7CA3-4396-98AF-BF1961C0CBBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21f874cd62b020a4ae60236fb3b5a2aa846f00c4","datavalue":{"value":{"entity-type":"item","numeric-id":1274809,"id":"Q1274809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"704c4ed6203be34dc6d0f5bf14fd33c5f06dcbce","datavalue":{"value":{"amount":"+0.7702358365058899","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":"Q795039$A4CA3F4F-B486-4FAB-9C1D-3AF8CBE2BEA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b3dfbdaf48ad859cfd2aa0184105a4901a0ed18","datavalue":{"value":{"entity-type":"item","numeric-id":676314,"id":"Q676314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99901a19348dd68a6087b95b090c1e927f40da0d","datavalue":{"value":{"amount":"+0.7540658712387085","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":"Q795039$EA33532B-9DFE-415D-AB76-D5AA0163187C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a8f620322bd4e8f4b15b0c10239475282b1892b","datavalue":{"value":{"entity-type":"item","numeric-id":3613305,"id":"Q3613305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50bb9da858beafd22639424082a98ae2a2bad0a8","datavalue":{"value":{"amount":"+0.7502719163894653","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":"Q795039$07B20F10-3277-41AC-8678-1B82D909EB4E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reducibilities on real numbers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Reducibilities_on_real_numbers"}}}}}