Expressivity of AuDaLa: Turing Completeness and Possible Extensions
Establishes the theoretical expressivity of a new programming paradigm for autonomous data, providing a foundation for future language development.
The paper proves that the AuDaLa programming language is Turing complete by implementing and verifying Turing machines, and discusses extensions to improve its practical expressivity for parallel algorithms.
AuDaLa is a recently introduced programming language that follows the new data autonomous paradigm. In this paradigm, small pieces of data execute functions autonomously. Considering the paradigm and the design choices of AuDaLa, it is interesting to determine the expressivity of the language. In this paper, we implement Turing machines in AuDaLa and prove that implementation correct. This proves that AuDaLa is Turing complete, giving an initial indication of AuDaLa's expressivity. Additionally, we give examples of how to add extensions to AuDaLa to increase its practical expressivity and to better match conventional parallel languages, allowing for a more straightforward and performant implementation of algorithms.