{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:34Z","timestamp":1777516774525,"version":"3.51.4"},"reference-count":25,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2018,5,4]],"date-time":"2018-05-04T00:00:00Z","timestamp":1525392000000},"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":[[2018,10,24]]},"abstract":"<jats:p>There is considerable interest in constructing succinct programs and much debate over which languages are most expressive. However, such debates tend to revolve around syntactic notions of program size and language constructs, without considering the complex interrelations of syntax, semantics, and implementation.<\/jats:p>\n                  <jats:p>We hypothesise that languages with larger semantics have more succinct programs. To explore this, we have conducted an empirical study of the expressive properties of Turing and Random Access Stored Program machines, taking into account their Structural Operational Semantics, universal machines, implementations in each other, and physical realisations as Field Programmable Gate Arrays (FPGAs). We conclude that our intuitions about the relationship between the expressiveness of a language and the typical succinctness of programs are largely correct. We also conclude that the information content of abstract models of computations is a good indicator of the component count for FPGA realisations.<\/jats:p>","DOI":"10.3233\/com-180090","type":"journal-article","created":{"date-parts":[[2018,5,4]],"date-time":"2018-05-04T10:23:58Z","timestamp":1525429438000},"page":"367-394","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":2,"title":["Expressiveness, meanings and machines"],"prefix":"10.1177","volume":"7","author":[{"given":"Joe","family":"Davidson","sequence":"first","affiliation":[{"name":"GoodAI, Prague, Czech Republic."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Greg","family":"Michaelson","sequence":"additional","affiliation":[{"name":"Heriot-Watt University, MACS, Edinburgh, Scotland. ."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2018,5,4]]},"reference":[{"key":"ref001","unstructured":"A.\u00a0Avram, Study: Clojure, CoffeeScript and Haskell Are the Most Expressive General-purpose Languages,\n                      InfoQ\n                      (2013), http:\/\/www.infoq.com\/news\/2013\/03\/Language-Expressiveness."},{"key":"ref002","unstructured":"D.\u00a0Berkholz, Programming languages ranked by expressiveness, Donnie Berkholz\u2019s Story of Data, 2012, http:\/\/redmonk.com\/dberkholz\/2013\/03\/25\/programming-languages-ranked-by-expressiveness\/."},{"key":"ref003","unstructured":"G.J.\u00a0Chaitin, The Unknowable. Discrete Mathematics and Theoretical Computer Science, Springer, Singapore, 1999."},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"S.A.\u00a0Cook and R.A.\u00a0Reckhow, Time-bounded random access machines, in: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, STOC \u201972, ACM, New York, NY, USA, 1972, pp.\u00a073\u201380. doi:10.1145\/800152.804898.","DOI":"10.1145\/800152.804898"},{"key":"ref005","unstructured":"J.R.\u00a0Davidson, An Information Theoretic Approach to the Expressivness of Programming Languages, PhD thesis, University of Glasgow, 2016."},{"key":"ref006","unstructured":"M.\u00a0Davis, Computability & Unsolvability, Dover Books on Computer Science Series, Dover, 1958."},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321240"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(91)90036-W"},{"key":"ref009","unstructured":"M.H.\u00a0Halstead, Elements of Software Science (Operating and Programming Systems Series), Elsevier Science Inc., New York, NY, USA, 1977."},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1007\/BF01694180"},{"key":"ref011","unstructured":"J.E.\u00a0Hopcroft, R.\u00a0Motwani and J.D.\u00a0Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd edn, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006."},{"key":"ref012","unstructured":"IEEE, IEEE Standard VHDL Language Reference Manual,\n                      IEEE Std 1076-2008 (Revision of IEEE Std 1076-2002)\n                      (2009), c1\u2013626."},{"key":"ref013","unstructured":"S.C.\u00a0Kleene, Introduction to Metamathematics. Bibl. Matematica, North-Holland, Amsterdam, 1952."},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00075-9"},{"key":"ref015","unstructured":"T.\u00a0Neary, Small universal Turing machines, PhD thesis, NUI Maynooth, 2007."},{"key":"ref016","unstructured":"R.\u00a0P\u00e9ter and I.\u00a0F\u00f6ldes, Recursive Functions, by Dr. R\u00f3zsa P\u00e9ter; Translated by Istv\u00e1n F\u00f6ldes, 3rd revised edn, Academic Press, 1967."},{"key":"ref017","unstructured":"G.D.\u00a0Plotkin, Structural approach to operational semantics, Technical report, Aarhus University, 1981."},{"issue":"3","key":"ref018","first-page":"376","volume":"30","author":"Pogorzelski H.A.","year":"1965","journal-title":"Journal of Symbolic Logic"},{"key":"ref019","unstructured":"V.J.\u00a0Rayward-Smith, A First Course in Computability, Blackwell, 1986."},{"key":"ref020","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80030-3"},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"J.E.\u00a0Stoy, Semantic models, in: Theoretical Foundations of Programming Methodology: Lecture Notes of an International Summer School Directed and Bauer, F. L. and Dijkstra, E. W. and Hoare, C. A. R., Netherlands, M.\u00a0Broy and G.\u00a0Schmidt, eds, Springer, Dordrecht, 1982, pp.\u00a0293\u2013325. doi:10.1007\/978-94-009-7893-5_10.","DOI":"10.1007\/978-94-009-7893-5_10"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"A.S.\u00a0Troelstra, Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Springer, New York, 1973.","DOI":"10.1007\/BFb0066739"},{"issue":"42","key":"ref023","first-page":"230","volume":"2","author":"Turing A.M.","year":"1936","journal-title":"Proc. London Math. Soc."},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.1109\/4235.585893"},{"key":"ref025","unstructured":"Xilinx Inc, 7 Series FPGA Configurable Logic Block, Technical report, Xilinx Inc., 2014."}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-180090","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-180090","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-180090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:58Z","timestamp":1777391998000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-180090"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,4]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,24]]}},"alternative-id":["10.3233\/COM-180090"],"URL":"https:\/\/doi.org\/10.3233\/com-180090","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,4]]}}}