{"entities":{"Q2372684":{"pageid":2383427,"ns":120,"title":"Item:Q2372684","lastrevid":57882513,"modified":"2026-04-02T22:42:47Z","type":"item","id":"Q2372684","labels":{"en":{"language":"en","value":"The halting problem is decidable on a set of asymptotic probability one"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5176391"}},"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":"Q2372684$E3324A11-D548-493D-91E1-2993198DC737","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c28d9ff15be64ed094a065af3216bfc80953124","datavalue":{"value":{"text":"The halting problem is decidable on a set of asymptotic probability one","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2372684$9E53D300-CC43-412F-B2A7-585D680F81A1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1ab83ac1d3db38fb31c5ed210e046c45da766297","datavalue":{"value":"1137.03024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$1D6427C4-9A3D-4333-ABB0-2B914B0AAECD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c237c0edc686c7e9971d10e201d8b8137b9a6f25","datavalue":{"value":{"entity-type":"item","numeric-id":167886,"id":"Q167886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2372684$0B6E6288-DB02-4C6B-92C0-9044C85F4E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b1843ff51384642f69cbb6cac945664c66fbeb9","datavalue":{"value":{"entity-type":"item","numeric-id":639687,"id":"Q639687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2372684$FDB4F355-5A26-49AC-B1BD-36825297610E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2372684$97E39FFE-71E2-45CE-B534-A8C59FE9E184","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"37c844feca35da75671978fc1effde9476fb11ba","datavalue":{"value":{"time":"+2007-08-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2372684$D5A9D025-E313-4608-85E5-8C1AC4E34F1A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6e91e006caf973116fec46fb4b09ee4c30dafe55","datavalue":{"value":"https://arxiv.org/abs/math/0504351","type":"string"},"datatype":"url"},"type":"statement","id":"Q2372684$24218F14-7BFB-4881-AA9B-35457A84B9F4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b446d95725113c0e5c2d1071b5ab2c39adb91069","datavalue":{"value":"Let \\(P_{n}\\) be the set of all \\(n\\)-state Turing programs. The authors  define the asymptotic density (or asymptotic probability) of a set \\(B\\)  of Turing machines as follows: \\(\\mu (B) = \\lim_{n\\to\\infty}{{| B\\cap  P_{n}| }\\over {| P_{n}| }}\\) provided that the limit exists. Let \\(H\\)  (``halting problem'') denote the set of programs that eventually reach  the (\\textit{halt}) state from any initially empty tape.    The Main Theorem proved by the authors states that there exists a set  \\(B\\) of Turing machine programs such that: {\\parindent=6mm  \\begin{itemize}\\item[(1)]\\(B\\) has asymptotic probability one, \\item[(2)]\\(B\\) is polynomial time decidable, and  \\item[(3)]the halting problem \\(H\\cap B\\) is polynomial time decidable.  \\end{itemize}}  The authors first prove this theorem for a standard model of TM  computation that assumes semi-infinite tape and single halt state.  Moreover, if the machine head attempts to move over the end cell then  the head falls off the tape and all computation ceases. Later the  result is extended to several other (but not all) models. For all the  models the following result is obtained (Theorem 9): For any model of  Turing machine, including those with two-way infinite tape, there  exists a set \\(B\\) of Turing machine programs such that: {\\parindent=6mm  \\begin{itemize}\\item[(1)]\\(B\\) has nonzero asymptotic probability, \\item[(2)]\\(B\\) is polynomial time decidable, \\item[(3)]the halting problem \\(H\\cap B\\) is polynomial time decidable.  \\end{itemize}}  Assuming unary representation of natural numbers the authors denote by  FIN (COF) the set of the programs on \\(N\\) having finite (respectively,  cofinite) domains. The authors show, as a corollary to the main  theorem, that there exists a set \\(B\\) of Turing machine programs such  that the claim (3) of the Main Theorem can be replaced with the  following two ones: {\\parindent=6mm  \\begin{itemize}\\item[(3)]\\(\\text{FIN}\\cap B\\) is polynomial time decidable,  \\item[(4)]\\(\\text{COF}\\cap B\\) is polynomial time decidable.  \\end{itemize}}  The paper contains also other results and general observations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372684$56917159-5438-438C-A131-15727CFC172F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$48758E7B-5E03-469F-AB04-CA95CBD44A8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$E5E70F28-2164-41AC-88F1-4CE4426B1728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$290026EC-14AA-4C27-BC6B-CEC777E36DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$F98B384F-1932-467F-A7F6-39B911C88316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$C9A403D5-6CAA-4E4B-BED0-3A682027F682","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f8749368c2b7d18c7613c1cc40d416e7576149d","datavalue":{"value":"5176391","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$D23FA38F-B4FB-43C5-BAED-947CFD22CE50","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c0f1970b625c924543cd42f8a54c7ce976554","datavalue":{"value":"Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372684$E00856A9-75E1-42D9-90E2-28672F6C9259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9b38447a3ea959cbe95310edeeb21e7ef6903f8","datavalue":{"value":"halting problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372684$0DE5009D-1F5D-402D-AD0F-B11D06F21AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eab1db2a822c2f199222f5d286cdd6eeaeaf7fea","datavalue":{"value":"asymptotic density","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372684$7A462B4C-C585-4A43-B6E1-7F7F1B8CB5AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5addc63d0ac40779d36956c5f274f077824cc57f","datavalue":{"value":"asymptotic probability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372684$FDDC5E91-4CF6-4EDB-881C-1F9FCB572BCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19b62791329316a6c3d8b5049680f4875cfc58f7","datavalue":{"value":"polynomial time decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372684$BA45407B-7CC6-4A0D-9273-E8545A9853DA","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"955a92001efc314ce60cbd8745e41fab22f14571","datavalue":{"value":"Q56813206","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$E2C92A70-94A1-4AF2-AB75-A42533791C9C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fe64c30036b6931dfc08c246a2592bfd800c1f57","datavalue":{"value":{"entity-type":"item","numeric-id":1612485,"id":"Q1612485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2372684$841CD01B-50DC-4824-820B-5BBEC25B4FCE","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":"Q2372684$E73179C6-6AB2-4A14-A745-D268BEC461EA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"df5efc0272c0ea7f61f495f1fdbe9640c23e8ad7","datavalue":{"value":"W1963569554","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$B026E5CC-3D32-46F1-8223-C1EFC091D51C","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"5fe9b9e43ea94908d6f5964aaa7761e804cae562","datavalue":{"value":"journals/ndjfl/HamkinsM06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$7F2DFDA4-74A9-4F20-A2D9-0727810F6965","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2ad5cedfb5e97b661936218fef9236629d1210c0","datavalue":{"value":"10.1305/NDJFL/1168352664","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372684$02F05815-064D-4EAD-ACE8-7D0885B5E57A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2d9423c0667e96ab69cb7806db5cf76295e624d","datavalue":{"value":{"entity-type":"item","numeric-id":2482913,"id":"Q2482913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed168429d174a05b9290000bc07f236f195819b3","datavalue":{"value":{"amount":"+0.8165638446807861","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":"Q2372684$DBA18AE2-D921-49BA-8C72-C49955D61EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0929dbd645ef3de8b518e6b4d0506097dc6ba62f","datavalue":{"value":{"entity-type":"item","numeric-id":884482,"id":"Q884482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69e8a32fac7b7d6e6ebb8966af87ed28eb802700","datavalue":{"value":{"amount":"+0.8163120150566101","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":"Q2372684$BD82E9B9-D864-4A14-8040-7283515750B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"086a031673703433ac93482774e1b6926a0ce48f","datavalue":{"value":{"entity-type":"item","numeric-id":929131,"id":"Q929131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2072fa8a7c9ecd119169edd367bee61eb520c87e","datavalue":{"value":{"amount":"+0.8102683424949646","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":"Q2372684$46EA27F4-51C3-4A30-A721-10E8A26DF517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f53e2948f9edd63967b4b5d80119fff7f9b494f4","datavalue":{"value":{"entity-type":"item","numeric-id":2800974,"id":"Q2800974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4fffa6f9eefdf365ae45cd619cd561bfd16d099","datavalue":{"value":{"amount":"+0.8025191426277161","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":"Q2372684$6E128AAC-D113-4B05-9C46-82FDF4235A05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05cc60b8721c71ad1832530218a6bbb2438191c8","datavalue":{"value":{"entity-type":"item","numeric-id":3448787,"id":"Q3448787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db3d2b0a73f9589a9939b4b755ad06f843f0dca1","datavalue":{"value":{"amount":"+0.7964040637016296","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":"Q2372684$8C70165C-4501-458C-BA3A-67973A89CE9F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2372684","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2372684"}}}}}