可计算性

计算机科学概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

什么是可计算性？

可计算问题

• 算法存在： 有清晰步骤。
• 有限时间： 在有限步内产生输出。

不可计算问题

• 无算法： 对所有输入无法求解。
• 计算无限： 可能永不结束。

¹ 一旦找到算法和/或使已知算法在有限时间内结束，非可计算问题可转为可计算问题。

自动机

自动机的定义

• 假想机器
• 帮助理解计算原理
• 有状态
• 有状态转换规则

有限自动机（FA）

有限自动机（FA）

• 简单的"机器"
• 状态数固定
• 除当前状态外无记忆

下推自动机（PDA）

下推自动机（PDA）

• 更强大
• 有状态
• 具有栈式内存，可做更复杂决策

总结

有限自动机（FA）

• 适用于简单任务

下推自动机（PDA）

• 更适合复杂问题

重要性

• 若能用自动机建模，就能实现算法来求解

让我们练习吧！

计算机科学概念