{"entities":{"Q1334675":{"pageid":1345414,"ns":120,"title":"Item:Q1334675","lastrevid":67587063,"modified":"2026-04-12T18:56:16Z","type":"item","id":"Q1334675","labels":{"en":{"language":"en","value":"On recursive bounds for the exceptional values in speed-up"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 643683"}},"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":"Q1334675$C578D5B1-3FE1-403C-8CCC-2ACEC6015D95","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a129a9a63a3c5be6f961f7910b6aca050ac85e3e","datavalue":{"value":{"text":"On recursive bounds for the exceptional values in speed-up","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1334675$1B5C737C-35BF-4031-88B4-0961D1157405","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0944eff767d6390abcb2741e391131cde6a39a15","datavalue":{"value":"0807.03026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334675$1768F7B7-0393-452A-9711-47EC31FD87C6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9ef25cbd3002a01a6239ad7b247f8c5e1364863d","datavalue":{"value":"10.1016/0304-3975(94)00050-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334675$4E1906E3-19D3-44FC-8C82-4BA76CD3A091","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":"Q1334675$5BA266EF-9AF0-4035-A7C3-B1C372151D61","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c8ed3bb629960f79b097c1d049886bd39178543","datavalue":{"value":{"time":"+1994-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1334675$8FA6BE99-D3C6-4FD4-9F81-E3BAAE480EBA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e4e259a46da21c29b8c9cd98e6f5ce3991dab539","datavalue":{"value":"We state Blum's original speed-up theorem in extremely concrete terms. Let \\(f\\) be any recursive function. We think of \\(f\\) as being slow-growing (e.g., \\(f(n) = \\log n\\)). There exists a recursive set \\(A\\) such that the following occurs. For all \\(i\\) such that \\(M_ i\\) (Turing machine \\(i\\)) accepts \\(A\\) in \\(\\text{DTIME}(T(n))\\), there exists \\(j\\) such that \\(M_ j\\) accepts \\(A\\) in \\(\\text{DTIME}(f(T(n)))\\) steps on all but a finite number of values (called `exceptional values'). The original proof was nonconstructive in that you cannot obtain \\(j\\) from \\(i\\).   The paper under review asks the following two questions: (1) Given \\(i\\), can you effectively find a bound on the exceptional values? (2) Given \\(j\\), can you effectively find a bound on the exceptional values? This paper proves that for question (1) the answer is NO, but for question (2) the answer is YES. The proof of the NO answer uses the double recursion theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334675$88CE2262-16F2-4903-A3F4-ABDFBC07547B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"59c02125cd654c6fe0740c84a942b089a0294819","datavalue":{"value":{"entity-type":"item","numeric-id":811135,"id":"Q811135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$353C0B7E-2910-4524-964B-4C2ADD038621","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334675$8BF243BC-168A-4F04-873C-5B15F5E64F5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334675$ACCE092A-2EE7-485A-A7FC-1EAE7CDD5AF2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"462eb70985490dc23430e65372b8b17f2d81d4fc","datavalue":{"value":"643683","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334675$7964BA7A-2C3F-4CB2-9186-10EE854727E3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ad52beac8db45145b0cff53e99cdfbb60274683","datavalue":{"value":"Blum speed-up","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334675$FD0DC1D8-779D-4728-9437-28EDBA406E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"053105e7bd74d2dd60a23347246e5d38bf188313","datavalue":{"value":"exceptional values","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334675$2AA1CA6E-634B-4FA1-B12D-FE458CD446BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02ae711a30fd2979e3c5365f928e80b53c3a6e75","datavalue":{"value":"double recursion theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334675$5293D6CE-6183-4A98-9307-EF87A9E7E0E9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d0c467571618a5b33c7823110a5579080019d1c6","datavalue":{"value":"Q57001783","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334675$F99C9AF8-2EC3-487A-9412-ACDB9307D874","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6d6cdfad59386b4fdf0e04c7f9812453107706ac","datavalue":{"value":{"entity-type":"item","numeric-id":185794,"id":"Q185794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$52F14169-139A-4B5C-A34B-3D6BF7D39208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96e9fd827f0c306dc6fc60932527fbe8faec3e49","datavalue":{"value":{"entity-type":"item","numeric-id":235567,"id":"Q235567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$588515AF-6628-4E93-80E5-1D34A9AFB99E","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":"Q1334675$F4A2C433-1F5F-450C-8BAC-0120E421FF19","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9f94312a2ca379b10547e6ef2afbd6327fc7bab1","datavalue":{"value":"https://doi.org/10.1016/0304-3975(94)00050-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1334675$33086AFC-42E2-4BE0-B06C-30A19486F0F5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8e4011ec024fafce25270aa014cf4a1ca69c8246","datavalue":{"value":"W2039986919","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334675$3BEAE7BF-B972-4F97-BAE7-9C6FD817488A","rank":"normal"}],"P223":[{"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":"Q1334675$1AD87BC3-A02D-412C-B61C-FE5E422746AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0596e5c599613b80ada37fb1d40e1b8f50bde8d","datavalue":{"value":{"entity-type":"item","numeric-id":5549809,"id":"Q5549809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$FE10A0EC-5491-4EE4-AE2C-A94B774CD88F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99e7ae46485da06f7a508caf53fc752e95dfe3e5","datavalue":{"value":{"entity-type":"item","numeric-id":4285775,"id":"Q4285775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$FBE2BDC1-8BEF-4755-BD2F-EF60C6343961","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":"Q1334675$8BFFE792-FC0C-48DD-90E4-18B524EB38D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ee430b6ebc6d56e583a1169b7708e2a99b391ab","datavalue":{"value":{"entity-type":"item","numeric-id":4295226,"id":"Q4295226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$A3517485-47A7-4AEC-B222-330AAD3D2DC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c49d7de355c3c3d17fbfa1abc7d357a21d11c76","datavalue":{"value":{"entity-type":"item","numeric-id":909459,"id":"Q909459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$6E9D7910-A6DB-4445-9675-B7EBECB86080","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":"Q1334675$D8C20EFE-DE9E-4F59-A20D-EBDAD37B2CFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81549b50647122edca7fd749350fb0dc0673b39e","datavalue":{"value":{"entity-type":"item","numeric-id":5674405,"id":"Q5674405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$F8D546D4-DA07-421B-A11A-03A0694B3AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$1AF7415E-84EA-49A3-B493-7E2B56E38E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"917800fa52c098f2382f946c4094dc39e957bfbe","datavalue":{"value":{"entity-type":"item","numeric-id":4153600,"id":"Q4153600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$128F17BB-9D49-4304-945F-0FF6839AEF50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0d208916c9d05809760edbf98e4029e5f6fb13b","datavalue":{"value":{"entity-type":"item","numeric-id":5663367,"id":"Q5663367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$F1C1BF65-9BC5-4913-B17E-F74608F0ED8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5457b0cb72c8b95f4127d6fa8247d739851c4b50","datavalue":{"value":{"entity-type":"item","numeric-id":3680279,"id":"Q3680279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$B00A9C35-B91D-4BD1-BEC7-011E0A0D49D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea4a81e2c875eb41d86cce4eb84a351de6296d9a","datavalue":{"value":{"entity-type":"item","numeric-id":5680997,"id":"Q5680997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$4BEBA857-37B9-40D8-80E5-303083ADCDC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0f6a00e0b60381dbfb9628e8e47193a3d534bd9","datavalue":{"value":{"entity-type":"item","numeric-id":4053629,"id":"Q4053629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$DBB363A9-ADDF-460E-B59D-389B56DD7BC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"303aff42bba7cac20f2c31129d466b8c70f1731e","datavalue":{"value":{"entity-type":"item","numeric-id":3276696,"id":"Q3276696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$3AF8BE3A-1C4C-499E-A823-0AAE5A06A72D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31dd01e5f21b1bdf706c36866dc27edf4dbff6f1","datavalue":{"value":{"entity-type":"item","numeric-id":4088272,"id":"Q4088272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$ABD4F47B-C481-4A00-A526-6117445D8EB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98a3423516ab48dd654a7f59b83e72ebef08bdf4","datavalue":{"value":{"entity-type":"item","numeric-id":4094391,"id":"Q4094391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334675$1BB7CFE3-CD2E-4D8B-8C0F-75A992E41045","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"d461bc636f58f09caec12b4cb45763b7ef91776e","datavalue":{"value":"journals/tcs/BridgesC94","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334675$6CF2A396-32FF-4E9B-9E2B-561458B63585","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f6342a7d5a36cc875219e3740efc6a429a387f8","datavalue":{"value":{"entity-type":"item","numeric-id":5402504,"id":"Q5402504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a5e368c02c98bc84c9c94340b213b03129c659e","datavalue":{"value":{"amount":"+0.748278796672821","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":"Q1334675$05D9EFF0-7C85-4424-B272-6B1805FA4BF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a910dd446000f6dea0dab55502cc635e5e44542","datavalue":{"value":{"entity-type":"item","numeric-id":3751574,"id":"Q3751574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35bcf24fa4a6dd10b62c87e01acff34828391a8e","datavalue":{"value":{"amount":"+0.7472513318061829","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":"Q1334675$D7CB4A44-2233-402B-8E24-252306C37E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3abd29f5de738e3dd4c66ed78de4d5799c0c31f","datavalue":{"value":{"entity-type":"item","numeric-id":5402508,"id":"Q5402508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27ef1d8aaee1dc0f597ba85a1f7b8ecff210bbe5","datavalue":{"value":{"amount":"+0.7413343191146851","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":"Q1334675$664FE09F-24AA-4001-BF40-331A7AFEF55C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf3cba77b0b8556b4f4fd1b9dd4e2e437733af5d","datavalue":{"value":{"entity-type":"item","numeric-id":3630193,"id":"Q3630193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8d8eb8da3d2daf0713945e58eac89d59f8d3070","datavalue":{"value":{"amount":"+0.7404640913009644","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":"Q1334675$F37729B6-3ACA-42EA-AACD-1DC560B234A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7875bb14ac6c3e88982e22a33dc971dade4534d2","datavalue":{"value":{"entity-type":"item","numeric-id":688718,"id":"Q688718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3220b5375e8d7633c38df1b89f6e4a65908af0ee","datavalue":{"value":{"amount":"+0.7398277521133423","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":"Q1334675$C42E35E9-20FE-44F4-BE96-267CF353F5E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On recursive bounds for the exceptional values in speed-up","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_recursive_bounds_for_the_exceptional_values_in_speed-up"}}}}}