Expressiveness, meanings and machines

Joseph Ray Davidson, Gregory John Michaelson

Research output: Contribution to journalArticle

21 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)367-394
Number of pages28
JournalComputability
Volume7
Issue number4
DOIs
Publication statusPublished - 24 Oct 2018

Keywords

  • elegance
  • computability
  • expressiveness
  • semantics
  • FPGA
  • primitive recursion
  • Turing machine
  • RASP machine
  • universality

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Expressiveness, meanings and machines'. Together they form a unique fingerprint.

Cite this