计算机程序设计哲学
计算机 程序设计 哲学
2023-09-14 09:07:23 时间
计算机程序设计哲学
计算机抽象模型
图灵机(Turing machine)
- 一台图灵机是一个七元组,M = {Q,Σ,Γ,δ,q0,qaccept,qreject},其中 Q,Σ,Γ 都是有限集合,且满足:
1、Q 是状态集合;
2、Σ 是输入字母表,其中不包含特殊的空白符;
3、Γ 是带字母表,其中 □∈Γ且Σ∈Γ ;
4、 δ:Q ×「 → Q × Γ × {L,R} 是转移函数,其中L,R 表示读写头是向左移还是向右移;
5、q0∈Q是起始状态;
6、qaccept是接受状态。
7、qreject是拒绝状态,且qreject≠qaccept。 - 对于任意一个图灵机,因为它的描述是有限的,因此我们总可以用某种方式将其编码为字符串。我们用 <M> 表示图灵机 M 的编码。我们可以构造出一个特殊的图灵机,它接受任意一个图灵机 M 的编码<M> ,然后模拟 M 的运作,这样的图灵机称为通用图灵机(Universal Turing Machine)。现代电子计算机其实就是这样一种通用图灵机的模拟,它能接受一段描述其他图灵机的程序,并运行程序实现该程序所描述的算法。