{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:51:30Z","timestamp":1777517490282,"version":"3.51.4"},"reference-count":65,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2020,12,28]],"date-time":"2020-12-28T00:00:00Z","timestamp":1609113600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2021,4,16]]},"abstract":"<jats:p>The term \u2018Halting Problem\u2019 arguably refers to computer science\u2019s most celebrated impossibility result and to the core notion underlying the language-theoretic approach to security. Computer professionals often ignore the Halting Problem however. In retrospect, this is not too surprising given that several advocates of computability theory implicitly follow Christopher Strachey\u2019s alleged 1965 proof of his Halting Problem (which is about executable \u2013 i.e., hackable \u2013 programs) rather than Martin Davis\u2019s correct 1958 version or his 1994 account (each of which is solely about mathematical objects). For the sake of conceptual clarity, particularly for researchers pursuing a coherent science of cybersecurity, I will scrutinize Strachey\u2019s 1965 line of reasoning\u00a0\u2013 which is widespread today \u2013 both from a charitable, historical angle and from a critical, engineering perspective.<\/jats:p>","DOI":"10.3233\/com-180217","type":"journal-article","created":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T10:59:56Z","timestamp":1609239596000},"page":"141-158","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["The halting problem and security\u2019s language-theoretic approach: Praise and criticism from a technical historian"],"prefix":"10.1177","volume":"10","author":[{"given":"Edgar G.","family":"Daylight","sequence":"first","affiliation":[{"name":"School of Media and Information, Siegen University, Herrengarten 3, 57072 Siegen, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2020,12,28]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-34799-2_28"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/6682.001.0001"},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.2014.61"},{"issue":"6","key":"ref004","first-page":"13","volume":"36","author":"Bratus S.","year":"2011","journal-title":"USENIX; login"},{"key":"ref005","doi-asserted-by":"crossref","unstructured":"P.Br\u00f6dner, Coping with Descartes\u2019 error in information systems,\n                      AI & Society\n                      (Published online: 17 January 2018).","DOI":"10.1007\/s00146-018-0798-8"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1145\/2658985"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1145\/2830565"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0167-4048(87)90122-2"},{"key":"ref009","unstructured":"T.R.Colburn, Philosophy and Computer Science, M.E. Sharpe, 2000."},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1145\/1941487.1941509"},{"key":"ref011","unstructured":"B.J.Copeland (ed.), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life Plus the Secrets of Enigma, Clarendon Press, Oxford, 2004."},{"key":"ref012","unstructured":"M.Davis, Computability and Unsolvability, McGraw-Hill, New York, USA, 1958."},{"key":"ref013","doi-asserted-by":"crossref","unstructured":"M.Davis, R.Sigal and E.J.Weyuker, Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, 2nd edn, Morgan Kaufmann, 1994.","DOI":"10.1016\/B978-0-08-050246-5.50020-9"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxr002"},{"key":"ref015","unstructured":"E.G.Daylight, The Dawn of Software Engineering: From Turing to Dijkstra, Lonely Scholar, 2012."},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1145\/2629499"},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1080\/01445340.2015.1082050"},{"key":"ref018","unstructured":"E.G.Daylight, Turing Tales, Lonely Scholar, 2016."},{"key":"ref019","unstructured":"L.De Mol, Turing Machines,\n                      The Stanford Encyclopedia of Philosophy\n                      , 2018 Edition (2018), plato.stanford.edu\/entries\/turing\u2013machine\/."},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"W.Dean, Algorithms and the mathematical foundations of computer science, in: G\u00f6del\u2019s Disjunction, L.Horsten and P.Welch, eds, 1st edn, Oxford University Press, 2016.","DOI":"10.1093\/acprof:oso\/9780198759591.003.0002"},{"key":"ref021","doi-asserted-by":"publisher","DOI":"10.1145\/359104.359106"},{"key":"ref022","unstructured":"Duizenden pacemakers kwetsbaar voor hacking,\n                      De Standaard\n                      (2 September 2017)."},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48530"},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.1080\/095281398146653"},{"key":"ref025","unstructured":"J.H.Fetzer, Philosophy and computer science: Reflections on the program verification debate, in: The Digital Phoenix: How Computers Are Changing Philosophy, T.W.Bynum and J.H.Moor, eds, Blackwell, 1998, pp.\u00a0253\u2013273."},{"key":"ref026","unstructured":"E.Filiol, Computer Viruses: From Theory to Applications, Springer, 2005."},{"key":"ref027","doi-asserted-by":"publisher","DOI":"10.1145\/368959.368993"},{"key":"ref028","unstructured":"M.R.Garey and D.S.Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979."},{"key":"ref029","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1971.5216113"},{"key":"ref030","unstructured":"M.Goodman, Future Crimes: Inside the Digital Underground and the Battle for Our Connected World, Corgi Books, 2016."},{"key":"ref031","unstructured":"K.D.Grave, Networking self-driving cars, a comment on Edgar Daylight\u2019s blog (dijkstrascry.com) from a specialist in the automotive industry, Vol. 6, August 2016, dijkstrascry.com\/comment\/2232#comment-2232."},{"key":"ref032","unstructured":"J.E.Hopcroft, R.Motwani and J.D.Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley\/Pearson Education, 2007."},{"key":"ref033","unstructured":"S.C.Kleene, Introduction to Metamathematics, Van Nostrand, Princeton, New Jersey, USA, 1952."},{"key":"ref034","unstructured":"J.K\u00f6nig, On the foundations of set theory and the continuum problem, in: From Frege to G\u00f6del: A Source Book in Mathematical Logic, 1879\u20131931, Harvard University Press, 1981."},{"key":"ref035","doi-asserted-by":"crossref","unstructured":"E.A.Lee, in: The Past, Present and Future of Cyber-Physical Systems: A Focus on Models, Sensors, Vol. 15, 2015, pp.\u00a04837\u20134869.","DOI":"10.3390\/s150304837"},{"key":"ref036","doi-asserted-by":"crossref","unstructured":"E.A.Lee, Plato and the Nerd: The Creative Partnership of Humans and Technology, MIT Press, 2017.","DOI":"10.7551\/mitpress\/11180.001.0001"},{"key":"ref037","doi-asserted-by":"publisher","DOI":"10.1145\/3029589"},{"key":"ref038","unstructured":"D.MacKenzie, Mechanizing Proof: Computing, Risk, and Trust, MIT Press, 2004."},{"key":"ref039","unstructured":"M.S.Mahoney, Histories of Computing, Harvard University Press, Cambridge, Massachusetts\/London, England, 2011."},{"key":"ref040","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2011.0332"},{"key":"ref041","unstructured":"L.Mearian, Here\u2019s Why Self-Driving Cars May Never Really Be Self-Driving, Computerworld, See: computerworld.com\/article\/3171160\/car-tech\/heres-why-self-driving-cars-may-never-really-be-self-driving.html. Accessed on 27th January 2018."},{"key":"ref042","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/29.3.213"},{"key":"ref043","doi-asserted-by":"publisher","DOI":"10.1145\/214956.214961"},{"key":"ref044","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-012-2904-2"},{"key":"ref045","doi-asserted-by":"crossref","unstructured":"G.Primiero, On the Foundations of Computing, Oxford University Press, 2020.","DOI":"10.1093\/oso\/9780198835646.001.0001"},{"key":"ref046","unstructured":"W.J.Rapaport, What Is a Computer? A Survey, Minds and Machines, 2018, Published online: 25 May 2018."},{"key":"ref047","unstructured":"M.C.Reingruber and W.W.Gregory, The Data Modeling Handbook: A Best-Practice Approach to Building Quality Data Models, Wiley, 1994."},{"key":"ref048","unstructured":"B.Russell, Mathematical logic as based on the theory of types, in: From Frege to G\u00f6del: A Source Book in Mathematical Logic, 1879\u20131931, Harvard University Press, 1981."},{"issue":"6","key":"ref049","first-page":"22","volume":"36","author":"Sassaman L.","year":"2011","journal-title":"USENIX; login"},{"issue":"2","key":"ref050","first-page":"47","volume":"19","author":"Schneider F.B.","year":"2012","journal-title":"The Next Wave"},{"key":"ref051","unstructured":"E.Sch\u00fcttpelz, Figuren der Rede: Zur Theorie der Rhetorischen Figur, Eric Schmidt Verlag GmbH & Co., 1996."},{"key":"ref052","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015694932257"},{"key":"ref053","unstructured":"S.Shapiro, Thinking About Mathematics: The Philosophy of Mathematics, Oxford University Press, 2000."},{"key":"ref054","doi-asserted-by":"crossref","unstructured":"R.Slayton, Arguments That Count: Physics, Computing, and Missile Defense, 1949\u20132012, MIT Press, 2013.","DOI":"10.7551\/mitpress\/9234.001.0001"},{"key":"ref055","doi-asserted-by":"publisher","DOI":"10.1145\/379486.379512"},{"key":"ref056","unstructured":"J.Somers, The Coming Software Apocalypse,\n                      The Atlantic\n                      , (2017), See: theatlantic.com\/technology\/archive\/2017\/09\/saving-the-world-from-code\/540393\/."},{"key":"ref057","unstructured":"P.N.Stearns, Why Study History? American Historical Association, 1998, Position statement: historians.org\/about-aha-and-membership\/aha-history-and-archives\/historical-archives\/why-study-history-(1998)."},{"key":"ref058","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010070228552"},{"key":"ref059","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/7.4.313"},{"key":"ref060","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010000313106"},{"key":"ref061","doi-asserted-by":"crossref","unstructured":"L.A.Suchman, Human-Machine Reconfigurations: Plans and Situated Actions, 2nd edn, Cambridge University Press, 2007.","DOI":"10.1017\/CBO9780511808418"},{"key":"ref062","doi-asserted-by":"publisher","DOI":"10.1007\/s13347-012-0098-z"},{"key":"ref063","doi-asserted-by":"crossref","unstructured":"R.Turner, Computational Artifacts: Towards a Philosophy of Computer Science, Springer, 2018.","DOI":"10.1007\/978-3-662-55565-1"},{"key":"ref064","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxu145"},{"key":"ref065","doi-asserted-by":"crossref","unstructured":"M.Vanhoef and F.Piessens, Key Reinstallation Attacks: Forcing Nonce Reuse in WPA2, in: ACM SIGSAC Conference on Computer and Communications Security 2017, ACM, 2017, pp.\u00a01313\u20131328.","DOI":"10.1145\/3133956.3134027"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-180217","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-180217","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-180217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T16:02:48Z","timestamp":1777392168000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-180217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,28]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,16]]}},"alternative-id":["10.3233\/COM-180217"],"URL":"https:\/\/doi.org\/10.3233\/com-180217","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,28]]}}}