一句话：通过在 AuDaLa 中实现并验证图灵机，证明其图灵完备，并探讨提升实用表达力的扩展。
AuDaLa 是一种新提出的数据自治（data autonomous）编程语言，其中小片数据可自主执行函数。本文关注该语言表达能力的界定，核心问题是在其范式与设计选择下它能表达何种计算。作者在 AuDaLa 中实现图灵机并证明该实现正确，从而证明 AuDaLa 是图灵完备的，为其表达力提供初步依据。此外，论文给出若干向 AuDaLa 添加扩展的示例，以提升实际表达能力并更贴近传统并行语言，使算法实现更直接且性能更好。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{FrankenN26,
title = {Expressivity of AuDaLa: Turing Completeness and Possible Extensions},
author = {Tom T. P. Franken and Thomas Neele},
journal = {Logical Methods in Computer Science},
volume = {Volume 22, Issue 2},
year = {2026},
doi = {10.46298/lmcs-22(2:5)2026}
}