Programming languages shouldn't and needn't be Turing complete
Any algorithmic problem faced by application programmers in the wild can in principle be solved using a Turing incomplete programming language. [Rice 1953] suggests that Turing completeness bears a heavy price, fundamentally limiting the ability of automatic assistants to help programmers be more productive, create less bugs and write safer software. Nevertheless, no widespread programming language is Turing incomplete. While there are some strongly-normalizing dependently typed languages, they require in-depth academic knowledge and currently lack affordances for practical application development. We contend that the pervasive choice of Turing completeness across programming languages has been driven by ill-placed expediency rather than necessity. In particular, loops and recursion are common ”Turing-traps”: Sources of Turing completeness, whether accidental or intentional. We present an approach to eliminating Turing-traps during the language design process, with several examples suitable for non-academic languages. Designers of modern practical programming languages should strongly consider evading Turing completeness and enabling better verification, security, automated testing and distributed computing.
Wed 18 NovDisplayed time zone: Central Time (US & Canada) change
15:00 - 16:20
|Programming languages shouldn't and needn't be Turing complete|
|User-Centered Programming Language Design: A Course-Based Case Study|
Michael Coblenz University of Maryland at College Park, Ariel Davis Carnegie Mellon University, Megan Hofmann Carnegie Mellon University, Vivian Huang Carnegie Mellon University, Siyue Jin Carnegie Mellon University, Max Krieger , Kyle Liang Carnegie Mellon University, Brian Wei Carnegie Mellon University, Mengchen Sam Yong Carnegie Mellon University, Jonathan Aldrich Carnegie Mellon UniversityLink to publication
|Day 1 Discussion|