Core Concepts and Applications of Computational Models | 计算模型的核心概念与应用

📚 Core Concepts and Applications of Computational Models | 计算模型的核心概念与应用

A computational model is an abstract mathematical description of how a machine or algorithm processes input and produces output. It defines the rules, memory structures, and operations that a computing system can perform, serving as the theoretical foundation for computer science.

计算模型是对机器或算法如何处理输入并产生输出的抽象数学描述。它定义了计算系统可以执行的规则、存储结构和操作，是计算机科学的理论基础。

1. What Is a Computational Model? | 什么是计算模型？

A computational model specifies the basic components of a computing device: the set of possible states, the input alphabet, the transition function, and the acceptance condition. Different models have different levels of power, measured by the complexity of the languages they can recognise.

计算模型规定了一个计算设备的基本组成部分：可能的状态集合、输入字母表、转移函数和接受条件。不同的模型具有不同的能力等级，以它们能识别的语言复杂度来衡量。

State: A snapshot of the machine at a given moment.
Transition: A deterministic or non-deterministic rule mapping a state and input to a new state.
Acceptance: The condition under which an input string is considered part of the language.

状态：机器在某一时刻的快照。
转移：将状态和输入映射到新状态的确定性或非确定性规则。
接受：输入字符串被视为语言一部分的条件。

2. The Turing Machine | 图灵机

The Turing machine, proposed by Alan Turing in 1936, is the most powerful computational model. It consists of an infinite tape divided into cells, a read/write head, and a finite control unit. The machine reads a symbol, writes a new symbol, moves the head left or right, and changes state according to a transition table.

图灵机由艾伦·图灵于1936年提出，是最强大的计算模型。它由一条无限长的纸带（分为单元格）、一个读写头和有限控制器组成。机器读取一个符号，写入新符号，将头向左或向右移动，并根据转移表改变状态。

M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)

Q: finite set of states
Σ: input alphabet (does not contain blank)
Γ: tape alphabet, where Σ ⊂ Γ and blank ∈ Γ
δ: transition function: δ(q, a) → (q’, b, direction)
q₀: start state
q_accept / q_reject: accepting / rejecting states

Q：有限状态集合
Σ：输入字母表（不含空白符号）
Γ：纸带字母表，其中 Σ ⊆ Γ 且空白符号 ∈ Γ
δ：转移函数：δ(q, a) → (q’, b, 方向)
q₀：起始状态
q_accept / q_reject：接受/拒绝状态

3. Finite Automata | 有限自动机

A finite automaton (FA) is the simplest computational model. It has a finite number of states and no external memory. It reads characters one by one from left to right and changes state accordingly. If the machine ends in an accepting state after processing the entire input, the input is accepted.

有限自动机（FA）是最简单的计算模型。它只有有限数量的状态，没有外部存储器。它从左到右逐个读取字符并相应改变状态。如果处理完整输入后，机器处于接受状态，则输入被接受。

There are two types:

有两种类型：

Deterministic finite automaton (DFA): Each transition has exactly one target state for a given input symbol.
Non-deterministic finite automaton (NFA): A state may have multiple possible transitions for the same input, including ε (epsilon) transitions that occur without consuming input.

确定性有限自动机（DFA）：对于给定的输入符号，每个转移只有一个目标状态。
非确定性有限自动机（NFA）：同一输入可以有多个可能转移，包括不消耗输入的 ε（epsilon）转移。

DFA and NFA recognise exactly the class of regular languages, and they are equivalent in expressive power.

DFA 和 NFA 识别的语言类恰好是正则语言，它们在表达能力上是等价的。

4. Regular Expressions and Languages | 正则表达式与语言

A regular language is a language that can be described by a regular expression or accepted by a finite automaton. Regular expressions are a concise notation for patterns built from literals, concatenation, union (|), and the Kleene star (*).

正则语言是可以用正则表达式描述或由有限自动机接受的语言。正则表达式是对由字面量、连接、并（|）和克莱尼星号（*）构成的模式的一种简洁表示法。

For example, the pattern a(b|c)* matches strings starting with ‘a’ followed by any number of ‘b’ or ‘c’ characters.

例如，模式 a(b|c)* 匹配以 ‘a’ 开头后跟任意数量的 ‘b’ 或 ‘c’ 字符的字符串。

ε represents the empty string.
∅ represents the empty language.
If R and S are regular expressions, then R|S, RS, and R* are also regular expressions.

ε 表示空字符串。
∅ 表示空语言。
如果 R 和 S 是正则表达式，则 R|S、RS 和 R* 也是正则表达式。

5. Pushdown Automata and Context-Free Languages | 下推自动机与上下文无关语言

A pushdown automaton (PDA) is a finite automaton extended with a stack. The stack provides unbounded memory but only in a LIFO (last-in-first-out) manner. PDAs recognise exactly the class of context-free languages (CFLs).

下推自动机（PDA）是有限自动机增加一个栈后的扩展。栈提供了无界内存，但只能以 LIFO（后进先出）方式访问。PDA 识别的语言类恰好是上下文无关语言（CFL）。

Context-free grammars (CFGs) generate CFLs. A CFG consists of variables (non-terminals), terminals, production rules, and a start symbol. For instance, the language of balanced parentheses can be generated by: S → (S)S | ε.

上下文无关文法（CFG）生成 CFL。一个 CFG 由变量（非终结符）、终结符、产生式规则和起始符号组成。例如，平衡括号语言可以由 S → (S)S | ε 生成。

PDA = FA + Stack

PDAs are important in parsing programming languages. Many compilers use a stack-based parser to check syntactic structure according to a CFG.

PDA 在编程语言解析中非常重要。许多编译器使用基于栈的解析器，依据 CFG 检查语法结构。

6. Turing Completeness and the Halting Problem | 图灵完备性与停机问题

Any computational model that can simulate a Turing machine is called Turing complete. Most modern programming languages are Turing complete, meaning they can compute any function computable by a Turing machine — provided sufficient time and memory are available.

任何能模拟图灵机的计算模型都称为图灵完备的。大多数现代编程语言都是图灵完备的，这意味着只要时间和内存充足，它们就能计算任何图灵机可计算的函数。

The halting problem asks whether there exists a Turing machine that, given a description of another Turing machine and its input, can decide whether that machine eventually halts. Turing proved in 1936 that no such universal decider exists.

停机问题问的是：是否存在一个图灵机，给定另一个图灵机的描述及其输入，能够判定该机器是否最终会停机。图灵在1936年证明，这样的通用判定器不存在。

Halting Problem is undecidable ⇒ no algorithm can always determine whether a program terminates.

停机问题不可判定 ⇒ 不存在总能判断程序是否终止的算法。

7. Computability and Undecidability | 可计算性与不可判定性

A function is computable (or decidable) if there exists a Turing machine that computes it for every valid input in finite time. Languages whose membership can be decided by a Turing machine are called recursive (decidable). Semidecidable languages are those accepted by a Turing machine that may loop forever on non-members.

一个函数是可计算的（或可判定的），如果存在一个图灵机对每个有效输入都能在有限时间内计算出结果。其成员关系可由图灵机判定的语言称为递归（可判定）语言。半可判定语言是被图灵机接受，但对非成员可能永远循环的语言。

Decidable: There is a Turing machine that always halts and answers YES or NO correctly.
Recognisable: There is a Turing machine that halts on YES instances but may not halt on NO instances.
Undecidable: No Turing machine can decide it correctly in all cases.

可判定：存在一个图灵机总是停机并正确回答是或否。
可识别：存在一个图灵机在“是”实例上停机，但在“否”实例上可能不停机。
不可判定：不存在任何图灵机在所有情况下都能正确判定。

Other classic undecidable problems include the Post correspondence problem and Rice’s theorem, which states that any non-trivial property of the language recognised by a Turing machine is undecidable.

其他经典不可判定问题包括波斯特对应问题和莱斯定理。莱斯定理指出，图灵机所识别语言的任何非平凡属性都是不可判定的。

8. Introduction to Computational Complexity | 计算复杂性简介

Computational complexity classifies problems according to the resources needed to solve them, primarily time and space. The class P contains decision problems solvable in polynomial time by a deterministic Turing machine. The class NP contains problems verifiable in polynomial time, even if solving them takes exponential time.

计算复杂性根据解题所需资源（主要是时间和空间）对问题进行分类。P 类包含可由确定性图灵机在多项式时间内求解的判定问题。NP 类包含可在多项式时间内验证解的问题，即使求解可能需要指数时间。

P ⊆ NP

The famous P vs NP question asks whether every problem whose solution can be quickly verified (NP) can also be quickly solved (P). This remains an open problem in computer science.

著名的 P vs NP 问题询问：每个解能被快速验证的问题（NP）是否也能被快速求解（P）。这至今仍是计算机科学中的开放问题。

P: O(nᵏ) time for some constant k.
NP: A solution can be checked in O(nᵏ) time.
NP-complete: The hardest problems in NP; if any one has a polynomial-time solution, then P = NP.

P：O(nᵏ) 时间，k 为常数。
NP：解可在 O(nᵏ) 时间内验证。
NP 完全：NP 中最难的问题；如果其中任何一个有多项式时间解法，则 P = NP。

9. Applications of Computational Models | 计算模型的应用

Computational models are not merely theoretical — they underpin practical tools used daily:

计算模型不仅仅是理论，它们支撑着日常使用的实际工具：

Model	Application
Finite automata	Text search, network protocol validation, digital circuit design
Regular expressions	Pattern matching in programming languages, lexical analysis in compilers
Pushdown automata	Syntax parsing, expression evaluation
Turing machine	Modeling general-purpose computers, proving unsolvable problems
Context-free grammars	Programming language specification, markup language definitions (e.g., XML, HTML)

模型	应用
有限自动机	文本搜索、网络协议验证、数字电路设计
正则表达式	编程语言中的模式匹配、编译器的词法分析
下推自动机	语法解析、表达式求值
图灵机	建模通用计算机、证明不可解问题
上下文无关文法	编程语言规范、标记语言定义（如 XML、HTML）

10. Exam Focus and Common Questions | 考试要点与常见问题

In A-Level and AP Computer Science exams, you may be asked to compare computational models, construct state diagrams, or explain the halting problem. Key skills include:

在 A-Level 和 AP 计算机科学考试中，你可能会被要求比较计算模型、构建状态图或解释停机问题。关键技能包括：

Given a simple language, design a DFA or NFA that accepts it.
Convert an NFA to a DFA using subset construction (conceptually).
Write a regular expression matching a given set of strings.
Explain why the halting problem is undecidable.
Describe the role of a stack in a PDA and its relationship to context-free grammars.
Identify whether a language is regular, context-free, or recursively enumerable.

给定一个简单语言，设计一个接受该语言的 DFA 或 NFA。
使用子集构造法（概念上）将 NFA 转换为 DFA。
编写与给定字符串集合匹配的正则表达式。
解释为什么停机问题不可判定。
描述栈在 PDA 中的作用及其与上下文无关文法的关系。
判断一个语言是正则语言、上下文无关语言还是递归可枚举语言。

Memory tip: Regular ⊂ Context-free ⊂ Recursive ⊂ Recursively enumerable

记忆提示：正则语言 ⊂ 上下文无关语言 ⊂ 递归语言 ⊂ 递归可枚举语言

11. Summary | 总结

Computational models provide a hierarchical view of computing power. Finite automata capture simple patterns, pushdown automata add stack memory for nested structures, and Turing machines formalise the concept of general computation. Understanding these models helps you reason about what computers can and cannot compute, and connects directly to programming languages, compilers, and algorithm design.

计算模型提供了计算能力的层次化视角。有限自动机捕捉简单模式，下推自动机增加栈内存以处理嵌套结构，图灵机形式化通用计算的概念。理解这些模型有助于你推理计算机能做什么、不能做什么，并直接关联到编程语言、编译器和算法设计。

Published by TutorHao | 计算机 Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Core Concepts and Applications of Computational Models | 计算模型的核心概念与应用