The Expressive Power of Programming Languages

关于程序设计语言的文献包含了大量关于程序设计语言的相对表达能力以及相对于程序设计语言的程序设计结构的可表达性或不可表达性的非正式声明。尽管在各个分支学科中取得了巨大的进步，但编程语言理论还没有发展出一个正式的框架来指定和验证这些语句。因此，也不可能从这些声明中得出任何可靠的结论，也不可能将它们用于编程语言的客观比较。最近开始对程序设计语言的表达性进行调查。基于可表达性的第一个形式化，现在可以正式区分有限环境中的通用编程语言，并且可以确认文献中的一些非正式声明。为了拓宽我们的视野，我们将探讨当前框架内的更多例子。从这些例子中，我们将推导出更多关于形式框架的元属性。

The literature on programming languages contains an abundance of informal claims on the relative expressive power of programming languages and on the expressibility or non-expressibility of programming constructs with respect to programming languages. Despite tremendous progress in various subdisciplines, programming language theory has not developed a formal framework for specifying and verifying such statements. Consequently, it is also impossible to draw any solid conclusions from such claims or to use them for an objective comparison of programming languages. An investigation of the expressiveness of programming languages has recently been initiated. Based on a first formalization of expressibility, universal programming languages in a restricted setting can now formally be distinguished and some of the informal claims in the literature can be confirmed. More examples within the current framework will be explored in order to broaden our perspective. From these examples, more meta-properties about the formal framework will be deduced.