Core Topics in the Theory of Computation | 计算理论核心内容解析

📚 Core Topics in the Theory of Computation | 计算理论核心内容解析

Computer science is not only about writing programs; it is also about knowing what can be computed and how hard that computation is. The theory of computation supplies the vocabulary and proof techniques for answering these questions. This revision article walks through automata, formal languages, Turing machines, undecidability and complexity classes – the core topics that regularly appear in A-Level Computer Science papers.

计算机科学不只是写代码，更要理解什么可以被计算、计算起来有多难。计算理论为这些问题提供了术语与证明方法。这篇复习文章沿着自动机、形式语言、图灵机、不可判定性和复杂度类展开，这些正是 A-Level 计算机科学考卷中反复出现的核心考点。

1. Algorithms and Formal Problems | 算法与形式化问题

The theory of computation starts from the definition of an algorithm: a finite list of unambiguous and effective instructions. Given an input, an algorithm must terminate after a finite number of steps, and it must produce the same output every time it is run with the same input. A decision problem is then formalised as a language over an alphabet; solving the problem means accepting every valid instance and rejecting every invalid instance.

计算理论首先建立在“算法”的定义上：一组有限、明确、可执行且无歧义的指令。对于给定输入，算法必须在有限步内终止，并且相同输入必须产生相同输出。判定问题被形式化为某个字母表上的语言；解决问题意味着接受所有合法实例、拒绝所有非法实例。

This shift from code to formal objects is why examiners expect you to discuss problems, not just programs. Before writing a Turing machine or a proof, always ask what the input alphabet is and what counts as an accepting outcome.

从代码转向形式化对象，正是考官希望看到的思维方式。在编写图灵机或构造证明之前，先问自己：输入字母表是什么？什么样的结果算接受？

2. Finite State Machines | 有限状态机

A finite state machine (FSM) is an abstract machine with a finite number of states and explicit rules for changing between them. A deterministic finite automaton can be written as the tuple

Published by TutorHao | Computer Science Revision Series | aleveler.com

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