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. 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.
|Number of pages||28|
|Publication status||Published - 24 Oct 2018|
- primitive recursion
- Turing machine
- RASP machine
ASJC Scopus subject areas
- Computer Science(all)
FingerprintDive into the research topics of 'Expressiveness, meanings and machines'. Together they form a unique fingerprint.
Gregory John Michaelson
- School of Mathematical & Computer Sciences - Professor Emeritus
- School of Mathematical & Computer Sciences, Computer Science - Professor Emeritus