图灵机

计算机科学概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

从自动机到图灵机

• 有限自动机：内存有限，处理正则语言。
• 下推自动机：基于栈，处理上下文无关语言。
• 图灵机：内存无限（无限纸带），可解所有可计算问题。

什么是图灵机？

图灵机

• 抽象机器，具无限纸带。
• 读写符号。
• 能模拟任何算法。

用类比理解图灵机

厨房与厨师类比图灵机

• 操作台是纸带。
• 操作台分区是格子。
• 食材是符号。
• 厨师是读/写的读写头。
• 菜谱是程序，指导全流程。

图灵机为何重要？

图灵机与可计算性

• 可模拟任何算法
• 界定计算机可解问题的边界
• 引入不可判定问题的概念（如停机问题）
• 奠定现代计算理论基础

停机问题

• 问题：能否预测某程序在特定输入上会停止还是永远运行？
• 图灵的洞见：不存在对所有程序通用的算法。
• 结论：停机问题不可判定，有些问题无算法解。
• 影响：计算极限影响密码学与人工智能

Passons à la pratique !

计算机科学概念