主要观点：

• 程序员常使用“图灵完备性”术语，多数关于非图灵完备性的讨论是误解，其并非人们所想，而是多种实用属性的替代。
• 图灵完备性有特定含义，不能随意重新定义。理解图灵完备性需知道关于原始递归函数的理论结果，这是 CS 教育的缺失。
• 文章分三部分：第一部分给出理论结果及后果的简要总结；第二部分介绍图灵机、有限状态自动机和原始递归函数；第三部分回到实际问题。
• 实际中，非图灵完备语言在处理大多数实际问题时不受限制，程序不终止和需大量步骤终止在实践中等价，使语言非图灵完备不能解决程序终止问题。
• 有限状态自动机是简单的二进制识别器，不能进入无限循环，其表达能力与正则表达式等价；图灵机比有限状态自动机更强大，有可变磁带，可模拟有限状态自动机，存在通用图灵机，Python 和图灵机有等效计算能力，存在比图灵机弱的计算设备。
• 图灵机存在不能计算的函数，如停机问题，对于任意程序，很难说出其性质，不存在非平凡的可算法检查的重构不变属性。
• 原始递归函数是一种计算设备，总是终止且非图灵完备，但有一定计算能力，可定义基本编程要素和复杂数学函数，虽不能模拟任意图灵机，但能模拟图灵机的单个步骤。
• 非终止并非实现为原始递归函数的唯一障碍，存在超出原始递归函数能力的函数，可通过组合有限状态自动机和图灵机的思想来构造。
• 在实际中，非图灵完备语言有一定表达能力，如将图灵完备语言添加迭代计数器并强制终止可使其变为原始递归函数，且不同配置语言有其设计目标，如确定性、定义明确、纯性、安全性和简单性等。

关键信息：

• 理论结果：若程序在图灵完备语言中且不太慢（运行快于(O(2^{2N}))），可在非图灵完备语言中实现，大多数实际问题属于此空间，非图灵完备语言在实践中不限制或额外控制计算。
• 有限状态自动机定义及示例，其不能识别特定无限集字符串。
• 图灵机定义、编程细节（如磁带处理、编码方案、通用图灵机等）及示例。
• 图灵机的极限，如存在不能计算的函数（停机问题），不存在非平凡的可算法检查的重构不变属性。
• 原始递归函数定义及各种函数的构造方法（如加法、乘法等），不能模拟任意图灵机，但可模拟图灵机的单个步骤。

重要细节：

• 有限状态自动机有有限个状态，通过转移函数根据当前状态和输入符号确定新状态，其行为决定输入字符串是否被接受。
• 图灵机有状态、转移函数、可变磁带，可在达到指定停机状态时停止，其行为决定输入的处理结果，可能不终止。
• 原始递归函数定义为接受自然数元组并返回自然数的函数，通过组合基本函数（如零、后继、循环等）来构造更复杂的函数。
• 证明不存在识别特定无限集字符串的有限状态自动机的方法，通过假设存在并利用其状态有限性找到循环，从而构造矛盾。
• 证明存在能识别特定字符串的图灵机的方法，如通过逐步擦除和移动来判断。
• 构造不能由图灵机计算的函数(g)的方法，通过与已知的图灵机函数(f)进行差异构造。
• 原始递归函数构造中的各种技巧，如使用部分应用函数、处理减法等问题。
• 配置语言的设计目标，如确定性、定义明确、纯性、安全性和简单性等。