现代可计算性理论的基础是图灵机吗

发布网友发布时间：2022-04-29 14:26

共1个回答

热心网友时间：2023-10-10 19:42

现代可计算性理论的基础是图灵机。

早在30年代，图灵对存在通用图灵机的逻辑证明表明，制造出能编程序来作出任何计算的通用计算机是有可能的，这影响了40年代出现的存储程序的计算机（即冯诺依曼型计算机）的设计思想。可计算性理论确定了哪些问题可能用计算机解决，哪些问题是不可能用计算机解决的。

可计算性理论的应用领域有：

1、程序理论：程序逻辑、程序正确性验证、形式开发方法等。

2、计算理论：算法设计与分析、复杂性理论、可计算性理论等。

3、语言理论：形式语言理论、自动机理论、形式语义学、计算语言学等。

4、人工智能：知识工程、机器学习、模式识别、机器人等。

5、逻辑基础：数理逻辑、多值逻辑、模糊逻辑、模态逻辑、直觉主义逻辑、组合逻辑等。

6、数据理论：演绎数据库、关系数据库、面向对象数据库等。

7、计算机数学：符号计算、数学定理证明、计算几何等。

8、并行计算：网络计算、分布式并行计算、大规模并行计算、演化算法等。