{"entities":{"Q802546":{"pageid":804394,"ns":120,"title":"Item:Q802546","lastrevid":64488549,"modified":"2026-04-11T20:13:12Z","type":"item","id":"Q802546","labels":{"en":{"language":"en","value":"Probabilistic Turing machines and recursively enumerable Dedekind cuts"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3891342"}},"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":"Q802546$FE248D4C-CC95-4F8F-BEBD-C59F2D884550","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b12bb25e54a960e27b6873b747d7b42c5fae8322","datavalue":{"value":{"text":"Probabilistic Turing machines and recursively enumerable Dedekind cuts","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q802546$A372DCCC-F66B-49FA-AD2B-EA3A92F962F7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e6208c5a38d10a2fe4b034873cbb85ce2f24f37c","datavalue":{"value":"0559.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802546$1E9DE281-6FA4-41E2-9EFC-B41C9A46A2AE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"697c242491dc2097491777a89869c08d73491c42","datavalue":{"value":"10.1016/0020-0190(84)90078-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802546$11E0FAC8-8B6F-4801-9D98-B1B6C486BCF9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$A22D8198-F146-4CB4-8C6C-2BC299F3FE31","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":"Q802546$7A2F1F41-3523-4F3D-AFF8-7F4E0A40ABA3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c157a5af1c582ff2cfe35fd0f71fa102c3b22dc","datavalue":{"value":"The question ''For which real numbers \\(r\\in [0,1]\\) are all languages accepted by each probabilistic Turing machine (PTM) with probability greater than r always recursively enumerable?'' is investigated, and it is given as answer that r has this property iff the upper Dedekind cut of r is r.e. It is also shown that in the case that the lower Dedekind cut of r is r.e., a language L is accepted by some PTM with probability greater than or equal to r iff \\(L\\in \\Pi^ 0_ 2.\\)    Reviewer's remark: These results were obtained under an implicit understanding that the relation \\(''pr(w,k)>q''\\) is recursive, where pr(w,k) is the probability that a given PTM accepts the input w in at most k steps. But this is not sure if the transition probabilities in a PTM are usual real numbers, even when they are computable real numbers! Of course, the obtained results are certainly true if all transition probabilities in the considered PTMs are required to be rational.","type":"string"},"datatype":"string"},"type":"statement","id":"Q802546$8DFF2E11-77DD-4289-8D0A-F6417720499B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802546$FA2A9261-BA7A-468D-9B3D-89077E42F8BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0282342b24b585fa878a09dabeb8eb52c72be5a3","datavalue":{"value":"03F60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802546$DC516034-00AB-42A1-9E64-683E5B938F19","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"19cad6709a345bdaa28799eedaf97e997cef86ae","datavalue":{"value":"3891342","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802546$E939BB26-E8BE-4043-9EA3-E8AB52A4BA90","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63f0d189c006f1876f9ee89a3c0c7b626f07dc54","datavalue":{"value":"recursive real number","type":"string"},"datatype":"string"},"type":"statement","id":"Q802546$A0A4CFBC-0554-4CD4-9481-770CE2245692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d3317fee091a183b95c82d29dc1e995b7455f26","datavalue":{"value":"arithmetical hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q802546$706BE6CA-D181-4430-8514-2C20453D8F1A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"97f37dc983198355fd189ee54af7058c412c3222","datavalue":{"value":{"entity-type":"item","numeric-id":287139,"id":"Q287139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$4A9E032F-8FD5-4523-BAAA-80E1F81C8184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a81ee3d22f4d6472094917e6f4d497a318f69849","datavalue":{"value":{"entity-type":"item","numeric-id":529039,"id":"Q529039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$9C53205F-A8C8-4DAB-8387-4EAD4545F968","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":"Q802546$8B256539-E4A8-4BF9-B25B-B822C8079C0D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1fc9fef12e224e1574d6da0484c9c2caaf55cf88","datavalue":{"value":"https://doi.org/10.1016/0020-0190(84)90078-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q802546$1A1D89FB-51BA-46E7-8D16-2E19372464C1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b7c506e1195eb0fe821a4c6fa51b61281ad61e2a","datavalue":{"value":"W2168971817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802546$B1AF5E92-9453-4E3F-BD11-07AD5DF43695","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6ad89a01696e5095512d78d1f8332ce1eed1341","datavalue":{"value":{"entity-type":"item","numeric-id":4145647,"id":"Q4145647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$2125D3EB-9EF1-4626-AA35-1D2021BF8F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$2B505462-F4B0-4287-9495-BDE7EDBC4FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca5466532ce748319c6945ee654a01a4898c1d9d","datavalue":{"value":{"entity-type":"item","numeric-id":1143792,"id":"Q1143792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$5280E35B-6FBE-458F-A680-28562BA65862","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":"Q802546$F9FD6CA6-4F85-4016-A3E3-6ADC060CB792","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":"Q802546$456EA994-2FD2-48CB-A416-9CCD36CC4DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"289e5708eb0cbb9a9dbb4d75ee2db63a898b6188","datavalue":{"value":{"entity-type":"item","numeric-id":5181669,"id":"Q5181669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$1824675B-7398-45D4-98FA-E9988185F530","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3e32cd00e50889ce6fdac19be614a9be1a54020","datavalue":{"value":{"entity-type":"item","numeric-id":4164569,"id":"Q4164569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$859811A3-A541-46BC-A1CE-50B5EE33D274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13ecf59f9a4d1b7659a1683859f2c9d3ac797ae0","datavalue":{"value":{"entity-type":"item","numeric-id":5572344,"id":"Q5572344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$5D9D7731-AEDA-40C4-9E56-59D85166C08C","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":"Q802546$18F79EFD-7152-43A5-9B23-C545DD93F4A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd2f45038ab8e4e4836ac8e04a5fbfcb672edc4f","datavalue":{"value":{"entity-type":"item","numeric-id":5588675,"id":"Q5588675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$D17A5DE4-D8FB-439F-A8FF-65F39D43DD86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78d76393a70d405a8059be716f4f3c29dd963950","datavalue":{"value":{"entity-type":"item","numeric-id":5658085,"id":"Q5658085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$DF968CAA-EDBF-4494-B9AC-E5DDBB62E390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27d911397582ceb5a1b462d5874cecc9ed198a01","datavalue":{"value":{"entity-type":"item","numeric-id":5579493,"id":"Q5579493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$557F3B21-1687-4152-9D2D-DA354A02BA73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45693627939fec63d2836fa11bb5f307d8dbed5a","datavalue":{"value":{"entity-type":"item","numeric-id":3899517,"id":"Q3899517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$5C17774E-0D20-406D-AAF1-DAC606EEF187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d4b76e9cc7bd13c5d7b25255c39eb916e75586d","datavalue":{"value":{"entity-type":"item","numeric-id":1158756,"id":"Q1158756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$E46675C2-50B4-4565-A9CF-64347552EBE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2901f59e974bb3153a3f3ebe52d0c1cb384280a4","datavalue":{"value":{"entity-type":"item","numeric-id":2531924,"id":"Q2531924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$2302DB21-778B-4CED-B2B0-9F585C7ADC6F","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":"Q802546$8B741AB6-FD81-43D0-930C-5F1AEE722E86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8706e2a690d5177037c83ceb7a917b1bfcfb5f56","datavalue":{"value":{"entity-type":"item","numeric-id":4113883,"id":"Q4113883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$74DEF7D3-09A6-4C6F-8384-EF6F96EC4A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66e3bbc9b3d1eddc34941d8d96b4bfa7380dd3fd","datavalue":{"value":{"entity-type":"item","numeric-id":1838301,"id":"Q1838301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802546$8ABCB667-EE0D-42F6-A8E7-37B34B3F3A83","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6af494247adc214751480e5863d24bf933f750f","datavalue":{"value":{"entity-type":"item","numeric-id":4727435,"id":"Q4727435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0790c7e0447b9931d52f4ec296d2cc39e26ea367","datavalue":{"value":{"amount":"+0.7409638166427612","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":"Q802546$F93EB619-B256-44A6-86C4-C32E7A379622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28970a95deb1f05c8c19ee25e02ea593ce49c9bc","datavalue":{"value":{"entity-type":"item","numeric-id":5941066,"id":"Q5941066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a384404d31bda9afc9ad4e451735068b31fe7c09","datavalue":{"value":{"amount":"+0.6963168382644653","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":"Q802546$186B2F37-EEC8-4D87-BF08-8CB20594AF9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"506bfa664e7e5d118f318e517255bf07e8adc3d1","datavalue":{"value":{"entity-type":"item","numeric-id":5958328,"id":"Q5958328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab0de300684efb01c7deb78f63b43cf5b2d1d846","datavalue":{"value":{"amount":"+0.6951019763946533","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":"Q802546$C1E12732-4833-4C21-8A2F-DA8265E94D62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbfcf14298af65192b49d474a8c0f4dc74af3019","datavalue":{"value":{"entity-type":"item","numeric-id":2372684,"id":"Q2372684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39b8cd7d034aa1d7c0fae52c1216b75bc4b1e0a9","datavalue":{"value":{"amount":"+0.6945797801017761","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":"Q802546$8B987972-843D-4B3A-BB90-CDDC80B9EF1E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Probabilistic Turing machines and recursively enumerable Dedekind cuts","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Probabilistic_Turing_machines_and_recursively_enumerable_Dedekind_cuts"}}}}}